递归汉诺塔

经典算法

递归汉诺塔

阅读量: 82 编辑

已知有三个柱子用 a、 b、 c 表示。

在 a 柱子中从小到大放 n 个盘子，现要求把所有的盘子从 a 柱子全部移到 c 柱子。移动规则是：使用 b 作为过渡，每次只移动一块盘子，且每个柱子上不能出现大盘压小盘，找出移动次数最小的方案。

【输入描述】

输入一行。输入柱子的数量，和每个柱子的符号，用空格隔开。

【输出描述】

输出若干行，分别表示移动盘子的过程。

【输入样例】

3 a b c

【输出样例】

a->1->c
a->2->b
c->1->b
a->3->c
b->1->a
b->2->c
a->1->c

【参考程序】

// 爱码岛编程
#include <bits/stdc++.h>
using namespace std;

/**
 *把第n号盘子从a移动到c（注意参数的顺序）
 *b是中转柱（注意谁是中转盘）
 */
void hanoi(int n, char a, char b, char c) {
    if (n == 0)
        return;

    //移动n-1整体盘子，从a到b，c是中转盘
    hanoi(n - 1, a, c, b);

    //移动编号 n 的盘子
    printf("%c->%d->%c\n", a, n, c);

    //移动n-1整体盘子，从b到c，a是中转盘
    hanoi(n - 1, b, a, c);
}

int main() {
    int n;
    char a, b, c;
    cin >> n >> a >> b >> c;

    //如果是移动到b, 互换b、c参数位置；（一本通1205）
    hanoi(n, a, b, c);

    return 0;
}