2018年1月月赛 复仇的汉诺塔 题解

2018年1月月赛 复仇的汉诺塔 题解

题目背景

汉诺塔觉得自己不被mh和cl尊重，决定发动复仇！

它把mh和cl困在了古印度圣庙中，并告诉wy，如果不能输出最少搬动的方案，那mh和cl就再也出不来了！

题目描述

题目的要求是输出最少搬动方案。

输入输出格式

输入格式

一行，包含一个整数n，即为盘子数n，n为正整数，且最大值为10

输出格式

若干行。每一行格式如下：

Step i:X -> Y

其中，i为第i步，从1开始计算。

X，Y为A、B、C中某一个值。

输入输出样例

输入样例#1：

1

输出样例#1：

Step 1:A -> C

说明

对于100%的数据，1<=n<=20。

裸的递归，没什么好说的。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int sum=1;
void move(char x,char y){printf("Step %d:%c -> %c\n",sum++,x,y);}
void hanoi(int n,char from,char temp,char destination)
{
    if(n==1) move(from,destination);
    else
    {
        hanoi(n-1,from,destination,temp);
        move(from,destination);
        hanoi(n-1,temp,from,destination);
    }
}
int main()
{
    int n;
    cin>>n;
    hanoi(n,'A','B','C');
    return 0;
}

在上述代码中，我们在hanoi函数里定义了剩余盘子数量n，起始盘子位置from，中转盘子位置temp，目标盘子位置destination。

在每一步移动中，都可以分成两部分，一部分是最下面的那个盘子，一部分是剩下的盘子。每一步都可以看成先将剩下的盘子全部移动到其中转位置，再将最下面的盘子移动到其目标位置。每当发生最下面的盘子被移动到其目标位置时就输出。递归操作即可。