我要招人

去企业版

首页 > 试题广场 >

4个圆盘的Hanoi塔,总的移动次数为()

[单选题]

```
7
```
```
8
```
```
15
```
```
16
```

查看正确选项

Ian

答案为C。设f(n)为n个圆盘的hanoi塔总的移动次数，其递推方程为f(n)=f(n-1)+1+ f(n-1)=2*f(n-1)+1。理解就是先把上面n-1个圆盘移到第二个柱子上(共f(n-1)步），再把最后一个圆盘移到第三个柱子(共1步），再把第二柱子上的圆盘移动到第三个柱子上（共f(n-1)步）。而f（1）=1；于是f(2)=3,f(3)=7,f(4)=15。故答案为C。进一步，根据递推方程其实可以得出f(n) = 2^n - 1。

编辑于 2021-01-12 09:43:53 回复(3)

牛牛12315

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

设移动n个盘子的汉诺塔问题需要g(n)次移动操作来完成。由展示移动过程算法可知g(n)应是三部分之和。
(1) 将n个盘上面的n-1个盘子借助C桩从A桩移到B桩上，需g(n-1)次移动；
(2) 然后将A桩上第n个盘子移到C桩上（1次）；
(3) 最后，将B桩上的n-1个盘子借助A桩移到C桩上，需g(n-1)次。
因而有递归关系：
g(n)=2*g(n-1)+1
初始条件(递归出口)：
g(1)=1
即 1、3、7、15、31。。。即g(n) = 2^n -1

发表于 2015-09-05 19:26:54 回复(0)

tthhee

f(1) = 1;

f(2) = 3;

f(n) = 2*f(n-1)+1;

发表于 2016-04-19 20:09:55 回复(0)

恶寒轻轻

汉诺塔问题，还是要把公式记住：f(x)=2^x-1

编辑于 2021-11-21 12:29:52 回复(0)

菜鸡准备转岗

#include<iostream>
using namespace std;
int move(int n, char a, char b, char c){
	int mm=0, pp=0; 
	if(n==1){
		cout<<"盘"<<n<<" 从"<<a<<"移动到"<<c<<endl; 
		return 1;
	}
	else{
		mm = move(n-1, a, c, b);
		cout<<"盘"<<n<<" 从"<<a<<"移动到"<<c<<endl; 
		mm+=1;
		pp = move(n-1, b, a, c);
	}
	return mm+pp;
	
}
int main(){
	int n=4;
	cout<<"共移动了"<<move(4, 'a', 'b', 'c')<<endl;
}

发表于 2019-08-14 11:00:17 回复(0)

★최강※단장

假设1个 1次

假设2个 3次

假设3个 7次

由此推导2ⁿ-1

发表于 2016-09-17 17:38:19 回复(0)

请叫我帅帅

写个小程序啦~

#include<stdio.h>
void hanio(int n,char start,char wait,char end);
int main()
{
    int n;
    char ch1='a',ch2='b',ch3='c';
    scanf("%d",&n);
    hanio(n,ch1,ch2,ch3);
    return 0;
}
void hanio(int n,char start,char wait,char end)
{
    if(n==1)
    {
        printf("%d from %c move to %c\n",n,start,end);
    }
    else
    {
        hanio(n-1,start,end,wait);
        printf("%d from %c move to %c\n",n,start,end);
        hanio(n-1,wait,start,end);
    }
}

发表于 2018-03-29 17:21:54 回复(0)

牛客725307966号

计算题，mark，抄答案

发表于 2022-04-11 21:38:33 回复(0)

wanlanwalan

汉诺塔、梵塔

规则是：一次移动一个盘；无论何时，小盘在上，大盘在下。

在游戏中，总共有n个金属盘片的塔叫做n阶汉诺塔，若要完成n阶汉诺塔，则最少要移动2^n -1次

发表于 2017-03-29 11:22:40 回复(0)

烬天玉藻前

汉诺塔问题是一个经典的数学难题，由 3 个柱子和多个半径不等的圆盘构成。

汉诺塔问题指的是：将一个柱子中的所有圆盘移动到另一个柱子，移动过程需遵守以下规则：

每次只能移动一个圆盘，而且只能移动某个柱子上最顶部的圆盘；
移动过程中，必须保证每个柱子上的大圆盘都位于小圆盘的下面。

至少需要移动2^n - 1次(n是圆盘数目)。

编辑于 2023-02-13 23:17:13 回复(0)

眼眸里的那抹朝阳

递归执行

package face1;/**

汉诺塔

@author Administrator
/
public class Hanoi {

public static int i=0;
public static void HanoiTower(int n,char A,char B,char C){

 if(n
     throw new IllegalAccessError("n必须小于1!");
 }
 if(n==1) {
     System.out.println(A+"->"+B);
 }else{
      HanoiTower(n-1, A, C, B); //将除过最大的盘子n个盘子，从A通过B移动到C
      System.out.println(A+"->"+B);//将最大的盘子从A移动到B
      HanoiTower(n-1, C, B, A);//将出去最大的盘子的n-1个盘子从C通过A移动到B
 }

}

public static void main(String[] args) {

 HanoiTower(4, 'A','B', 'C');
 System.out.println(i);

}
}

编辑于 2017-09-17 21:13:23 回复(0)

小郑同学ye

公式n^2-1

发表于 2023-11-14 11:47:07 回复(0)

腰马合一小垃圾

2^n - 1

发表于 2023-06-22 16:29:58 回复(0)

mitochondria

汉诺塔移动次数计算公式：y = 2^x - 1

发表于 2022-09-20 11:12:52 回复(0)

倾城一号线

根据规律得出移动次数=2^n次方-1

发表于 2022-09-05 16:54:59 回复(0)

秋越海

2的N次方减1

发表于 2022-06-08 12:50:11 回复(0)

路嘿

关于汉诺塔，就是有三个柱子，第一个柱子上是三个盘子，这些盘子从上至下是小，中，大，让盘子在这三个柱子上可以进行转移，要求是不能让大盘子落在小盘子上，结果是把这些盘子按照顺序转移到另一个柱子上

编辑于 2022-04-01 19:32:50 回复(0)

main方法栈帧

下面记录了第几次移动和移动到该位置的方块标号是多少

发表于 2021-11-20 21:28:23 回复(0)

脆莓啤酒

汉诺塔问题 2的n次方-1

发表于 2020-10-29 17:13:12 回复(0)

东河西岸

汉诺塔2^n-1

发表于 2020-08-10 08:57:13 回复(0)

提交观点

问题信息

栈递归

难度：

31条回答 2138收藏 22792浏览

4个圆盘的Hanoi塔,总的移动次数为()

问题信息

热门推荐

相关试题