汉诺塔1到9最快分别是几次？ 可以告诉我计算方法吗？

汉诺塔有世界纪录吗？如果有的话，各层分别是多少？~

汉诺塔是一个迭代问题，我们先假设x层汉诺塔从第一根柱子移动到最后一根柱子（目标柱子）的最快次数是f(x)次显然f(1)=1f(2)=3然后看3层的，我们可以把整个过程分解为三个部分一，把第一第二层移动到中间的柱子（过渡柱子），最快f(2)步二，把第三层移动到最后一根柱子（目标柱子），最快1步三，把刚才移动到中间柱子的第一第二层移动到最后一根柱子，最快f(2)步所以f(3)=f(2)+1+f(2)=7然后以此类推f(4)=f(3)+1+f(3)=15f(5)=f(4)+1+f(4)=31f(6)=f(5)+1+f(5)=63f(7)=f(6)+1+f(6)=127f(8)=f(7)+1+f(7)=255f(9)=f(8)+1+f(8)=511PS.如果学习过数列的话，这个其实可以得到更为一般的递推公式f(x+1)=2*f(x)+1再进一步，可以得到通项公式为f(x)=2^x-1

#include
int main()
{
int n;
printf("请输入汉诺塔的金片数: ");
scanf("%d",&n);
void hanoi(int n, int a, int b, int c, int &step);
int step = 0;
hanoi(n,1,2,3, step);
printf("移动了%d次
", step);
return 0;
}


void hanoi(int n, int a, int b, int c, int &step)
{
if (n==0)
return;
if (n==1)
{
printf("%d -> %d

",a,c);
step++;
}
else
{
hanoi(n-1,a,c,b, step);
printf("%d -> %d

",a,c);
step++;
hanoi(n-1,b,a,c, step);
}
}

1层：1次

2层：3次

3层：7次

4层：15次

5层：31次

6层：63次

7层：127次

8层：255次

9层：511次

计算公式：f(x)=2^x-1 

扩展资料

计算公式推导过程如下：

假设有n个圆盘，移动次数为f(n),根据经验，f(1)=1,f(2)=3

以3层为例，进行推导。可把整个过程分成三步，其中三个圆盘分别用A、B、C、代替且A的半径<B的半径<C的半径

1、把A、B移到中间的柱子，需要f(2)步

2、把C移动到第三根柱子，需要1步

3、把A、B再移动到第三根柱子，需要f(2)步

所以f(3)=f(2)+1+f(2)=7

同理，当圆盘数量为4时，三个步骤分别需要f(3)步、1步、f(3)步，即f(4)=f(3)+1+f(3)=15

由此可得递推公式：f(x+1)=2*f(x)+1

进一步可以通项公式：f(x)=2^x-1

参考资料来源：百度百科-汉诺塔

汉诺塔是一个迭代问题，我们先假设x层汉诺塔从第一根柱子移动到最后一根柱子（目标柱子）的最快次数是f(x)次
显然f(1)=1
f(2)=3
然后看3层的，我们可以把整个过程分解为三个部分
一，把第一第二层移动到中间的柱子（过渡柱子），最快f(2)步
二，把第三层移动到最后一根柱子（目标柱子），最快1步
三，把刚才移动到中间柱子的第一第二层移动到最后一根柱子，最快f(2)步
所以f(3)=f(2)+1+f(2)=7
然后以此类推
f(4)=f(3)+1+f(3)=15
f(5)=f(4)+1+f(4)=31
f(6)=f(5)+1+f(5)=63
f(7)=f(6)+1+f(6)=127
f(8)=f(7)+1+f(7)=255
f(9)=f(8)+1+f(8)=511

PS.如果学习过数列的话，这个其实可以得到更为一般的递推公式
f(x+1)=2*f(x)+1
再进一步，可以得到通项公式为
f(x)=2^x-1

N根＝2的N次方－1次

七层汉诺塔共要:
127步

---

云溪区15032476630： 在编写C语言程序求解汉诺塔问题时怎样表示每一步是第几步? - ？
陈于克泽： 可以设置一个全局变量K并初始化为0,然后在输出时,增加一项输出为++k

云溪区15032476630： 如图,汉诺塔问题是指有3根杆子A.B.C,B杆上有若干碟子,把所有碟子从B杆移到C杆上,每次只能移动一个 - ？
陈于克泽： 设h(n)是把n个碟子从B柱移到C柱过程中移动碟子之最少次数. 当n=1时,h(1)=1;n=2时,当n=2时,从B杆移到C杆上分3步,即B→A,B→C,A→C,有三种方法,即h(2)=3,当n=3时,从B杆移到C杆上分七步,即B→C,B→A,C→A,B→C,A→B,A→C,B→C,有七种方法,即h(3)=7;数列{h(n)}的通项公式为h(n)=2n-1,得h(4)=15. 故选B.

云溪区15032476630： (急)麻烦各为大虾:如何用Java编写汉诺塔排行榜,并且编写一个打印按钮,将排行榜打印出来,谢谢!!! - ？
陈于克泽： 求汉诺塔N个盘子须几次移动时得到了下面的递推公式: a[1] = 1; a[n] = a[n-1] * 2 + 1; 请教通项公式? a[1] = 1; a[n] = a[n-1] * 2 + 1; 可得a[i]= 2^i-1; 证明,采用数学归纳法: 1、猜想a[i]= 2^i-1 2、当i=1时,显然成立. 3、假设i=k时成立,即 ...

云溪区15032476630： 简单汉诺塔问题汉诺塔问题是指有3根杆子A、B、C. B杆上有若干碟子,把所有碟子从B杆移到A杆上,每次只能移动一个碟子,大的碟子不能叠在小的碟... - ？
陈于克泽：[答案] 把1,2移到C杆违反了规则:大的碟子2不能叠在小的碟子1上面把1移到A,2移到C,1移到C,3移到A,1移到B,2移到A,1再移到A

云溪区15032476630： 汉诺塔,给你任意一种合法状态,你能计算出从当前到把所有的金片移动到第三个针上的最小步数? - ？
陈于克泽： int hanio(int a,int b,int c,int n,int *result) //a,b,c 分别代表3根针,n是金片数//result是个长度为n的数组,第一位表示最小的金片,第二位表示次小的金片,...最后一位表示最大的数组.//数组每个位上的值为a或b或c,表示该金片在哪个针上.显然...

云溪区15032476630： 设计一个梵塔(又称汉诺塔)问题的求解程序 - ？
陈于克泽： #include ＂stdio.h＂ void move(int n, int x, int y, int z) {if (n == 1) printf(＂%c-->%c\n＂, x, z);else{move(n - 1, x, z, y);printf(＂%c-->%c\n＂, x, z);move(n - 1, y, x, z);} } int main() {move(7, 'a', 'b', 'c');getchar(); }

云溪区15032476630： 按规则移动9层的汉诺塔最少需要多少步 - ？
陈于克泽：[答案] n层汉诺塔最少需要移动 2^n - 1 步 按照公式,9层需要 2^9 - 1 = 511步

云溪区15032476630： 汉诺塔有N个塔身,只有左边第一塔上有上小下大的M个圆盘,移动一次只能是一盘且大盘不能在小盘上. - ？
陈于克泽： (1)将上面(n-1)个从左边移到中间,(2)将第n个从左边移到右边(3)将上面(n-1)个从中间移到右边 这样就把移动N个的任务,转化成移动两次(n-1)个和移动一次第N个的任务,而移动(n-1)个需要移动两次(n-20个和移动一次第(n-1)个,移动(n-2)个需要移动两次(n-3)个和移动一次第(n-2)个——如此继续,直到转化为移动一个的情形,根据这个过程,可得递推公式 a1=1 an=2an-1+1(n>1)[(n-1)是下标,(n)也是下标]

云溪区15032476630： 5层汉诺塔游戏31步怎么移到另一个柱子上? - ？
陈于克泽： 5层汉诺来塔游戏弄好四层后,先把上面的四个借助第三根柱子移到第二根柱子上,再把剩下的一个移到第三根柱源子上,最后借助第一根柱子将第二根柱子上的移到第三根柱子上去.1. 汉诺塔,又称河内塔,是一款WP7平台上源于印度一个古老传说的益智类游戏. 2. 汉诺塔:传说上帝创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着64片黄金圆盘.上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘.

云溪区15032476630： 若何计算汉诺塔移动的最少次数?就是我们平时玩的那个,有三条柱子,中间的柱子上穿着N(N为正整数)各碟子碟子由小到大从上到下排列,要把柱子上所有... - ？
陈于克泽：[答案] 假如说有一个盘子的话,只需挪动一步; 假如说有n个盘子要挪An步,那么有n+1个盘子可以先通过An步把上面的n个盘子挪到第三个柱子上,再挪最大的盘子,最后把n个盘子挪到大的上面,共2An+1步,所以A(n+1)=2An+1 这样计算下来An=2^n-1...