济宁网络,福建seo学校,成都网站建设福州,物流企业网站建设方案前言
今天我们学习一个老经典的问题-----汉诺塔问题#xff0c;可能在学习编程之前我们就听说过这个问题#xff0c;那这里我们如何去通过编程的方式去解决这么一个问题呢#xff1f;下面接着看。 汉诺塔问题
问题描述 这里是引用汉诺塔问题源自印度一个古老的传说#x…前言
今天我们学习一个老经典的问题-----汉诺塔问题可能在学习编程之前我们就听说过这个问题那这里我们如何去通过编程的方式去解决这么一个问题呢下面接着看。 汉诺塔问题
问题描述 这里是引用汉诺塔问题源自印度一个古老的传说印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上移动过程中必须遵守以下规则 每次只能移动柱子最顶端的一个圆盘 每个柱子上小圆盘永远要位于大圆盘之上 下面展示一个三个的汉诺塔解决过程如下图所示 其他情况
解决思路分治算法 看上面这几个图我们是否发现这么一个特点要想把A柱子起始柱上的汉诺塔转移到C柱子目标柱上而且还要满足汉诺塔的基本条件那就把第三个柱子作为辅助柱B柱假设A柱子上有n个汉诺塔这时候先把A柱子除了最下面的一层其余的全部汉诺塔先放到B柱子上面然后再把A柱子最下面的汉诺塔放到C柱子上然后把B柱子上面的汉诺塔重新放回给A柱子当中这个过程C柱作为辅助柱子B是起始柱A是目标柱这个过程就完成了一次放置此时A柱子上面就剩下n-1个汉诺塔再次重复以上的过程最后就完成了汉诺塔的转移。 汉诺塔问题中3 个圆盘至少需要移动 7 次移动 n 的圆盘至少需要操作 2^n-1 次。 在汉诺塔问题中当圆盘个数不大于 3 时多数人都可以轻松想到移动方案随着圆盘数量的增多汉诺塔问题会越来越难。也就是说圆盘的个数直接决定了汉诺塔问题的难度解决这样的问题可以尝试用分治算法将移动多个圆盘的问题分解成多个移动少量圆盘的小问题这些小问题很容易解决从而可以找到整个问题的解决方案。
代码实现C语言
#includestdio.h//打印移动的过程
void move(char x, char y) {printf(%c---%c\n, x, y);
}//递归移动
void generate(int n,char a, char b, char c) {if (n 0)return; //如果移动完成了就返回开始递归运算//第一个过程先把A柱子上的前n-1个汉诺塔移到B柱子上再把最底下的那个汉诺塔移动到C上//此时a是起始柱子c是目标柱b是辅助柱 a---cgenerate(n - 1, a, c, b);move(a, c);//第二个过程当第一个过程完成了之后就要把B柱子上的n-1个汉诺塔移回A柱子这就是整体一个分支过程//此时b是起始柱a是目标柱c是辅助柱 b---agenerate(n - 1, b, a, c);
}int main() {int n;printf(输入汉诺塔个数);scanf(%d, n);generate(n, A, B, C);
}运行结果如下
好了以上就是本期的全部内容了这个汉诺塔是不是很有意思呢你学会了吗 分享一张壁纸
