汉诺塔问题
汉诺塔问题源自印度一个古老的传说，印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱，其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：
- 每次只能移动柱子最顶端的一个圆盘；
- 每个柱子上，小圆盘永远要位于大圆盘之上；
问题分析：
假设有 n 个圆盘，三个柱子分别为 A, B, C。 那么把上面 (n - 1) 个圆盘，看成一个整体，那么可以执行以下步骤：
-
把(n-1)这个整体从 A 经由 C 移动到 B ------表达式记为：H(n-1);
-
把第 n 个圆盘从 A 移动到 C ------记为单次移动；
-
把(n-1)这个整体从 B 经由 A 移动到 C ------表达式记为：H(n-1);
数学表达式可以表示为：
代码和运行结果如下：
C 源代码：
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include <stdio.h>
//Author: wanlin_z
//用递归解决汉诺塔问题：
int hanoi(int n, char a, char b, char c)
{
static int count = 0;
if (n > 0)
{
hanoi(n-1, a, c, b);
printf("moving from %c to %c\n", a, c);
count++;
hanoi(n-1, b, a, c);
}
//printf("%d\n", count);
return count;
}
int main()
{
int n = 0;
char x = 'A';
char y = 'B';
char z = 'C';
printf("请输入圆盘数量>:");
scanf("%d", &n);
//调用函数，执行汉诺塔圆盘移动
int count1 = hanoi(n, x, y, z);
printf("count = %d\n", count1);
return 0;
}
运行结果如下：
请输入圆盘数量>:3
moving from A to C
moving from A to B
moving from C to B
moving from A to C
moving from B to A
moving from B to C
moving from A to C
count = 7
D:\C-language\c-language\Test_Project1\x64\Debug\Test_Project1.exe (进程 21256)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口.
Python 源代码：
# -*- coding:utf-8 -*-
# 汉诺问题，是一个递归问题，把（n-1）看成一个整体：f(n)=2f(n-1)+1
def hanoi(n, a, b, c):
if n > 0:
hanoi(n - 1, a, c, b)
print("moving from %s to %s" % (a, c))
hanoi(n - 1, b, a, c)
# 假设 n=3;
hanoi(3, "A", "B", "C")
C:\Users\79079\AppData\Local\Programs\Python\Python36\python.exe D:/Python源代码组/零基础7天极速入门/Python小达/自定义函数集/清华(数据结构与算法)/hanoi.py
moving from A to C
moving from A to B
moving from C to B
moving from A to C
moving from B to A
moving from B to C
moving from A to C
Process finished with exit code 0
代码和运行结果如上。小白打的代码有点菜，边学边分享，也是记录自己的学习之路。望各位路过的大佬多多指教，感激不尽。