汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
分析:
假设有三根柱子分别为A,B,C,其中A柱上有n个盘子,如果我们要把A最下面的那个盘子拿出来放到C柱上,我们需要把上面(n-1)个盘子借助C柱全部挪到B柱上,然后将A柱上最大的盘子放到C柱,最后再将B柱上的盘子放回到C柱上。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void move(char a,char b)//单独构建一个move函数,用来打印盘子的移动路径
{printf("%c-->%c\n", a, b);
}
void Hanoi(int x,char A,char B,char C)
{if (x == 1){move(A, C);}else{Hanoi(x - 1,A, C, B);//把A中1到n-1个盘子借助C挪到Bmove(A, C);//把A中剩下的第n个盘子移动到CHanoi(x - 1, B, A, C);//把B盘中1到n-1个盘子借助A移动到C中}
}
int main()
{int n = 0;scanf("%d", &n);//设置汉诺塔问题需要转移的盘子个数Hanoi(n,'A','B','C');//把n个盘子借助B挪到Creturn 0;
}