python实现汉诺塔移动

时间:2023-11-28 21:05:02

汉诺塔问题

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

思路

设hanoi(a, b, c, n)表示从A移动n个盘到C。那么要实现这个操作,首先要把A上面的n-1个盘移动到B,再把最大的第n个盘直接从A移动到C,然后把B的n-1个盘移动到C。用递归模拟这个操作。

代码实现

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 程序功能:实现汉诺塔移动

def move(a, b, c):
    print('move', a, 'to', c)

def hanoi(a, b, c, n):
    if n > 1:
        hanoi(a, c, b, n-1)
        move(a, b, c)
        hanoi(b, a, c, n-1)
    else:
        move(a, b, c)

n = input('请输入A柱的圆盘数量:')
hanoi('A', 'B', 'C', int(n))

如有不当之处欢迎指出!