汉诺塔问题算法分析

① 汉诺塔算法问题

怎么我看起来乱七八糟的呢?
至少 C语言里面 main()函数是不可以被其他函数调用的,你那样定义main()函数个人觉得是不正确的,main()函数怎么能有返回值呢?

② 汉诺塔问题

TMD 连个问题都没

③ 汉诺塔问题算法

用递归实现：

#include <iostream.h>

void Towers(int n, char fromPeg, char auxPeg, char toPeg)
{
if (1 == n) //递归出口
{
cout << "Move Disk 1 from Peg " << fromPeg << " to Peg " << toPeg << endl;
return;
}

//把n-1个盘子从fromPeg借助toPeg移动到auxPeg
Towers(n - 1, fromPeg, toPeg, auxPeg);

//把盘子n由fromPeg直接移动到toPeg
cout << "Move Disk " << n << " from Peg " << fromPeg << " to Peg " << toPeg << endl;

//把n-1个盘子从auxPeg借助fromPeg移动到toPeg
Towers(n - 1, auxPeg, fromPeg, toPeg);
}

int main()
{
int n = 0;
cout << "Pleae input disk number:";
cin >> n;
Towers(n, 'A', 'B', 'C');

return 0;
}

④ 汉诺塔算法步骤解析

这是一个递归的过程,你要自己搞个简单例子摆一摆,再看看我的解释就明白了

hanoi(n-1, A, C, B);//将n-1个盘通过c从a移到b
printf("Move sheet %d from %c to %c\n", n, A, C);//将第n个盘从a移到c
hanoi(n-1, B, A, C);//将n-1个盘通过a从b移到c

⑤ 汉诺塔问题的递归算法流程图

关键是第一步移法，奇数层的说，3层在第一柱，后两根柱数数：123。所以，第一块应放在第二根柱，4层，第一块放第三柱。...........奇数层第一块放第二柱，偶数层第一块放第三柱。

⑥ 汉诺塔递归算法分析

我之前回答过的，http://..com/question/499530116.html?oldq=1&from=evaluateTo#reply-box-1259261416

⑦ 汉诺塔问题公式是什么

汉诺塔问题（又称河内塔问题）是根据一个传说形成的一个问题：

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须尊循上述两条规则。

问：如何移？最少要移动多少次？
一般取N=64。这样，最少需移动264-1次。即如果一秒钟能移动一块圆盘，仍将需5845.54亿年。目前按照宇宙大爆炸理论的推测，宇宙的年龄仅为137亿年。

在真实玩具中，一般N=8；这将需移动255次。如果N=10，需移动1023次。如果N=15，需移动32767次；这就是说，如果一个人从3岁到99岁，每天移动一块圆盘，他仅能移动15块。如果N=20，需移动1048575次，即超过了一百万次。
先看hanoi(1, one, two, three)的情况。这时直接将one柱上的一个盘子搬到three柱上。注意，这里one柱或three柱到底是A、B还是C并不重要，要记住的是函数第二个参数代表的柱上的一个盘被搬到第四个参数代表的柱上。为方便，将这个动作记为：
one =》three

再看hanoi(2, one, two, three)的情况。考虑到hanoi(1)的情况已经分析过了，可知这时实际上将产生三个动作，分别是：
one =》two
one =》three
two =》three
很显然，这实际上相当于将one柱上的两个盘直接搬到three柱上。

再看hanoi(3, one, two, three)的情况。分析
hanoi(2, one , three, two)
one =》three
hanoi(2, two, one, three)
即：先将one柱上的两个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的两个盘搬到three柱上。这不就等于将one柱上的三个盘直接搬到three柱上吗？

运用归纳法可知，对任意n，
hanoi(n-1, one , three, two)
one =》three
hanoi(n-1, two, one, three)
就是先将one柱上的n-1个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的n-1个盘搬到three柱上。这就是我们所需要的结果！
回答者：wuchenghua121 - 经理 四级 12-5 11:51
汉诺塔
汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

后来，这个传说就演变为汉诺塔游戏:

1.有三根杆子A,B,C。A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上

经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

此外，汉诺塔问题也是程序设计中的经典递归问题。

补充：汉诺塔的算法实现（c++）
#include <fstream>
#include <iostream>
using namespace std;

ofstream fout("out.txt");

void Move(int n,char x,char y)
{
fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
}

void Hannoi(int n,char a,char b,char c)
{
if(n==1)
Move(1,a,c);
else
{
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
}
}

int main()
{
fout<<"以下是7层汉诺塔的解法:"<<endl;
Hannoi(7,'a','b','c');
fout.close();
cout<<"输出完毕！"<<endl;
return 0;
}

C语言精简算法
/* Copyrighter by SS7E */
#include<stdio.h> /* Copyrighter by SS7E */
void hanoi(int n,char A,char B,char C) /* Copyrighter by SS7E */
{
if(n==1)
{
printf("Move disk %d from %c to %c\n",n,A,C);
}
else
{
hanoi(n-1,A,C,B); /* Copyrighter by SS7E */
printf("Move disk %d from %c to %c\n",n,A,C);
hanoi(n-1,B,A,C); /* Copyrighter by SS7E */
}
}
main() /* Copyrighter by SS7E */
{
int n;
printf("请输入数字n以解决n阶汉诺塔问题：\n");
scanf("%d",&n);
hanoi(n,'A','B','C');
}/* Copyrighter by SS7E */
回答者： Vanquisher_ - 举人 五级 12-5 13:57
parcel::::::::::
program hanoi;
functionhanoi(x:integer):longint;
begin
if x=1 then hanoi:=1;
if x=2 then hanoi:=3;
else
begin
hanoi:=2*hanoi(x-1)+1;
end;
end;

begin
read(x){第几个数 }
write(hanoi(x));
end.

思想就是：第N个就等于第n-1个乘以2+1次

⑧ 汉诺塔问题算法详细解答

#include <stdio.h>
void hanio(int n,char a,char b,char c)
{
if(n>=1)
{hanio(n-1,a,c,b);//可以理解为把a上的n-1个盘子通过c移动到b上
printf("%c--> %c\n",a,c);//然后再把a上剩下的一个盘子移动到c上
hanio(n-1,b,a,c);//再把b上的n-1个盘子通过a移动到c上，搞定，递归程序，看起来简单，理解起来稍微有点难度，调试也不容易，你用多了就明白了
}
}
int main ()
{
int n ;
printf("please input the num:\n");
scanf("%d",&n) ;
//盘子数为n，三个柱子分别为ABC
hanio ( n, 'A' , 'B' , 'C' ) ;
return 0;
}

⑨ 怎么用归纳法证明汉诺塔问题 算法设计与分析的课后习题

如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。
如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。
事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1

算法Procere HANOI(n, A, B, C) [
IF(n == 1) [
PRINT("Move sheet " n " from " A " to " C);
]
ELSE [
HANOI(n-1, A, C, B);
PRINT("Move sheet " n " from " A " to " C);
HANOI(n-1, B, A, C);
]
]

⑩ 汉诺塔问题的递归求解算法,并分析算法的时间复杂性

void Hanoi(int n, char a, char b, char c)
{
if(n==1) //只有一个盘子，直接移动
printf("move %c to %c\n", a, c);
else
{
Hanoi(n-1, a, c, b); //将n-1个盘子从a柱移动到b柱
printf("move %c to %c\n", a, c); //将最后一个盘子从a柱移动到c柱
Hanoi(n-1, b, a, c); //将n-1个盘子从b柱移动到c柱
}
}时间复杂度下限是O(2n)