C/C++实现汉诺塔游戏和详细解

程序员小涛

发布于 2024-05-26 17:32:53

1540

发布于 2024-05-26 17:32:53

文章被收录于专栏：涛的程序人生涛的程序人生

C/C++实现汉诺塔游戏和详细解析

引言

汉诺塔问题是一个经典的递归问题，起源于一个传说中的印度寺庙。在这个问题中，我们需要将所有的圆盘从一个柱子移动到另一个柱子上，且在移动过程中，必须遵守以下规则：

一次只能移动一个圆盘。
每次移动后，较大的圆盘不能放在较小的圆盘上面。
可以借助第三个柱子作为中转。

本文将通过C/C++代码详细解释如何实现汉诺塔游戏，并展示其递归解法。

汉诺塔的递归解法

汉诺塔的解决方案可以通过递归方法非常优雅地实现。递归的基本思想是将问题分解成更小的问题，直到问题足够小，可以直接解决。

代码实现

以下是使用C/C++实现汉诺塔问题的代码示例：

#include<iostream>
using namespace std;

void hanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        cout << "Move disk 1 from " << from_rod << " to " << to_rod << endl;
        return;
    }
    hanoi(n-1, from_rod, aux_rod, to_rod);
    cout << "Move disk " << n << " from " << from_rod << " to " << to_rod << endl;
    hanoi(n-1, aux_rod, to_rod, from_rod);
}

int main() {
    int n;  // Number of disks
    cout << "Enter the number of disks: ";
    cin >> n;
    hanoi(n, 'A', 'C', 'B');  // A, B and C are names of rods
    return 0;
}