c语言怎么循环加数组实现汉诺塔
导读:本文共3194.5字符,通常情况下阅读需要11分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 简介汉诺塔问题是学数据结构与算法的时候会遇到的问题,相信来看本文的读者应该都对汉诺塔问题有基本的了解,理论上所有的递归都可以改成循环,常规的做法是借助堆栈,但是我一想好像用循环加数组也可以实现,于是就有了本文,实现声明,本文最后出来的算法效率不高的,比直接用递归实现还要差很多,追求算法效率的同学就不用看这个了。题目:假设有3个柱子,分别为A、B、C,A柱子上有数... ...
目录
(为您整理了一些要点),点击可以直达。汉诺塔问题是学数据结构与算法的时候会遇到的问题,相信来看本文的读者应该都对汉诺塔问题有基本的了解,理论上所有的递归都可以改成循环,常规的做法是借助堆栈,但是我一想好像用循环加数组也可以实现,于是就有了本文,实现声明,本文最后出来的算法效率不高的,比直接用递归实现还要差很多,追求算法效率的同学就不用看这个了。
题目:假设有3个柱子,分别为A、B、C,A柱子上有数量为n个的空心圆盘,从上到下序号分别为1...n,要求把A柱子中的n个圆盘移动到C柱中,且序号大的盘子必须在在需要小的圆盘下方。
思路:如果只有1个圆盘需要移动,则直接从A柱移动到C柱,如果有n个圆盘(n>1)需要移动,则需要先把n-1个圆盘从A柱移动到B柱,再把第n个圆盘从A柱移动到C柱,最后把原来的n-1个圆盘从B柱移动到C柱。
例如:
将1个圆盘从A柱移动到C柱只需要1个步骤:
1. 把圆盘1从A移动到C
将2个圆盘从A柱移动到C柱需要3个步骤:
1. 把圆盘1从A移动到B
2. 把圆盘2从A移动到C
3. 把圆盘1从B移动到C
将3个圆盘从A柱移动到C柱需要7个步骤:
1. 把圆盘1从A移动到C
2. 把圆盘2从A移动到B
3. 把圆盘1从C移动到B
4. 把圆盘3从A移动到C
5. 把圆盘1从B移动到A
6. 把圆盘2从B移动到C
7. 把圆盘1从A移动到C
可以看出下面的递归算法的时间复杂度为O(2^n),因为存在有调用2^n-2次递归调用和1次原生printf;而空间复杂度为O(n),因为运行时栈中最多会同时保存n个函数的调用信息。
解释一下代码中参数的含义,void towers(int n, char from, char to, char aux)的意思是把n个圆盘从from柱子移动到to柱子,中间可以借用aux柱子。
分析一下上面的递归执行过程:
我们已经知道把1个圆盘从from移动到to的步骤是showMove(1, from, to)
;
而把2个圆盘从from移动到to的步骤是,先照着移动1个圆盘的操作,把前面1个圆盘从from移动到aux,再把第2个圆盘从from移动到to,最后按照移动1个圆盘的操作,把刚才的1个圆盘从aux移动到to。
同理,把3个圆盘从from移动到to的步骤是,先照着移动2个圆盘的操作,把前面2个圆盘从from移动到aux,再把第3个圆盘从from移动到to,最后按照移动2个圆盘的操作,把刚才的2个圆盘从aux移动到to。
所以,把n个圆盘的操作从from移动到to的步骤是,先照着移动n-1个圆盘的操作,把前面n-1个圆盘从from移动到aux,再把第n个圆盘从from移动到to,最后按照移动n-1个圆盘的操作,把刚才的n-1个圆盘从aux移动到to。
因此,我们可以记录移动1个圆盘的步骤,来得到移动2个圆盘的步骤,通过移动2个圆盘的步骤来得到移动3个圆盘的步骤,...最后得到移动n个圆盘的步骤。经过分析可以知道移动n个圆盘一共会有2^n-1个步骤
为了代码更加易懂,这里写了注释,修改了部分变量命名,统一用数组保存步骤集合,最后才输出。
可以看出这个算法的时间复杂度还是O(2^n),一共会执行2^(n+1)-1次setMoveAction语句和2^n-1次,printf语句,比起直接用递归还要复杂一些,而空间复杂度也是O(2^n),属于没什么用的算法,就是随便写写。
c语言怎么循环加数组实现汉诺塔的详细内容,希望对您有所帮助,信息来源于网络。