汉诺塔IV - 博客频道 - CSDN.NET
Rookie的博客
分类：模拟递推
还记得汉诺塔III吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。
输入数据的第一行是一个数据T，表示有T组数据。
每组数据有一个正整数n(1 &= n &= 20)，表示有n个盘子。
对于每组输入数据，最少需要的摆放次数。
先将上面n-1个移至相邻
将第n个盘子移至最后一个
再将n-1个移至相邻。
#include &stdio.h&
#define LL long long
const int maxn = 25;
LL ans[maxn], sum[maxn];
int main ( )
ans[1] = sum[1] = 1;
for ( int i = 2; i & i ++ )
ans[i] = ans[i-1]*3;
//保存移至相邻柱子的次数
sum[i] = sum[i-1]+ans[i];
//统计总次数
scanf ( &%d&, &T );
while ( T -- )
scanf ( &%d&, &n );
printf ( &%lld\n&, sum[n-1]*2+2 );
//将前n-1移至相邻柱子,将第n个移至最后一根需要2次,然后再移至相邻柱子
排名：千里之外
（4）（17）（16）（12）（30）（18）（9）（8）（19）（7）（6）（1）（2）（3）（11）（5）（5）（1）（4）（8）（9）（1）（1）（4）（2）（1）（2）（4）（2）（3）（2）（3）（4）（6）（2）（1）温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(2206)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'《汉诺塔问题（递归）》',
blogAbstract:'&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &汉诺塔问题（递归）\r\n传说婆罗门庙里有一个塔台，台上有3根用钻石做成的柱子a，b，c。在a柱上放着64个金盘，每个都比下面的略小一点。把a柱上的金盘全部移到c柱上的那一天就是世界的末日。移动必须遵守如下规则：一次只能移动一个金盘，移动过程中大盘不能放在小盘上面。这种移动需要进行2的64次幂减1，如果每秒移动一次，需要5000多亿年。\r\n用递归思想解决汉诺塔问题是很方便的：（1）先将n-1个盘子从a柱移动到b柱，（2）然后把最大的盘子从a柱移动到c柱，（3）再把n-1个盘子从b柱移动到c柱。（1）、（3）均是n-1阶的汉诺塔问题。（2）是递归的终止条件，是一个能直接求解的最小子问题。把（1）（3）进一步分解下去，最后n阶汉诺塔问题可以被分解成若干个只需要移动一个盘子的能直接求解的子问题，使得整个问题得到解决。\r\n',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:2,
publishTime:4,
permalink:'blog/static/',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}Description
还记得汉诺塔III吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。
输入数据的第一行是一个数据T，表示有T组数据。
每组数据有一个正整数n(1 &= n &= 20)，表示有n个盘子。
对于每组输入数据，最少需要的摆放次数。
Sample Input
由汉诺塔3知从左往右的递推关系式为F[n]=F[n-1]*3+2,而此题允许最大盘在上记其步骤数为f[n]，则f[n]=F[n-1]+2。原理很简单，将上面n-1个盘看为整体先将其移到B上再将
第n个盘移到B上再将其移到C上，最后再将n-1个移到C上，故可得出上面的关系式，代码如下:
#include &iostream&
#include &math.h&
int main()
long long F[21],f[21],T,n;
F[1]=2,f[1]=2;
for(int i=2;i&=20;i++)
F[i]=3*F[i-1]+2;
for(int i=2;i&=20;i++)
f[i]=F[i-1]+2;
while(T--) {cin&&n;cout &&f[n]&&}
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3942次
排名：千里之外
原创：16篇
(8)(3)(8)(1)【图文】汉诺塔问题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
汉诺塔问题
上传于||暂无简介
大小：3.61MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢}