题目描述

约 19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由 64 个圆盘构成的塔。

目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。

这是一个著名的问题，几乎所有的教材上都有这个问题。

由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以 64 个盘的移动次数是：18,446,744,073,709,551,615 这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。

我们仅能找出问题的解决方法并解决较小 N 值时的汉诺塔，但很难用计算机解决 64 层的汉诺塔。

假定圆盘从小到大编号为 1,2,…

输入格式
输入为一个整数后面跟三个单字符字符串。

整数为盘子的数目，后三个字符表示三个杆子的编号。

输出格式
输出每一步移动盘子的记录。一次移动一行。

每次移动的记录为例如 a->3->b 的形式，即把编号为 3 的盘子从 a 杆移至 b 杆。

数据范围
盘子的数目范围 [1,20]。

样例

输入

2 a b c

输出

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

C

#include <stdio.h>

void hanoi(int n, char a, char b, char c);

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

    scanf("%d %c %c %c", &n, &a, &b, &c);

    hanoi(n, a, c, b);

    return 0;
}

void hanoi(int n, char a, char b, char c) {
    if (n == 1)
        printf("%c->%d->%c\n", a, n, c);
    else {
        hanoi(n - 1, a, c, b);
        printf("%c->%d->%c\n", a, n, c);
        hanoi(n - 1, b, a, c);
    }
}

C++

注意C++的输出要用printf，否则会超时

#include <iostream>

using namespace std;

void hanoi(int n, char a, char b, char c);

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

    cin >> n >> a >> b >> c;

    hanoi(n, a, c, b);

    return 0;
}

void hanoi(int n, char a, char b, char c) {
    if (n == 1)
        printf("%c->%d->%c\n",a,n,c);
    else {
        hanoi(n - 1, a, c, b);
        printf("%c->%d->%c\n",a,n,c);
        hanoi(n - 1, b, a, c);
    }
}

Java

注意Java的输入输出要用BufferedReader和BufferedWriter，否则会超时

import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] lines = br.readLine().split(" ");
        int n = Integer.parseInt(lines[0]);
        char a = lines[1].charAt(0);
        char b = lines[2].charAt(0);
        char c = lines[3].charAt(0);

        hanoi(n, a, c, b);

        br.close();
        bw.close();
    }

    public static void hanoi(int n, char a, char b, char c) throws IOException {
        if (n == 1) {
            bw.write(a + "->" + n + "->" + c);
            bw.newLine();
        }
        else {
            hanoi(n - 1, a, c, b);
            bw.write(a + "->" + n + "->" + c);
            bw.newLine();
            hanoi(n - 1, b, a, c);
        }
    }
}

Python3

def hanoi(n, a, b, c):
    if (n == 1):
        print(a + "->" + str(n) + "->" + c)
    else:
        hanoi(n - 1, a, c, b)
        print(a + "->" + str(n) + "->" + c)
        hanoi(n - 1, b, a, c);

lines = input().split(" ")
n = int(lines[0])
a = lines[1]
b = lines[2]
c = lines[3]
hanoi(n, a, c, b)