F



i



v



e



-



gr



ea



t
汉诺塔游戏(递归与非递归详解)

汉诺塔游戏

​ 时间限制: 1 s|空间限制: 32000 KB

题目描述 Description

汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题。在A,B,C三根柱子上,

有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示),

你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。

游戏中的每一步规则如下:


\1. 每一步只允许移动一个盘子(从一根柱子最上方到另一个柱子的最上方)

\2. 移动的过程中,你必须保证大的盘子不能在小的盘子上方

(小的可以放在大的上面,最大盘子下面不能有任何其他大小的盘子)

如对于n=3的情况,一个合法的移动序列式:

1 from A to C

2 from A to B

1 from C to B

3 from A to C

1 from B to A

2 from B to C

1 from A to C

给出一个数n,求出最少步数的移动序列

输入描述 Input Description

一个整数n

输出描述 Output Description

第一行一个整数k,代表是最少的移动步数。

接下来k行,每行一句话,N from X to Y,表示把N号盘从X柱移动到Y柱。X,Y属于{A,B,C}

样例输入 Sample Input

3

样例输出 Sample Output

7

1 from A to C

2 from A to B

1 from C to B

3 from A to C

1 from B to A

2 from B to C

1 from A to C

数据范围及提示 Data Size & Hint

n<=10


递归思路分析:

我们设定三个柱子A,B,C。我们的目的是将环从A–>C。(A为起始位置,C为目标位置)

当N=1即一阶时它的路径很简单只需要从A->C进行移动。

当N=2时我们需要进行三步:

1.小盘 A->B

(假想没有大盘只有小盘,与N=1 的步骤一样,只是目标位置变为了 B)

2.大盘 A->C

(大盘上面的小盘到B去了,与N=1 的步骤一样直接到C )

3.小盘 B->C

(大盘到了C,对于小盘而言,C可以看作无盘,与N=1 的步骤一样,只是起始位置变为 B )

(分解一下,小盘从A通过B作为中间目标再到C。可以这样想

小盘下面的大盘目标是C 所以小盘第一次目标则变成B,

等到大盘到了目标C ,小盘再到C。

则完成将大小盘按小盘在上大盘在下的要求移到C。)

当N=3时我们需要进行七步:

1. 小盘 A->C 2.中盘 A->B 3.小盘 C->B

(假想没有大盘只有小盘和中盘,与N=2 的步骤一样,只是目标位置变为了 B)

4. 大盘 A->C,

​ (大盘上面的小盘和中盘都到B去了,与N=1 的步骤一样直接到C )

5. 小盘 B->A 6.中盘 B->C 7.小盘 A->C

(大盘到了C,对于小盘和中盘而言,C可以看作无盘,与N=2 的步骤一样,只是起始位置变为了 B )

(分解一下,大盘想从A去C。但上面压着小盘与中盘 ,

所以得先把他们移开 并且上面两盘不能移动到C,得移动到B 去

就相当于N=2时,起始位置A到目标位置B。待大盘移动到C。

当前在B 的小盘和中盘,完全就是执行N=2 的步骤。从当前起始位置B 到目标位置C.)

如此执行,通过递归方式。代码思路如下:

1. 对于执行最大盘(n) 到C的操作之前,肯定是?把次大盘(n-1)从A移动到 B 2. 执行最大盘(n) 到C的操作 3.对于执行最大盘(n) 到C的操作之后,肯定是?把次大盘(n-1)从B移动到C

每次只关心上一层,上上层是到了上一层才考虑的事——递归

题目链接:http://codevs.cn/problem/3145/


#include <stdio.h>
void han(int n, char A, char B, char C){
    if(n == 1)printf("%d from %c to %c\n", n, A, C);
    else{
    //第一步  对于执行最大盘(n) 到C的操作之前
    han(n-1, A, C, B);
    //第二步  执行最大盘(n) 到C的操作 
    printf("%d from %c to %c\n", n, A, C);
    //第三步  对于执行最大盘(n) 到C的操作之后 
    han(n-1, B, A, C); 
   }
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", (1 << n) - 1);
    han(n, 'A', 'B', 'C');
    return 0;
}

点击并拖拽以移动


非递归 思路:

我们先找找规律:

当3个盘的时候:

