写点什么

汉诺塔(递归 + 非递归版)

作者:Five
  • 2022 年 8 月 17 日
    四川
  • 本文字数:2731 字

    阅读完需:约 9 分钟

汉诺塔(递归+ 非递归版)

汉诺塔

时间限制: 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 个盘的时候:


4 个的时候:



仔细研究研究就能发现,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;}
复制代码


点击并拖拽以移动


发布于: 2022 年 08 月 17 日阅读数: 35
用户头像

Five

关注

有事多研究,没事瞎琢磨 2022.08.02 加入

🏆第三季签约作者🏆,CSDN 前端领域优质创作者 , 博客专家认证, 华为云云享专家。 退役ACMer, IT技术狂热爱好者 擅长领域,web前端,算法, 业务架构,可视化,富文本编辑器等。

评论

发布
暂无评论
汉诺塔(递归+ 非递归版)_算法题_Five_InfoQ写作社区