汉诺塔移动路线和移动次数问题

题目

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

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

3

样例输出

7

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

include
int h(int m)
{int s;if(m==1)      // 确定初始条件s=1;elses=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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！