1 1:A–>C
2 2:A–>B
3 1:C–>B
4 3:A–>C
5 1:B–>A
6 2:B–>C
7 1:A–>C

4个的时候:

1 1:A–>B
2 2:A–>C
3 1:B–>C
4 3:A–>B
5 1:C–>A
6 2:C–>B
7 1:A–>B
8 4:A–>C
9 1:B–>C
10 2:B–>A
11 1:C–>A
12 3:B–>C
13 1:A–>B
14 2:A–>C
15 1:B–>C

仔细研究研究就能发现,1号出现在·1,3,5,7,9步

2号出现在2,6,10,14 步

3号出现在4,12 步

4号在8,步

规律与2^n有关。

我们在研究研究,三个时:

一号盘的行动方式是:

A–>C

C–>B

B–>A

A–>C

二号盘的行动方式是:

A–>B

B–>C

三号盘的行动方式是:

A–>C

四个时:

一号盘的行动方式是:

A-->B

B–>C

C–>A

A-->B

B–>C

C–>A

A-->B

B–>C

(成一定的周期T=3,当l号盘同最大盘n奇偶性相同,则 执行周期为顺时针,A–>B,B–>C,C–>A

​ 否者则 执行周期为逆时针,A–>C,C–>B,B–>A )

二号盘的行动方式是:

A–>C

C–>B

B–>A

A–>C

三号盘的行动方式是:

A–>B

B–>C

四号盘的行动方式是:

A–>C

总结下:
A号柱有n 个盘子,叫做源柱.移往C 号柱,叫做目的柱.B 号柱叫做中间柱.
全部移往C 号柱要f(n) =(2^n)- 1 次.
最大盘n 号盘在整个移动过程中只移动一次,n-1 号移动2 次,i 号盘移动
2^(n-i)次.
1 号盘移动次数最多,每2 次移动一次.
第2k+1 次移动的是1 号盘,且是第k+1 次移动1 号盘.
第4k+2 次移动的是2 号盘,且是第k+1 次移动2 号盘.

第(2^s)k+2^(s-1)次移动的是s 号盘,这时s 号盘已被移动了k+1 次.
每2^s 次就有一次是移动s 号盘.
第一次移动s 号盘是在第2^(s-1)次.
第二次移动s 号盘是在第2^s+2^(s-1)次.
第k+1 次移动s 号盘是在第k*2^s+2^(s-1)次.

A–>B,B–>C,C–>A叫做顺时针方向,A–>C,C–>B,B–>A叫做逆时针方向.
最大盘n 号盘只移动一次:A–>C它是逆时针移动.
n-1 移动2 次:A–>B,B–>C,是顺时针移动.

代码实现:

​ 枚举 1, 2, 3, 4·····i, i+1, i+2, ·····步。

​ 先 获取 第i步移动的几号盘,根据 (2^s)k+2^(s-1)=i,转化一下,满足 i%(2^s) =2^(s-1) ,令t=2^s;则有i%t=t/2

​ 再 获得第S盘 第几次移动 ,根据 (2^s)k+2^(s-1)=i, k=i/(2^s) ,即 k=i/t;

​ 最后 根据周期T 与奇偶性 确定具体移动的步骤(共6六种)

代码:

#include<stdio.h>
int main(){
long long i, res,t,k;int n,s;
scanf("%d", &n);
res=(1<<n)-1; 
 printf("%lld\n",res);
     for( i=1; i <=res; i++ ){ 
        for( t=2,s=1; s<= n; s++,t*=2)if( i%t == t/2 ) break;//i%t=t/2 找 第i步移动的S号盘
          k = i/t;//获得第S盘 第几次移动 
            if( n%2 == s%2 ){// 逆时针
                    if( (k+1)%3 == 0 ) printf("%d from B to A\n",s);
                    if( (k+1)%3 == 1 ) printf("%d from A to C\n",s);
                    if( (k+1)%3 == 2 ) printf("%d from C to B\n",s);
            }
            else{// 逆时针
                    if( (k+1)%3 == 0 ) printf("%d from C to A\n",s);
                    if( (k+1)%3 == 1 ) printf("%d from A to B\n",s);
                    if( (k+1)%3 == 2 ) printf("%d from B to C\n",s);
            }
     }
 return 0;
}

更多详情请到:Five-菜鸟级