宽屏模式

递归函数与汉诺塔移动

汉诺塔
汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。)(来自百度百科);

假设函数 move(n, a, b, c), 其接收的参数中, a,b,c分别代表三根柱子, n表示a柱子中盘的数量;
打印出a中的盘子借助b转移到c的方法;
关键点:

  • 大盘不能放在小潘下面;
  • 每次只能移动一个盘;

那么,
1~n:表示从最小到最大的盘编号
n:a->b表示移动轨迹;
n=1,时需要1次;从a到c;
1:a->c
n=2的时候需要3次;
1:a->b,2:a->c,3:b->c;
n=3的时候需要7次;
1:a->c,2:a->b,1:c->b,3:a->c,
1:b->a,2:b->c,1:a->c;
n=4的时候就需要15次;
1:a->b,2:a->c,1:b->c,
3:a->b,1:c->a,2:c->b,
1:a->b,4:a->c,1:b->c,
2:b->a,1:c->a,3:b->c,
1:a->b,2:a->c,1:b->c
...
n=n的时候需要2的n次方减1次;
显然,
首先,需要将前n-1个盘借助c从a移动到b;
然后,最后一个盘从a移动到c的;
最后,n-1个盘借助a从b移动到c;
即:

def hanoi(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        hanoi(n-1, a, '-->', b)
        hanoi(1, a, '-->', c)
        hanoi(n-1, b, '-->', c)

这样,汉诺塔的递归就出来了~

本文为Larwas原创文章,转载无需和我联系,但请注明来自larwas博客 https://larwas.com

Larwas
请先登录后发表评论
  • latest comments
  • 总共0条评论