C语言汉诺塔数列(循环版)
汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘,大梵天命令僧侣把圆盘移到另一根柱子上,并且规定:在小圆盘上不能放大圆盘,每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时,世界就会毁灭。
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, …
第 1 项为 1,表明移动 1 片圆盘的汉诺塔需 1 步;第 2 项为 3,表明移动 2 片圆盘的汉诺塔需 3 步;……,以此类推。请编写递归函数,求汉诺塔数列中任一项的值。
函数原型
double NumHanoi(int index);
说明:参数 index 为索引号(正整数),函数值为汉诺塔数列第 index 项的值。
要求:不要使用选择语句。不要调用 pow、exp 等数学函数。
裁判程序
#include <stdio.h> double NumHanoi(int index); int main() { int n; scanf("%d", &n); printf("%.15g\n", NumHanoi(n)); return 0; }
/* 你提交的代码将被嵌在这里 */
输入样例1
3
输出样例1
7
输入样例2
45
输出样例2
35184372088831
提交代码:
算法思路:该算法的思路为,通过分析题目的情况,然后可以得到的这个汉诺塔的公式为2^n - 1,对于汉诺塔的总层数。
double NumHanoi(int index) { int i = 1; double result = 1; while (i < index) { result = 2 * result + 1; i++; } return result; }
递归版
分数 10
作者 李祥
单位 湖北经济学院
汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘,大梵天命令僧侣把圆盘移到另一根柱子上,并且规定:在小圆盘上不能放大圆盘,每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时,世界就会毁灭。
请编写函数,完成移动汉诺塔的任务。
函数原型
void MoveTower(int num, char src, char dst, char trs);
说明:参数 num 为金片数,src、dst 和 trs 分别为起始柱、目的柱和过渡柱。若金片数大于 0,则函数将金片组成的汉诺塔由起始柱利用过渡柱最终搬到目的柱,否则什么也不做。
下面的程序,输入汉诺塔圆片的数量,输出移动汉诺塔的步骤。
裁判程序
`
#include <stdio.h>
void MoveTower(int num, char src, char dst, char trs);
int main()
{
int n;
char s, d, t;
scanf(“%d %c %c %c”, &n, &s, &d, &t);
MoveTower(n, s, d, t);
return 0;
}
`
/* 你提交的代码将被嵌在这里 */
输入格式
圆盘数
起始柱 目的柱 过渡柱
输出格式
移动汉诺塔的步骤
每行显示一步操作,具体格式为:
盘片号: 起始柱 -> 目的柱
其中盘片号从 1 开始由小到大顺序编号。
输入样例
3
a c b
输出样例
1: a -> c
2: a -> b
1: c -> b
3: a -> c
1: b -> a
2: b -> c
1: a -> c
提交代码
void MoveTower(int num, char src, char dst, char trs) { if(num > 0) { MoveTower(num - 1,src,trs,dst); printf("%d: %c -> %c\n",num,src,dst); MoveTower(num - 1,trs,dst,src); } }