汉诺塔专题讲解

汉诺塔

题意：三根柱子，每次移动距离无限制，一次移动一个圆盘，问将所有圆盘从按大小顺序移动到最少需要多少步。

思路：因为这里不需要小圆盘始终在大圆盘上面，所以

设移动个圆盘的方案为，显然先将个圆盘移动到上需要步。

然后最后一个圆盘移动到需要步，然后再将个圆盘移动到需要步。

所以.

汉诺塔1

题意：三根柱子，每次移动距离无限制，一次移动一个圆盘，要求小圆盘始终在大圆盘上面，问将所有圆盘从按大小顺序移动到最少需要多少步。

思路：设移动个圆盘的方案为，显然先将个圆盘移动到上需要 步，然后最后一个圆盘移动到需要步，然后再将个圆盘移动到需要步。所以 。（另外递归或者打表都可以找到规律）

递归代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int  cnt=0;
void fun(int n,char a,char b,char c){
     if(n==1){
          printf("第%d次移动：将%d号圆盘从 %c 移动到 %c\n",++cnt,1,a,c);
          return;
     } 
     fun(n-1,a,c,b);
    printf("第%d次移动：将%d号圆盘从 %c 移动到 %c\n",++cnt,n,a,c);
     fun(n-1,b,a,c);
}
int main(){
    int n;
    char a='a',b='b',c='c';
    while(~scanf("%d",&n)){
        cnt=0;
        fun(n,a,b,c);
        printf("总共移动次数：%d\n",cnt);
    }
    return 0;
} 

汉诺塔2

题意：三根柱子，每次移动到相邻柱子，一次移动一个圆盘，要求小圆盘始终在大圆盘上面，问将所有圆盘从按大小顺序移动到最少需要多少步。

思路：设移动个圆盘的方案为，先将上面个圆盘移动到上需要 步，然后最后一个圆盘移动到需要步，然后再将个圆盘移动到需要步,再将最后一个圆盘移动到需要一步，再将个圆盘移动到需要步，所以