C++汉诺塔问题（河内塔）
这是一个非常经典的递归问题。
递归：在函数内部又再次调用函数自身的问题
假设有n个盘子，需要把这些盘子从第一根起始柱A移动到第三根目标柱C中。
1、首先需要把n-1个盘子移动到第二根中转柱B上；
2、再把最后一个也就是最大的那一个盘子移动到第三根目标柱C上；
3、最后再把剩下的n-1个盘子移动到第三根目标柱C上。
我们定义f ( n ) f(n)f(n)是需要移动的次数；
f ( 1 ) = 1 ， f ( 2 ) = 3 ， f ( 3 ) = 7 f(1) = 1，f(2) = 3，f(3) = 7f(1)=1，f(2)=3，f(3)=7
…
f ( n ) = 2 f ( n − 1 ) + 1 f(n) = 2f(n-1)+1f(n)=2f(n−1)+1
#include<iostream>
#include<stdio.h>
using namespace std;
void move(int n, char pos1, char pos3)
{
//打印移动的过程
// 1代表上面最小的盘子
// 2代表中间位置的盘子
// 3代表下面最大的盘子
cout << "盘子" << n << "从" << pos1 << "移动到" << pos3<<endl;
}
void Hanoi(int n, char pos1, char pos2, char pos3)
{
//如果是1个盘子，直接从起始柱A移动到目标柱C
if (n == 1)
{
move(n, pos1, pos3);
}
else
{
//如果盘子大于1个，需要把n-1个盘子，从起始柱pos1，通过目标柱pos3，移动到中转柱pos2
Hanoi(n - 1, pos1, pos3, pos2);
//此时pos1上的n-1个盘子全部移动pos2上去了，那么可以直接把pos1上剩下的1个盘子，直接移动到pos3上
move(n, pos1, pos3);
//把pos2剩下的n-1个盘子，通过中转位置pos1，移动到目标位置pos3
Hanoi(n - 1, pos2, pos1, pos3);
}
}
int main()
{
//盘子个数
int n = 5;
//起始柱A
char pos1 = 'A';
//中转柱B
char pos2 = 'B';
//目标柱C
char pos3 = 'C';
cout << "移动盘子的顺序如下" << "这里有" << n << "个盘子:" << endl;
//汉诺塔函数
Hanoi(n, pos1, pos2, pos3);
return 0;
}
