用户名：sikeIT
访问量：2667
注册日期：
阅读量：1297
阅读量：3317
阅读量：452741
阅读量：1137191
51CTO推荐博文
问题：汉诺塔递归算法时间复杂度算法如下：&&&&& & 解释：size表示汉诺塔的规模，startStack表示汉诺塔起始，endStack 表示完成，midStack表示辅助&&&&&&&&&&&&&&def Towers(size,startStack,endStack,midStack):& &&&&&&&&&&&&& if size == 1:& & & & &&&&&&&&&&&&print 'Move disk from ', firstStack, 'to ', endStack& & &&&&&&&&&&&&else:& & & & &&&&&&&&&&&&Towers(size-1,firstStack,midStack,endStack)& & & & &&&&&&&&&&&&Towers(1,firstStack,endStack,midStack)& & & & &&&&&&&&&&&&Towers(size-1,midStack,endStack,firstStack)分析：问题规模设置为n，T（n）为问题规模所需步骤，&&&&& T（n）=1+T(1)+2T（n-1）//规模为n-1时要经过两次，所以为2T（n-1）&&&&&&&&&&&&=1+2+2T(n-1)&&&&&//当规模为1时需要两步，因此为T（1）=2&&&&&&&&&&&&=3+2[3+2T（n-2)] //规模为n-2时，重复上述操作&&&&&&&&&&&&=9+4T（n-2）& &&&&&&&&&&&&&=9+4[3+2T(n-3)]&&&&&&&&&&&&=21+8T(n-3)&&&&&&&&&&&&......&&&&&&&&&&&&&&&&=C+2^kT(n-k)当n-k=1时，得到k=n-1，&&&&& T（n）=C+2^(n-1)T(1)//其中T（1）=2&&&&& T（n）=C+2^n综上：汉诺塔时间复杂度为O(2^n) & &注：算法采用Python语言编写本文出自 “” 博客，请务必保留此出处
了这篇文章
类别：┆阅读(0)┆评论(0)如何理解汉诺塔的递归？ - 知乎360被浏览70078分享邀请回答04 条评论分享收藏感谢收起最裸的汉诺塔：
第一步：把n-1个盘子移到B柱
第二步：把第n个柱子移到C柱
第三步：把n-1个盘子移到C盘
第一步和第三步是一样的，如果只需要求最少的步数，可以不管中间步骤，用递推直接写出即可
for(int i=2;i&=n;i++)
& & a[i]=2*a[i-1]+1;
最裸的弄懂当然是远远不够的，现在我们来看一些变形
输入n，m，问初始有n个盘子，问第m次移动的盘子号
咋看很麻烦，其实也是很简单的啦！
比如有4个盘子，我要看第4步的盘子。如果我3个盘子都移到目的柱，那一共需要7步，如果把2个盘子都移到目的柱那一共需要3步，所以第4步移动的盘子一定在前3个盘子中。
而我们可以利用这种思想不断递推/递归也行，直到正好等于把某些盘子移动到目的柱。
#include &iostream&
#include&stdio.h&
#include&algorithm&
ll n,m,a[64],b[64];
void inial()
a[1]=1;b[0]=1;b[1]=2;
for(int i=2;i&64;i++)
a[i]=a[i-1]*2+1;
b[i]=a[i]+1;
int sovle()
if(m==a[63])
while(m&0)
while(t&63)
if(m&b[t])
if(m==b[t])
return t+1;
m-=b[t-1];
int main()
while(cin&&n&&m&&n&&m)
cout&&sovle()&&
下面的题目比上一个更加进了一步
输入n，m问n个盘子，第m步移动的是哪个盘子，而且输出从哪个盘子移动到哪个盘子（比上一题进了一步）
大家想想。如果m步正好是k个盘子移动到目的柱，那么这时候肯定把1号盘由所在柱，移动k个盘所在的目的柱。1的所在柱就是我们递归函数中的所在柱，那么目的柱呢？大家想想我最开始讲的最裸的三部，要移动n个盘就把n-1个盘移动到B，那对于n-1个盘来说，中间B盘是目的柱，C是中间柱，那么对于n-2个盘来说目的柱是C柱，中间柱石B柱，那么判断k个盘的目的柱是哪个直接判断他与n的差的奇偶性即可。
#include &iostream&
#include&stdio.h&
#include&math.h&
#include&algorithm&
ll a[64],m;
void inal()
for(int i=2;i&=63;i++)
a[i]=2*a[i-1]+1;
void sovle(int s,int t,int z,int n)
{//cout&&&----------- &&&s&&& &&&t&&& &&&z&&& &&&n&&
while(k&64&&m-a[k]&0)
int d=(n-k)&1;
if(d==1)//1到k在第z上
cout&&1&&& &&&s&&& &&&z&&
cout&&k+1&&& &&&s&&& &&&t&&
sovle(z,t,s,k);
else//1到k在t上
cout&&1&&& &&&s&&& &&&t&&
cout&&k+1&&& &&&s&&& &&&z&&
sovle(t,z,s,k);
int main()
scanf(&%d&,&t);
while(t--)
scanf(&%d%I64d&,&n,&m);
sovle(1,3,2,n);
接下来咱们再进一步，第m步的时候输出三个柱子上的盘子的编号
如果直接看这题是不是会被吓到，但是有前面题目的积累，这题也只是进了一步而已。eg：4个盘子，第5步，3个盘子移到目的柱，则需要7步，2个盘子移到目的柱需要3步，
则这里可以判定第4个盘子肯定在原来的柱子上不动，那第3个盘子会移到中间柱上。写个递归函数是不是很方便呢？如何保存每个柱子上的盘子号呢？由于递归的性质，会大的盘子先确定，柱子上编号较小的盘子可能是在下一层递归中确定。输出是先输出大的再输出小的，先进先出，不就是队列么。
#include &iostream&
#include&stdio.h&
#include&math.h&
#include&algorithm&
#include&cstring&
#include&queue&
ll a[64],m;
int t,n,len[4];
queue&int& qu[4];
void inal()
for(int i=2;i&=63;i++)
a[i]=2*a[i-1]+1;
void sovle(int s,int t,int z,int n)
while(k&64&&m-a[k]&0)
for(int i=n;i&k+1;i--)
qu[s].push(i);
int d=(n-k)&1;
swap(z,t);
for(int i=k;i&=1;i--)
qu[z].push(i);
qu[s].push(k+1);
qu[t].push(k+1);
for(int i=k;i&=1;i--)
qu[z].push(i);
sovle(z,t,s,k);
int main()
scanf(&%d&,&t);
while(t--)
memset(len,0,sizeof(len));
scanf(&%d%I64d&,&n,&m);
sovle(1,3,2,n);
for(int i=1;i&=3;i++)
printf(&%d &,len[i]);
printf(&%d&,qu[i].front());
qu[i].pop();
while(!qu[i].empty())
printf(& %d&,qu[i].front());
qu[i].pop();
printf(&\n&);
问题把n个盘子移到目的柱，问第k个盘子在这过程中一共移动了多少次。
看上去很复杂的样子，但仔细想一想，第n个盘子只需要1次，第n-1个盘子只需要移动2次，你可以这么递归下去，当然有感觉的也可以直接找到规律，不说了，上代码
#include &iostream&
#include&stdio.h&
#include&math.h&
#include&algorithm&
using namespace std;
typedef long long ll;
int t,n,k;
int main()
scanf(&%d&,&t);
while(t--)
scanf(&%d%d&,&n,&k);
ll ans=pow(2,n-k);
printf(&%I64d\n&,ans);
问n个盘子，移动到目的柱的过程中（不考虑最优的情况）会产生序列的总数，low题，每个哦案子不就可以在三个柱子上么，3的阶层就行了
#include &iostream&
#include&stdio.h&
#include&algorithm&
#include&math.h&
void inial()
for(int i=1;i&=30;i++)
a[i]=3*a[i-1];
int main()
scanf(&%d&,&t);
while(t--)
scanf(&%d&,&k);
printf(&%I64d\n&,a[k]);
上面两题算是休息，现在来看看更加深入，更加有趣的汉诺塔，hdu1997，自己看题意啊
这题是不是一看到就把人吓到了，对于这种问题，肯定是递归的啦！现在的问题是递归什么，如果你要递归每一步，肯定会爆掉。我们要弄清楚我们可以确定什么，由于最裸的公式，我们可以确定，n在A或C，如果n确定了，那么我们需要考虑n-1。如果n在A，那还处于最裸的公式中的第一步，那么n-1只有在A或B，目的柱是B，起点是A，中间点是C。如果n到C，那一定经历过了第一步，那么n-1要么在C要么在B，起点是B，中间点是A，目的点是C
#include &iostream&
#include&stdio.h&
#include&algorithm&
const int M=70;
int t,n,len[4],a[4][M],no[4],f=-1;
void input()
scanf(&%d&,&n);
for(int i=0;i&3;i++)
scanf(&%d&,&len[i]);
for(int j=0;j&len[i];j++)
scanf(&%d&,&a[i][j]);
void dfs(int A,int B,int C,int n)
if(a[A][no[A]]==n)
no[A]++;//cout&&n&&& -------
dfs(A,C,B,n-1);
if(a[C][no[C]]==n)
no[C]++;//cout&&n&&& -------
dfs(B,A,C,n-1);
int main()
scanf(&%d&,&t);
while(t--)
no[0]=no[1]=no[2]=0;
dfs(0,1,2,n);//cout&&f&&
puts(&true&);
puts(&false&);
我们做一些改变了规则的汉诺塔
hdu2064盘子不能直接从A到C，只能先由B在到C。
学会着递推公式，找不到的话，可以先模拟少数几个盘子
n-1个盘子先要移到C，n移到B，n-1个盘子移到A，n移到C，n-1个盘子移到C
#include&iostream&
#include&stdio.h&
void Inial()
for(int i=2;i&36;i++)
f[i]=3*f[i-1]+2;
int main()
while(scanf(&%d&,&n)!=EOF)
cout&&f[n]&&
规则在hdu2064的基础上再变一下，最大的盘可以放在小的盘子的上面（最上面）
跟上题结合一下，n-1用上题的规则移到B，n移到B，再移到C，再把n-1个移到C
#include&iostream&
#include&stdio.h&
ll a[37],b[37];
void Inial()
for(int i=2;i&=20;i++)
a[i]=3*a[i-1]+2;
for(int i=2;i&=20;i++)
b[i]=b[i-1]+a[i-1]+1;
int main()
int n,m;cin&&n;
for(int i=0;i&n;i++)
cout&&b[m-1]*2+2&&
规则又做了一次改变，这次有了四根柱子，这题的难点在于惯性思维（惯性思维害死人啊！！！），大家都用递推来做，其实是里面柔和了dp。大家自己感受下来自世界的深深的恶意。
#include &iostream&
#include&stdio.h&
#include&algorithm&
double a[65],b[65];
void inial()
for(int i=2;i&65;i++)
b[i]=2*b[i-1]+1;
for(int i=3;i&=64;i++)
a[i]=b[i];
for(int j=1;j&i;j++)
a[i]=min(2*a[j]+b[i-j],a[i]);
int main()
while(scanf(&%d&,&n)!=EOF)
cout&&a[n]&&
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：10547次
排名：千里之外
原创：43篇
评论：22条
(3)(6)(2)(1)(2)(8)(16)(3)(1)(1)工具类服务
编辑部专用服务
作者专用服务
图解方式解析汉诺塔递归算法的教学实践
该文对递归算法的实质进行了探讨。以汉诺塔问题为例，提出一种图解的方式，直观地展示了递归算法的具体执行过程，有助于初学者对递归思想的深入理解。
作者单位：
山东省泰安第一中学,山东泰安,271000
年，卷(期)：
机标分类号：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社