做电影电视剧网站推广,移动应用开发是什么意思,商城网站建设 亚马逊,婚纱摄影网站1. 汉诺塔问题为什么有解
相信只要接触过编程就会知道什么是汉诺塔问题#xff1a;
有三根柱子#xff0c;分别标记为A、B和C。初始时#xff0c;在柱子A上按从大到小的顺序堆叠着若干个圆盘。目标是将所有的圆盘从柱子A移动到柱子C。在移动过程中可以借助柱子B作为辅助
有三根柱子分别标记为A、B和C。初始时在柱子A上按从大到小的顺序堆叠着若干个圆盘。目标是将所有的圆盘从柱子A移动到柱子C。在移动过程中可以借助柱子B作为辅助但有以下限制 每次只能移动一个圆盘。 移动过程中任何柱子上的圆盘必须保持从大到小的顺序。 在任意时刻都不能将一个大圆盘放在一个小圆盘上。
解决汉诺塔问题的一般代码如下
void hanoi(int n, char from, char to, char aux)
{ // n圆盘数量from起始柱子to目标柱子qux辅助柱子在全局过程中是动态的if(n1){// 只需要移动一个盘子为问题的下界cout from - to endl;}else{// 先移动上面n-1个盘子到auxhanoi(n - 1, from, aux, to);// 再移动最下面大盘子到tohanoi(1, from, to, aux);// 最后移动n-1个盘子到tohanoi(n - 1, aux, to, from);}
} 这种解法的思路是每次将要移动圆盘进行一次汉诺塔算法时对于当前柱子x上的n(n0)个大小圆盘有序序列首先尝试将x上n-1个圆盘挪动到y再将x上的最后一个圆盘挪动到C ( x , y ∈ { A , B } ) (x,y\in \lbrace A, B \rbrace) (x,y∈{A,B})通过问题规模的不断缩小最终解决问题。
以上看起来严谨的数学推导实际是最不被人脑接受的内容因为它极其反直觉为什么只在n1时函数有输出为什么可以一次挪动n-1个圆盘既然一次可以挪动n-1个为什么不直接挪动任意个为什么不能获知圆盘移动的具体情况……可以说几乎没有任何人能够第一次就写出这样的代码正因为这样的困惑没有被解答才会导致问题变得抽象直接后果是不会写递归函数或写出来也不知道正确与否。
理解汉诺塔递归的门槛可以归结为以下三个问题
为什么解决圆盘有序调度问题恰好需要三根柱子凭什么可以进行违规的一次挪动n-1个圆盘依赖调用过程的递归函数是否可靠
2. 建立数学论证
要获得正确和可靠的算法就必须进行合理的数学论证学计算机不能畏惧数学。 关于问题1和2
首先显然仅有两个柱子起始和目标是无法完成任务的需要一个或以上柱子来作为辅助柱子实现始终大小正序的移动。判断辅助柱子的个数在1~n-1之间当然可以更多但没必要。注意到对于第一个最小的圆盘它始终位于当前柱子的最上方每个柱子对于它而言都是可放置的因此对它的移动操作是可撤回的即假设把它从A住移动到C柱稍后总是可以把它再放回A柱。同时考虑第一个和第二个圆盘在开始时先把1移到B再把2移到C最后把1移到C此时12圆盘可视作一个整体因为对于它们而言可以撤回到一开始的A柱也可以通过相同的步骤移动到B柱说明它们是一个“最小圆盘”。把A柱上的次小圆盘3号圆盘移动到B柱“最小圆盘”的12组合可以通过简单重复的步骤移动到B柱上123组合处于最小的地位”最小圆盘“得到扩大不断扩大这个整体就得到了最终的目标结论用一个辅助柱子就可以完成任务之所以可以一次挪动n-1个柱子是因为它们在柱子上方任何位置都是可以逐步放置和撤回的因此它们相当于一个最小的圆盘而不是在挪动的时候违反规则什么都不管。
根据以上结论可以得知
每次移动都要按照规则且都是对正确排序的最上方圆盘进行移动所以每次“移动圆盘”的操作都可以看作一个汉诺塔问题只不过起始柱子、目标柱子、辅助柱子各不相同由1所有问题都是汉诺塔问题而每次只能挪动一个圆盘因此问题规模是以“n-1”下降的递归的终止条件是n1即当真的只有一个圆盘的时候才可以直接移动而每次移动也只能移动一个圆盘也就是说真正的操作步骤只在n1内其他时候都在进行函数的反复调用。
由此根据终止条件和数学递推在正确推导的前提下可以保证函数结果正确……吗
3. 依赖过程的递归和纯函数编程
上述递归函数运行时的状态几乎是不可知的比如在不适用全局变量的条件下无法输出当前的调用深度及实际状态移动的是哪个盘子且输出结果极度依赖调用顺序必须先移动n-1再移动1最后还要n-1函数本身是不知道所谓小在上大在下的规则要求的
针对以上问题可以给出一种滴水不漏的解决方案即使用纯函数编程将函数所处理的当前状态作为参数之一
// 纯函数递归写法
using State arrayvectorint, 3;
using Result vectorState;
State move_disk(const State s0, int n, int from, int to)
{State s s0;vectorint disks;for (int i 0; i n; i){disks.push_back(s[from].back());s[from].pop_back();}for (int i n-1; i 0; i--){s[to].push_back(disks[i]);}return s;
}
void append(Result res, const Result step)
{res.insert(res.end(), step.begin(), step.end());
}
Result hanoi_r(State s0, int n, int from, int to)
{if (n 1)return {move_disk(s0, 1, from, to)};int aux 3 - from - to;State s1 move_disk(s0, n - 1, from, aux);State s2 move_disk(s1, 1, from, to);State s3 move_disk(s0, n, from, to);auto step1 hanoi_r(s0, n-1, from, aux);auto step2 hanoi_r(s1, 1, from, to);auto step3 hanoi_r(s2, n-1, aux, to);assert(step1.back() s1);assert(step2.back() s2);assert(step3.back() s3);Result res;append(res, step1);append(res, step2);append(res, step3);return res;
}纯函数编程的好处是对于同样的输入函数总会给出同样的输出而不依赖特定的调用顺序如step1~step3处可以任意打乱对调用顺序没有要求只需要符合数学推导就可以即程序运行时的特定生产过程就像数学公式一样当然这也就要求更完整的输入参数和对实际问题的适度模拟。
第一种递归写法中过程信息全部丢失只有n1的cout相当于只有一个活跃的State s每次传递都对其进行修改因此涉及到调用深度问题无法读取而在纯函数写法中生成的是State s临时变量相当于有多个短暂的副本每次函数的运行状态都得到了读取和拼接。汉诺塔问题只有三次调用自身如果遇到更复杂的问题恐怕是很难按照逻辑顺序写出非纯函数的。
n3时两种写法的对比如下
此外更经济的做法是直接用栈或者一个全局变量来记录或删除当前经历的状态这种做法也更常用于算法竞赛等场景加入边界条件和搜索剪枝等就可以解决动态规划等问题
Result Stack;
void hanoi_s(State s, int n, int from, int to)
{ // n圆盘数量from起始柱子to目标柱子int aux 3 - from - to;if(n1){// 只需要移动一个盘子为问题的下界s[to].push_back(s[from].back());s[from].pop_back();return;}else{hanoi_s(s, n-1, from, aux);if(Stack.empty() || s ! Stack.back())Stack.push_back(s);hanoi_s(s, 1, from, to);if(Stack.empty() || s ! Stack.back())Stack.push_back(s);hanoi_s(s, n-1, aux, to);if(Stack.empty() || s ! Stack.back())Stack.push_back(s);}
} 4. 测试用全部代码
#includeiostream
#includestring
#includevector
#includearray
#includeassert.husing namespace std;void hanoi(int n, char from, char to, char aux)
{ // n圆盘数量from起始柱子to目标柱子qux辅助柱子在全局过程中是动态的if(n1){// 只需要移动一个盘子为问题的下界cout from - to endl;}else{// 先移动上面n-1个盘子到auxhanoi(n - 1, from, aux, to);// 再移动最下面大盘子到tohanoi(1, from, to, aux);// 最后移动n-1个盘子到tohanoi(n - 1, aux, to, from);}
} // 自调用递归写法// 问题无法得知当前动的是该柱子上的几号盘子除非使用全局变量否则无法输出// cout只输出了从哪个柱子到哪个柱子同时由于cout的存在表示当前状态// 一旦依赖树状调用顺序的else部分受到打乱运行即出错或者说结果是错的// 纯函数递归写法
using State arrayvectorint, 3;
using Result vectorState;
State move_disk(const State s0, int n, int from, int to)
{State s s0;vectorint disks;for (int i 0; i n; i){disks.push_back(s[from].back());s[from].pop_back();}for (int i n-1; i 0; i--){s[to].push_back(disks[i]);}return s;
}
void append(Result res, const Result step)
{res.insert(res.end(), step.begin(), step.end());
}
Result hanoi_r(State s0, int n, int from, int to)
{if (n 1)return {move_disk(s0, 1, from, to)};int aux 3 - from - to;State s1 move_disk(s0, n - 1, from, aux);State s2 move_disk(s1, 1, from, to);State s3 move_disk(s0, n, from, to);auto step1 hanoi_r(s0, n-1, from, aux);auto step2 hanoi_r(s1, 1, from, to);auto step3 hanoi_r(s2, n-1, aux, to);assert(step1.back() s1);assert(step2.back() s2);assert(step3.back() s3);Result res;append(res, step1);append(res, step2);append(res, step3);return res;
}Result Stack;
void hanoi_s(State s, int n, int from, int to)
{ // n圆盘数量from起始柱子to目标柱子int aux 3 - from - to;if(n1){// 只需要移动一个盘子为问题的下界s[to].push_back(s[from].back());s[from].pop_back();return;}else{hanoi_s(s, n-1, from, aux);if(Stack.empty() || s ! Stack.back())Stack.push_back(s);hanoi_s(s, 1, from, to);if(Stack.empty() || s ! Stack.back())Stack.push_back(s);hanoi_s(s, n-1, aux, to);if(Stack.empty() || s ! Stack.back())Stack.push_back(s);}
} int main()
{// 测试 hanoi 函数cout Recursive Hanoi Function: endl;hanoi(3, A, C, B);cout --------------------------------------- endl;// 测试 hanoi_r 函数cout Pure Recursive Hanoi Function: endl;vectorint A {3, 2, 1};vectorint B, C {};State initial_state {A, B, C}; // 初始状态3个盘子在A柱Result result hanoi_r(initial_state, 3, 0, 2);hanoi_s(initial_state, 3, 0, 2);result Stack;// 输出每一步的状态for (const auto state : result) {for (const auto peg : state) {cout [ ;for (const auto disk : peg) {cout disk ;}cout ] ;}cout endl;}return 0;
}
