当前位置:网站首页>汉诺塔问题思路的证明
汉诺塔问题思路的证明
2022-07-05 11:25:00 【炎黄子孙__】
前言
问题描述:在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。
问题分析
其实答案的思路很简单:
- 设A上有n个圆盘
- 如果n=1,就直接将 A->C ,Move( A, C);
- 如果是其他情况
- 先将前 A 上的 n-1 个圆盘移动到 B 上,Hanoi(n - 1, A, C, B)
- 再将 A 上的最后一个圆盘移动到 C上,Move(A, C)
- 最后将 B 上的 n-1 个圆盘移动的 C 上,Hanoi(n - 1, B, A, C)
但为什么这样可行?这个比较让人费解。这里我给大家提供一个思路:利用数学归纳法。
证:
假设 f(n) 操作代表把 n 个圆盘从 A 杆移动到 C 杆
注意,将 n 个圆盘无论是进行 A->C、B->C、A->B、C->B,B->A、C->A,这几个操作是完全等价的
首先,f(1) 操作一定可行
现假设 f(n) 操作可行,则 f(n+1) 操作代表要把 n+1 个圆盘从 A 杆移动到 C 杆。
因为 f(n) 操作可行,所以可以把 n 个圆盘从 A 杆移动到 B 杆,将 A 杆剩余的最后一个圆盘直接放到 C 杆。
然后还是因为 f(n) 可行,所以可以直接把 B 杆的 n 个圆盘移动到 C 杆
由此可知 f(n+1) 的操作可行。
得证:当 n∈{1,2,3,…} 时, f(n) 操作可行
下面是C语言版完整的案例,P121_6 代表题号,这个代码是我刷题的时候写的。起始真正的操作只有 P121_6 这一个函数,其他函数都是用于输出相关信息的,方便我们观察究竟发生了什么。
typedef struct {
int *A;
int *B;
int *C;
int top[3];
}s_Hannoi,*p_hannoi;
// 汉诺塔堆栈初始化
void P121_6_init(s_Hannoi& h, int n)
{
int i = n-1;
h.A = (int*)malloc(sizeof(int) * n);
h.B = (int*)malloc(sizeof(int) * n);
h.C = (int*)malloc(sizeof(int) * n);
h.top[0] = i;
h.top[1] = -1;
h.top[2] = -1;
for (;i >= 0;i--) {
h.A[i] = i;
}
}
void P121_6_Move(s_Hannoi& h,char out,char in)
{
int temp = -1,i,j;
printf("%c->%c:\n", out, in);
switch (out) {
case 'A':
temp = h.A[h.top[0]];
--h.top[0];
break;
case 'B':
temp = h.B[h.top[1]];
--h.top[1];
break;
case 'C':
temp = h.C[h.top[2]];
--h.top[2];
break;
}
switch (in) {
case 'A':
++h.top[0];
h.A[h.top[0]] = temp;
break;
case 'B':
++h.top[1];
h.B[h.top[1]] = temp;;
break;
case 'C':
++h.top[2];
h.C[h.top[2]] = temp;
break;
}
// 打印当前结构
printf("\tA:");
for (i = 0;i < h.top[0]+1;i++) {
printf("%d,", h.A[i]);
}
printf("\n\tB:");
for (i = 0;i < h.top[1]+1;i++) {
printf("%d,", h.B[i]);
}
printf("\n\tC:");
for (i = 0;i < h.top[2]+1;i++) {
printf("%d,", h.C[i]);
}
printf("\n");
}
// 汉诺塔问题
void P121_6(s_Hannoi& h,int n,char A,char B,char C)
{
if (n == 1) {
P121_6_Move(h, A, C);
}
else {
P121_6(h, n - 1, A, C, B);
P121_6_Move(h, A, C);
P121_6(h, n - 1, B, A, C);
}
}
int main()
{
printf("***********************\n");
s_Hannoi h;
P121_6_init(h, 6);
P121_6(h, 6, 'A', 'B', 'C');
}
边栏推荐
- 如何让全彩LED显示屏更加节能环保
- AUTOCAD——遮罩命令、如何使用CAD对图纸进行局部放大
- Codeforces Round #804 (Div. 2)
- 【Oracle】使用DataGrip连接Oracle数据库
- Mysql统计技巧:ON DUPLICATE KEY UPDATE用法
- C#实现WinForm DataGridView控件支持叠加数据绑定
- The ninth Operation Committee meeting of dragon lizard community was successfully held
- OneForAll安装使用
- How did the situation that NFT trading market mainly uses eth standard for trading come into being?
- [advertising system] parameter server distributed training
猜你喜欢
How to introduce devsecops into enterprises?
Wechat nucleic acid detection appointment applet system graduation design completion (7) Interim inspection report
2022 mobile crane driver examination question bank and simulation examination
About the use of Vray 5.2 (self research notes)
R3live series learning (IV) r2live source code reading (2)
Characteristics and electrical parameters of DDR4
OneForAll安装使用
Modulenotfounderror: no module named 'scratch' ultimate solution
Question bank and answers of special operation certificate examination for main principals of hazardous chemical business units in 2022
修复动漫1K变8K
随机推荐
Oneforall installation and use
deepfake教程
Detailed explanation of DDR4 hardware schematic design
2022 Pengcheng cup Web
Advanced technology management - what is the physical, mental and mental strength of managers
Go language learning notes - analyze the first program
IPv6与IPv4的区别 网信办等三部推进IPv6规模部署
7.2每日学习4
[JS learning notes 54] BFC mode
[first release in the whole network] (tips for big tables) sometimes it takes only 1 minute for 2 hours of SQL operation
Risc-v-qemu-virt in FreeRTOS_ Scheduling opportunity of GCC
C # to obtain the filtered or sorted data of the GridView table in devaexpress
Basics - rest style development
技术分享 | 常见接口协议解析
如何将 DevSecOps 引入企业?
【DNS】“Can‘t resolve host“ as non-root user, but works fine as root
LSTM applied to MNIST dataset classification (compared with CNN)
2022 chemical automation control instrument examination questions and online simulation examination
About the use of Vray 5.2 (self research notes) (II)
Repair animation 1K to 8K