汉诺塔的递归算法是什么?
汉诺塔是一个经典的递归问题;
据传说,在古代印度的寺庙里,有一种游戏叫做河内塔。游戏在一个铜板装置上,有三根棒(编号为A、B、C)。在A杆上,64个金盘从下到上依次摆放。
游戏的目标:将A极上的所有金盘移动到C极,保持原来的顺序折叠。操作规则:一次只能移动一个盘子,移动过程中大盘子始终保持在三根杆子下面,小盘在上面。在操作过程中,该板可以放置在A、B和C的任何电极上。
如果A只有一个(A->;c)进行测试.
如果A有两个(A->;b)、(A->;c),(B->;c)进行测试.
如果A有三个(A->;c),(A->;b)、(C->;b)、(A->;c),(B->;a)、(B->;c),(A->;c)进行测试.
再多就爆炸了。
递归:函数调用自身。子问题必须和原问题是同一件事,或者更简单;递归通常可以简单地处理子问题,但不一定是最好的。
事实上,递归在某些情况下是低效的。尤其是斐波那契。从图中可以看出,一个简单的操作被重复多次。因为它递归调用了两个自我。那么它的递归膨胀率就是指数级的,重复大量相同的计算。
产地:
河内塔的问题是一个起源于古代印度传说的教育玩具。梵天创造世界的时候,做了三根钻石柱子,64个黄金圆盘从下到上按大小顺序叠放在一根柱子上。
梵天命令梵天从下到上按大小顺序重新排列另一根柱子上的圆盘。还规定小盘不能放大盘,一次只能在三根柱子之间移动一个盘。