汉诺塔问题

学递归,跳不过汉诺塔这个程序。以前弄NOIP,老师很详细地讲过汉诺塔的原理以及实现算法,不过我上大学了却发现老师讲到汉诺塔,只是像一笔带过,原理都没讲通,更别说算法了。我相信像他那么讲,没一个同学(没基础的)能弄得懂,就算你给一个flash汉诺塔的游戏,也不见得会玩。

汉诺塔真的挺有意思的,我写这篇文章,也算是回忆回忆以前学过的知识。如果有什么错误,还请原谅。

没有听说过汉诺塔的人,可以去baidu查查,或则你去http://www.4399.com/flash/293.htm 玩一玩,大概就知道是干什么的了。

现在有A、B、C三根柱子,A柱子上有n个大小不同的盘子,准备移到C柱子上。我们现在换一个说法:A柱子上有n个大小不同的盘子,我们借助B,将A上的n个盘子移动到C上。

假设n是1,很简单,直接将A上的1个盘子移到C上。

汉诺塔 - 两个盘子

假设n是2,怎么想?分三步,一是将小盘子移到B上,二是将大盘子移到C上,三是将小盘子移到C上。在大盘子移到C上之前,小盘子在哪里都无所谓。

所以我们先将小盘子从A上移到B上,再把大盘子从A移到C上,再把小盘子从B移到C上。移完后总共需要移动的次数是3。

汉诺塔 - 三个盘子

假设n是3,分三步,一是把上面的两个盘子借助C移到B,二是把大盘子移到C,三是将其余两个盘子借助A移到C。其中第一、第三步又分两个小步。这两步步骤和n=2时相同,所以移完后总共需要移动的步数是3+1+3=7步。

我们已经可以从其中发现递归的思想。当我们做第一步时,完全可以忽略最大的盘子,问题仅仅是将两个盘子从A借助C移到B。第三步时,也忽略已经移到C柱子上的大盘子,问题变成将在B上的两个盘子借助A移到C。

于是我们可以设计一个函数,它的功能是将n个在x柱子上的盘子借助y柱子移到z柱子上。

这么写:hanota(n,x,y,z);

于是我们上面的三步可以用程序语言来表达:

  1. hanota(n-1,A,C,B);
  2. hanota(1,A,B,C);
  3. hanota(n-1,B,A,C);

这是三个盘子时候的情况。四个盘子时候我们仍然可以这样想,先将上面的三个盘子借组C移动到B,再将最下面一个盘子移动到C,最后将其余三个盘子借助A移动到C。然后一、三两步又分两个小步。通过递归的思想,将大问题逐步转化成小问题。最后解决。

下面看我们这个hanota函数怎么写。

#include<stdio.h>
void hanota(int n,char x,char y,char z){
    if(1 == n) 
        printf("将%c上的盘子移动到%c柱子上\n",x,z);
    else{
        hanota(n-1,x,z,y);  //第一步
        printf("将%c上的盘子移动到%c柱子上\n",x,z);  //第二步
        hanota(n-1,y,x,z);  //第三步
        }
    }
int main(){
    int n;
    printf("输入盘子的数量:");
    scanf("%d",&n);
    hanota(n,'A','B','C');
    return 0;
    }

我们看这个递归,最后的结束条件是n==1时。也就是说问题大而化小之后,只有一个盘子了,就可以直接移动了。否则就继续将n-1放进hanota函数进行移动(也是三步)。

汉诺塔 - 程序结果截图

这是移动三个盘子的结果图,和我上面的那个gif里移动的步骤是一样的。你们也可以试一下,不过输入的n不能太大了,否则算不出来的。移动的步数和n是成指数增加的,当n=64时,需要移动2<sup>64</sup>-1次,这是个天文数字。n通常不要大于16就行了。

如果你以前没有任何递归的基础,也许你看不懂这些代码。如果你知道递归的一些知识,你才会发现这道题实际上十分基础。但是如果不用递归来做,我想没多少人能把程序写出来。因为递归解决了我们很难思考的问题,将问题大而化小。很多新手包括我有时候在想,递归明明好像比循环难,但为什么老师说递归更易于理解。这些东西也许只有等我们做了更多题,接触了更多有关树和图的问题以后才能理解吧。

最后给大家和我自己留一个问题:汉诺塔是三根柱子,如果我们有四根柱子,我们又怎样移动盘子,或者说怎样移动使步数最少?有时间我会想想这个问题,以后写一个“汉诺塔拓展”。

我把程序传到附件里了,大家可以下载运行了试试。

赞赏

喜欢这篇文章,扫码和我成为赞友!

评论

草没味的梨 回复

为什么 输入 偶数个盘子和奇数个盘子 编译的结果不同 一个是把1个从a移到b 奇数个楼主已经编译了 请问这是为什么

落沐萧萧 回复

@草没味的梨:盘子个数不同,移动的步骤当然不同呀

captcha