第一题：汉诺塔问题

题目描述

给定三根柱子，初始状态下，最左边上有若干个圆盘，这些圆盘从上到下按从小 到大的顺序排列。任务是将这些圆盘全部移到中间杆上，且必须保持原有顺序不 变。在移动过程中，需要遵守以下规则：

  • 1、 只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。
  • 2、 每次只能移动一个圆盘。
  • 3、 小圆盘必须始终在大圆盘之上。 这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移 动一个盘，且不允许大盘放在小盘上面，所以 64 个盘的移动次数是：

18,446,744,073,709,551,615 这已经是一个天文数字，假定圆盘从小到大编 号为 1, 2, …n（n<20)，请你模拟下圆盘的移动过程。

输入格式

输入为一个整数(n<20）后面跟三个单字符字符串。

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

输出格式

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

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

样例：

输入数据

2 a b c

输出数据

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

样例解释

image.png

以样例数据为例：三根杆从左到右依次为 a,b,c,目标是从 a 杆把盘子移到 b 杆，移动过程中严格遵循题目上述 3 条移动规则，移动过程为：第一步将 1 号盘从 a移到 c（a->1->c），第二步将 2 号盘从 a 移到 b（a->2->b），第三步将 1 号盘从 c 移到 b（c->1->b），移动完毕。

视频讲解

https://dl.ccf.org.cn/video/videoDetail.html?_ack=1&id=7291955414321152

递归思路：

  • 将 n-1 个盘子从起始柱移动到辅助柱。
  • 将第 n 个盘子（最大的盘子）从起始柱移动到目标柱。
  • 将 n-1 个盘子从辅助柱移动到目标柱。

AC源码

方法一：

#include <bits/stdc++.h>
using namespace std;
void hanoi(int n , char source,char target ,char tmp){
    if(n== 0) return;

    hanoi(n-1,source,tmp,target);
    cout << source << "->" << n << "->" << target << "\n";
    hanoi(n-1,tmp,target,source);

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

    return 0 ;
}

方法二：

#include <bits/stdc++.h>
using namespace std;
char id[4];
// 使用数字代替字母柱号方便进行数学运算
// 1->2  空3=1^2
// 2->3  空1=2^3
// 1->3. 空2=1^3
void dfs(int c , int x ,int y){
    if(c==0 ) return;
    dfs(c-1,x,x^y);
    cout << id[x] << "->" << c << "->" << id[y] << "\n";
    dfs(c-1,x^y,y);
}
int main(){
    int n;
    cin >> n;
    for(int i = 1; i<= 3; i++){
        cin >> id[i];
    }
    dfs(n,1,2);

    return 0 ;
}