问题描述

给定三根杆A、B、C和大小不同的几个盘子。这些盘子按尺寸递减顺序套在A杆上，最小的在最上面。现在的任务是把这些盘子从A杆移到C杆且保持原来堆放顺序。在实现任务时，每次只能移动一个盘子，且任何时刻不允许大的盘子放在小的盘子上面，B杆可以作为辅助存放杆。求：总共有n个圆盘时，搬动过程中的第m步是从哪个杆到哪个杆。

输入说明

你的程序需要从标准输入设备（通常为键盘）中读入多组测试数据。每组输入数据由一行组成，每行输入一个整数表示盘子数n，1≤n≤10，以及步数m，两个数据之间以一个空格分隔。行首和行尾没有多余的空格，两组数据之间也没有多余的空行。

输出说明

对每组测试数据，你的程序需要向标准输出设备（通常为启动该程序的终端）依次输出一行对应的答案，该行中输出第m步移动的情况，如第m步是从A移到B，则输出“A--B”（不包括引号）。如果移动过程不存在第m步，则输出“none” （不包括引号）。

两组数据之间无空行，第一组前及最后一组后也无空行。

#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
using namespace std;
int n, m;
int num;
bool flag = true;
void hannoi(int number, char start, char end, char help)
{if (number == 1){num++;if (num == m){cout << start << "--" << end << endl; flag = false;}return;}//汉诺塔是经典递归问题 其思想可以看成 先将n-1个盘子移动到 help 上hannoi(number - 1, start, help, end);//这里对于这n-1个盘子  目标杆就是 上述辅助杆//然后移动最大的盘子到 目标杆num++;if (num == m){cout << start << "--" << end << endl; flag = false;}hannoi(number - 1, help, end, start);}
int main()
{while (cin >> n >> m){num = 0;flag = true;hannoi(n, 'A', 'C', 'B');if (flag)cout << "none" << endl;}}

请忽略掉 头文件(之前的题留的没删

这道题 主要难点 在于 如何确定 第 m步 的路径 

首先 这道题的递归思想是 

如果 有 abc 3个杆 n个盘子（n>1

那就把 n-1个盘子放到b 然后把 最大的放到c 再把n-1个盘子移到c  就行

第一个问题在于  a b c三个杆的意义是会变的 所以 采用上面的递归方式 就行

然后我们回到最初的问题

根据上面的思想 我们大致写出了下面的递归式子

void hannoi(int number, char start, char end, char help)
{//汉诺塔是经典递归问题 其思想可以看成 先将n-1个盘子移动到 help 上hannoi(number - 1, start, help, end);//这里对于这n-1个盘子  目标杆就是 上述辅助杆//然后移动最大的盘子到 目标杆hannoi(number - 1, help, end, start);}

然后 我们就要开始统计步数了  首先 这是一个2级的递归  你一定要弄清他的底层逻辑

啊 当然 我们还没有设置 递归边界 就是当number==1 做一些操作然后return 就行

那么   这道题是如何递归的呢？

其实 他会一直进行上面的递归 直到 number==1  一直进行左递归

然后 遇到number==1 执行 左递归倒数第2层 的 最大（相对）盘子移动到目标杆（这里代码未给出

然后进行 左递归中 倒数第2层的右递归。 是的就是这么绕脑

因为这题双递归 是有很多分支的 因为有点抽象 所以自己理解理解吧 加油