博客

题目

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



###　　输入盘子的数量n，求多少步能搬完。


样例输入

3

样例输出

7

//C语言求移动次数的递归函数

include<stdio.h>
int h(int m)
{
	int s;
	if(m==1)      // 确定初始条件
		s=1;
	else
		s=2*h(m-1)+1;
	return s;
}
int main()
{   
	int n;
	scanf("%d",&n);
	printf("%ld",h(n));
}

移动3个盘子的过程：

A → C

A → B

C → B

A → C

B → A

B → C

A → C

总共移动了7次

解析：


1个圆盘的时候 2的1次方减1　　　　　2个圆盘的时候 2的2次方减1

3个圆盘的时候 2的3次方减1　　　　　4个圆盘的时候 2的4次方减1

5个圆盘的时候 2的5次方减1

…………


n个圆盘的时候 2的n次方减1