1.汉诺塔问题的由来
(感谢chatgpt)汉诺塔,又称河内塔,是一种传统的益智玩具和数学问题。据说其起源可以追溯到印度古代传说中的 Brahma 寺庙,从印度传播到东南亚、中国等地区。最早的正式记载出现在 19 世纪末的法国数学家 Edouard Lucas 发表于《科学》杂志上的一篇文章中。
故事的情节大致是这样的:在 Brahma 所供奉的圆锥形塔庙里,有三根钉子,最初所有的圆盘都串在其中一根钉子上,大的在下,小的在上,形成一个由大到小的递减序列;路过此处的人们想试一下自己的本领,就开始实行“移魂换魄”的任务。用任何一根钉子作为中介,只允许在小盘子上面放大盘子,在三根钉子之间移动。目标是尽快完成把所有圆盘从初始位置移到某个其他钉子上的操作。如果能在数量较少的步骤中完成,則壓力減小,而如果得不出答案则不礼也不会武变態了!
汉诺塔问题引入后在数学界得到了广泛的关注和研究。除了其本身作为益智游戏之外,汉诺塔问题在计算复杂度、基于规则的机器学习等领域都具有重要的意义。汉诺塔问题也被用来解释人类思维能力中的归纳、递推等抽象概念,成为了教育多尚方宝剑。
画图理解:
2.汉诺塔问题的求解(关于移动步数)
图片理解:
#include <stdio.h> //汉诺塔问题(利用函数递归实现) //函数定义部分 static int count = 1; int hannuo(int n) { if (n > 1) { count = count * 2 + 1; hannuo(n - 1); } else return count; return count; } int main() { int n; printf("请输入圆盘个数:"); scanf("%d",&n); int step = hannuo(n); printf("完成步骤为:%d步\n", step); return 0; }
3.如何打印移动路径
//汉诺塔移动步骤 //定义move函数,来打印路径 void move(char s, char d) { printf("%c -> %c \n", s, d); } //pos1:起始位置 //pos2:中转位置 //pos3:终点位置 void hannuo(int n, char pos1, char pos2, char pos3) { if (1 == n)//如果只有一个盘子,直接移动即可 { move(pos1, pos3); } else//多于一个盘子,用大事化小的思维 { hannuo(n - 1, pos1, pos3, pos2);//先将最大盘子之上的n-1个盘子经过c,转移到b上 move(pos1, pos3);//再将最大的盘子转移到c, hannuo(n - 1, pos2, pos1, pos3);//最后将b上的n-1个盘子经a的中转转移到c上 } } int main() { int n; printf("请输入盘子的个数n:"); scanf("%d", &n); //定义三个盘子分别为'A', 'B', 'C' hannuo(n, 'A', 'B', 'C'); return 0; }