双色Hanoi塔问题(hanoi)

设A、 B、 C是3 个塔座。开始时，在塔座A 上有一叠共n 个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1， 2， ……， n，奇数号圆盘着蓝色，偶数号圆盘着红色，如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：

规则(1)：每次只能移动1 个圆盘；
规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则(3)：任何时刻都不允许将同色圆盘叠在一起；
规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A， B， C 中任一塔座上。

试设计一个算法，用最少的移动次数将塔座A 上的n个圆盘移到塔座B 上，并仍按同样顺序叠置。

对于给定的正整数n，编程计算最优移动方案。

输入

第1 行是给定的正整数n。

输出

每一行由一个正整数k和2个字符c1和c2组成，表示将第k个圆盘从塔座c1移到塔座c2上。

样例输入

3

样例输出

1 A B
2 A C
1 B C
3 A B
1 C A
2 C B
1 A B

C语言实现

#include <stdio.h>

// 递归函数，用于解决汉诺塔问题，按照特殊规则移动圆盘
// n表示圆盘个数，from表示起始塔座，to表示目标塔座，aux表示辅助塔座
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf(“%d %c %c\n”, 1, from, to);         // 当只有1个圆盘时，直接从起始塔座移到目标塔座
        return;
    }
    // 先把上面n - 1个圆盘从起始塔座借助目标塔座移到辅助塔座
    hanoi(n - 1, from, aux, to);
    // 把最底下的第n个圆盘从起始塔座移到目标塔座
    printf(“%d %c %c\n”, n, from, to);
    // 再把辅助塔座上的n - 1个圆盘借助起始塔座移到目标塔座
    hanoi(n - 1, aux, to, from);
}

int main() {
    int n;
    scanf(“%d”, &n);     // 输入圆盘个数
    hanoi(n, ‘A’, ‘B’, ‘C’);     // 调用函数开始解决汉诺塔问题，起始塔座为A，目标塔座为B，辅助塔座为C
    return 0;
}

C++实现

#include <iostream>
using namespace std;

// 递归函数，用于解决汉诺塔问题，按照特殊规则移动圆盘
// n表示圆盘个数，from表示起始塔座，to表示目标塔座，aux表示辅助塔座
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << 1 << " " << from << " " << to << endl;         // 当只有1个圆盘时，直接从起始塔座移到目标塔座
        return;
    }
    // 先把上面n - 1个圆盘从起始塔座借助目标塔座移到辅助塔座
    hanoi(n - 1, from, aux, to);
    // 把最底下的第n个圆盘从起始塔座移到目标塔座
    cout << n << " " << from << " " << to << endl;
    // 再把辅助塔座上的n - 1个圆盘借助起始塔座移到目标塔座
    hanoi(n - 1, aux, to, from);
}

int main() {
    int n;
    cin >> n;     // 输入圆盘个数
    hanoi(n, ‘A’, ‘B’, ‘C’);     // 调用函数开始解决汉诺塔问题，起始塔座为A，目标塔座为B，辅助塔座为C
    return 0;
}

Java实现

import java.util.Scanner;

public class HanoiTower {
// 递归函数，用于解决汉诺塔问题，按照特殊规则移动圆盘
// n表示圆盘个数，from表示起始塔座，to表示目标塔座，aux表示辅助塔座
static void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        System.out.println(1 + " " + from + " " + to);         // 当只有1个圆盘时，直接从起始塔座移到目标塔座
        return;
    }
    // 先把上面n - 1个圆盘从起始塔座借助目标塔座移到辅助塔座
    hanoi(n - 1, from, aux, to);
    // 把最底下的第n个圆盘从起始塔座移到目标塔座
    System.out.println(n + " " + from + " " + to);
    // 再把辅助塔座上的n - 1个圆盘借助起始塔座移到目标塔座
    hanoi(n - 1, aux, to, from);
}
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();     // 输入圆盘个数
    hanoi(n, ‘A’, ‘B’, ‘C’);     // 调用函数开始解决汉诺塔问题，起始塔座为A，目标塔座为B，辅助塔座为C
    scanner.close();
}
}

Python实现

def hanoi(n, from_, to, aux):
    if n == 1:      # 递归函数，用于解决汉诺塔问题，按照特殊规则移动圆盘, n表示圆盘个数，from_表示起始塔座，to表示目标塔座，aux表示辅助塔座
        print(f"{1} {from_} {to}“)         # 当只有1个圆盘时，直接从起始塔座移到目标塔座
        return
    # 先把上面n - 1个圆盘从起始塔座借助目标塔座移到辅助塔座
    hanoi(n - 1, from_, aux, to)
    # 把最底下的第n个圆盘从起始塔座移到目标塔座
    print(f”{n} {from_} {to}")
    # 再把辅助塔座上的n - 1个圆盘借助起始塔座移到目标塔座
    hanoi(n - 1, aux, to, from_)

n = int(input())     # 输入圆盘个数
hanoi(n, ‘A’, ‘B’, ‘C’)     # 调用函数开始解决汉诺塔问题，起始塔座为A，目标塔座为B，辅助塔座为C