题目描述

汉诺塔问题：
1.递归思想
首先递归你需要把他想象成已经完成的最后一步比如你上一个楼梯 你要把你想象成站在最后一级楼梯考虑问题，汉诺塔也是一样的。
2.分析：
当汉诺塔n=2时 假设柱子是A B C 盘子编号是 1，2
操作步骤：1->B 2->C 1->C
当汉诺塔n=n时 假设柱子是A B C 盘子编号是 1，2…n
操作步骤：(A上除最后一个的所有盘子)->B （A上盘子n）->C (B上所有盘子)->C
3.递归函数： void dfs（int n,int fir,int temp,int aim）
1.fir表示第几个柱子，temp表示辅助柱子 aim表示转移的目标柱子 m由于是全局变量直接统计就行
2.递归操作： (A上除最后一个的所有盘子)->B （A上盘子n）->C (B上所有盘子)->C 、
dfs(n-1 , 1 , 2 , 3 ) dfs( 1 , 1 , 3 , 2 ) dfs( u-1 , 2 , 3 , 1 )

样例

3
4
5

算法1

C++ 代码

#include<iostream>
using namespace std;

int n,m; //定义全局变量 盘子个数n 方案总数m

void dfs(int u,int fir,int temp,int aim) //汉诺塔递归函数 u表示 fir位置盘子个数 
{                                        //fir表示起始柱子 temp表示辅助盘子 aim表示目标柱子 
    if(u==1)
    {
        m++; return;   //递归终止条件 
    }

    dfs(u-1,1,2,3);
    dfs(1,1,3,2);
    dfs(u-1,2,3,1);
}
int main()
{
    cin>>n;     //输入盘子个数 
    dfs(n,1,2,3);  //递归开始 
    cout<<m<<endl; //输出结果 
}