番禺建网站,河北省和城乡住房建设厅网站首页,wordpress 自定义留言,wordpress 去掉tag说明#xff1a;使用递归时#xff0c;必须要遵守两个限制条件#xff1a;
递归存在限制条件#xff0c;满⾜这个限制条件时#xff0c;递归不再继续#xff1b; 每次递归调⽤之后越来越接近这个限制条件#xff1b;
1 汉诺塔#xff08;Hanoi Tower#xff09;经典…说明使用递归时必须要遵守两个限制条件
递归存在限制条件满⾜这个限制条件时递归不再继续 每次递归调⽤之后越来越接近这个限制条件
1 汉诺塔Hanoi Tower经典问题
1.1 汉诺塔问题描述
汉诺塔Hanoi Tower问题是一个经典的递归问题起源于一个关于印度的传说。问题描述如下
有一个三脚架上面有三个从下到上依次递减的圆盘总共有n个圆盘这些圆盘最初都放在第一个柱子上并且每个圆盘上都有不同的大小使得较大的圆盘不能放在较小的圆盘上面。任务是将所有圆盘从第一个柱子移动到第三个柱子同时满足以下规则
每次只能移动一个圆盘。每次移动的圆盘必须放在另一个柱子的顶部。任何时候较大的圆盘不能放在较小的圆盘上面。
1.2 汉诺塔问题分析
汉诺塔问题的分析可以通过递归的方式来理解。下面是针对n1, n2, n3时的步骤说明其中ABC分别对应第一二三个柱子
#n1时
初始状态 第一步完成
A B C A B C
1 0 0 0 0 1 #n2时
初始状态 第一步 第二步 第三步完成
A B C A B C A B C A B C
1 0 0 0 1 0 0 1 0 0 0 1
2 0 0 2 0 0 0 0 2 0 0 2#n3时
说明由n2时的状态可知2个盘从A移动到B或C均是可行的那么这里我们就将1和2堪称整体。
初始状态 第一步 第二步 第三步完成
A B C A B C A B C A B C
1 0 0 0 1 0 0 1 0 0 0 1
2 0 0 0 2 0 0 2 0 0 0 2
3 0 0 3 0 0 0 0 3 0 0 3可以看到这里的第一步和第三步实际上是使用了n2时的结论。接下来我们把2 3换成出n-1 n之间的关系。
初始状态 第一步 第二步 第三步完成
A B C A B C A B C A B C
1 0 0 0 1 0 0 1 0 0 0 1
2 0 0 0 2 0 0 2 0 0 0 2
3 0 0 0 3 0 0 3 0 0 0 3
... ... ... ...
n 0 0 n 0 0 0 0 n 0 0 n
可以看出来实际上和2与3 的关系是一致的。因此我们使用递归公式的分析进阶思考
对于n个圆盘将前n-1个圆盘从A柱移动到B柱使用辅助柱C。将第n个圆盘从A柱移动到C柱。将n-1个圆盘从B柱移动到C柱使用辅助柱A。
这个递归过程会不断重复直到所有的圆盘都按照规则成功地移动到目标柱子上。递归的深度是n-1因为每次移动n-1个圆盘然后是第n个圆盘再是n-1个圆盘。总共需要进行2^n - 1次移动才能完成n个圆盘的汉诺塔问题。
1.3 汉诺塔问题 逻辑解决方案
解决汉诺塔问题的方法是递归。对于n个圆盘解决步骤可以概括为
将上面的n-1个圆盘从起始柱子移动到辅助柱子不违反规则。将最大的圆盘第n个圆盘从起始柱子移动到目标柱子。将n-1个圆盘从辅助柱子移动到目标柱子现在最大的圆盘已经在目标柱子上不违反规则。
这个过程可以继续递归地应用到n-1个圆盘上直到n为1这时问题就变得非常简单只需将圆盘直接移动到目标柱子上。
2 代码实现
2.1 python代码实现
#!/usr/bin/python3
# -*- coding: UTF-8 -*-def hanoi(n, source, target, auxiliary):if n 0:# 将n-1个圆盘从source移动到auxiliary以target作为辅助hanoi(n-1, source, auxiliary, target)# 将第n个圆盘从source移动到targetprint(fMove disk {n} from {source} to {target})# 将n-1个圆盘从auxiliary移动到target以source作为辅助hanoi(n-1, auxiliary, target, source)# 调用函数将3个圆盘从A柱移动到C柱B柱作为辅助
hanoi(3, A, C, B)2.2 C代码实现
#include iostream// 函数声明
void hanoi(int n, char source, char target, char auxiliary);int main() {int numDisks 3; // 圆盘的数量hanoi(numDisks, A, C, B); // 将3个圆盘从A柱移动到C柱B柱作为辅助return 0;
}// 函数定义
void hanoi(int n, char source, char target, char auxiliary) {if (n 0) return; // 递归的基本情况// 将n-1个圆盘从source移动到auxiliary以target作为辅助hanoi(n - 1, source, auxiliary, target);// 将第n个圆盘从source移动到targetstd::cout Move disk n from source to target std::endl;// 将n-1个圆盘从auxiliary移动到target以source作为辅助hanoi(n - 1, auxiliary, target, source);
}
