#1 DarkMaster@2008-08-08 18:41:00
3812
回复
删除
动态规划,用f[i,j]表示有i+3根柱子,j个盘子所需要的最小移动次数,很容易写出状态转移方程:
f[i+1,j]=min{2*f[i+1,j-k]+f[i,k]|1<=k<n}
#2 lizhixin@2008-08-09 01:22:00
3840
回复
删除
我的想法:
for i:=1 to n-1 do
begin
s[i]:=(i-1)*2+1;
end;(递推的边界条件)
for i:=n to m do
s[i]:=2*s[i-(n-2)]+(n-3)*2+1;
(把第一个柱子的I-1个移走,I-(N-2)个占一个柱子,N-3个每个占一个柱子,再把N-3+1个大盘子移到第N个柱子上,再把I-(N-2)个移到第N个柱子.)
writeln(s[m] mod 181818181818);
#3 DarkMaster@2008-08-09 01:30:00
3842
回复
删除
LZ如果还不明白可以看看
北京大学学报(自然科学版)里面有一篇论文:
《多柱汉诺塔问题研究(刘铎 戴一奇)》里面对多柱汉诺塔问题进行了研究.采用动态规划的想法,给出了多柱汉诺塔问题最少移动步数的递推公式和具体表达式,并使用3层数学归纳和纯组合的方法对其进行了证明。
#5 181818181818@2008-08-09 02:48:00
3851
回复
删除
看我的题解!http://user.qzone.qq.com/281589210/blog/1218156497