汉诺塔递归算法python

汉诺塔是一个经典的递归算法问题，其思路是将n个盘子从起始柱子通过中间柱子移动到目标柱子，保证大盘子在下面，小盘子在上面。在移动过程中，不能将大盘子放在小盘子上面。下面是汉诺塔递归算法的Python实现：

def hanoi(n, start, end, mid):
    if n == 1:
        print(start, '->', end)
    else:
        hanoi(n-1, start, mid, end)
        print(start, '->', end)
        hanoi(n-1, mid, end, start)

其中，n表示盘子的数量，start表示起始柱子，end表示目标柱子，mid表示中间柱子。当n等于1时，直接将起始柱子上的盘子移动到目标柱子上；当n大于1时，先将n-1个盘子从起始柱子移动到中间柱子上，再将最后一个盘子从起始柱子移动到目标柱子上，最后将n-1个盘子从中间柱子移动到目标柱子上。

相关问题

python汉诺塔递归算法

汉诺塔问题是一个经典的递归问题，其目标是将所有圆盘从一个标杆移动到另一个标杆，同时满足每次只能移动一个盘子，并且较大的盘子不能放在较小的盘子上面。下面是一个用Python编写的汉诺塔递归算法的示例代码：

def move(n, A, B, C):
    if n == 1:
        print(A, "->", C)
    else:
        move(n-1, A, C, B)
        print(A, "->", C)
        move(n-1, B, A, C)

n = int(input("请输入盘数："))
print("具体走法步骤如下：")
move(n, "A", "B", "C")

这段代码中，`move`函数接受四个参数，`n`表示当前需要移动的盘子数量，`A`、`B`、`C`分别表示三个标杆。当`n`等于1时，直接将盘子从A移动到C；否则，先将n-1个盘子从A移动到B，然后将最后一个盘子从A移动到C，最后再将n-1个盘子从B移动到C。通过递归调用，实现了整个汉诺塔的移动过程。

请注意，这段代码中使用了全局变量`i`来记录移动的步数，所以在使用时需要将全局变量`i`初始化为1。另外，这段代码中的输出语句使用了箭头符号`->`来表示移动的方向。

希望这个示例代码能够帮助你理解和实现汉诺塔递归算法。
#### 引用[.reference_title]
- *1* *3* [汉诺塔递归算法（Python编程）](https://blog.csdn.net/weixin_44263764/article/details/97390068)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* [汉诺塔——python递归](https://blog.csdn.net/New_Teen/article/details/123564145)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]

汉诺塔问题非递归算法python

汉诺塔问题的非递归算法可以使用栈来实现。具体步骤如下：

1. 将源柱子、辅助柱子、目标柱子入栈。

2. 当栈不为空时，重复以下步骤：

a. 弹出栈顶的三个柱子，记为 A、B、C。

b. 如果 A 中只有一个盘子，则将 A 中的盘子直接移到 C 中。

c. 如果 A 中有多个盘子，则将 A 中除最上面的一个盘子外的所有盘子借助 B 移到 C 中，再将最上面的盘子直接移到 C 中。

d. 将 B、A、C 三个柱子按照顺序入栈。

下面是Python代码实现：

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def is_empty(self):
        return len(self.items) == 0

def hanoi(n, A, B, C):
    stack = Stack()
    stack.push((n, A, B, C))
    while not stack.is_empty():
        n, A, B, C = stack.pop()
        if n == 1:
            print(f"Move disk {n} from {A} to {C}")
        else:
            stack.push((n-1, B, A, C))
            stack.push((1, A, B, C))
            stack.push((n-1, A, C, B))

hanoi(3, 'A', 'B', 'C')

输出结果为：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C