分享

汉诺塔问题代码实现

 海漩涡 2014-09-03
/*


先分析盘子个数不同时移动的状况,以及A、B、C每个柱上盘子数变化

数字代表每个盘子的号码。
1、一个盘子,1:A-->C
2、两个盘子,1:A-->B 、2:A-->C、1:B-->C
3、三个盘子,1:A-->C、2:A-->B、1:C-->B
                      3:A-->C、1:B-->A、2:B-->C、1:A-->C
(1)有题目要求可知B柱是一个让我们间接放一下盘子的地方,明确我们的目的是从A柱上将盘子移动到C柱。

(2)从一个、两个、三个盘子,这三种情况可以分析出,要将A柱最低下的盘子移动到C柱,就必须先将最底下盘子之上的所有盘子移动到B柱。然后将最大号盘子移至C柱。

(3)此时,A柱上无盘子,B柱上除最大号盘子的所有盘子,C柱有一个最大号盘子。
 因为最大号盘子已经移动到目的地C柱,所有假设不再移动这个最大号盘子,


(4)在后续的移动中可以忽略这个不移动的最大盘子。此时:A无盘子,B所有盘子,C无盘子。

(5)又回到了一开始类似的情形,不过此时A成为了临时间接放盘子的地方,从B移动到目的地C柱。循环下去就会将所有最低下的盘子一个一个的移动到C柱,直到最上面的盘子移动到C柱。

*/

#########################################################################
#include <stdio.h>

void hanoi(char A,char B, char C, int n)
{
    if(n <= 0)
    {
        fprintf(stdout,"the n error: n <= 0");
}
else if(1 == n)
{
        fprintf(stdout,"%d:%c-->%c\n", n, A, C);
}
else
{
        hanoi(A,C,B,n-1);
fprintf(stdout,"%d:%c-->%c\n", n, A, C);
hanoi(B,A,C,n-1);
}
}

int main(int argc,char *argv[])
{
    int n=0;

    while(1)
    {
fprintf(stdout,"please input a number more than 0:\n");
scanf("%d",&n);
if(n<=0)
{
continue;
            fprintf(stdout,"you input a error nummber\n");
}
else
{
            break;
}
}
hanoi('A','B','C',n);

return 0;
}

#########################################################################

有一个梵塔,塔内有三个座A、B、C,A座上有诺干个盘子,盘子大小不等,大的在下,小的在上(如图)。

把这些个盘子从A座移到C座,中间可以借用B座但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘

子始终保持大盘在下,小盘在上。

描述简化:把A柱上的n个盘子移动到C柱,其中可以借用B柱。

  

  我们直接假设有n个盘子:

  先把盘子从小到大标记为1、2、3......n

  先看原问题三个柱子的状态:
状态0  A:按顺序堆放的n个盘子。B:空的。C:空的。

  目标是要把A上的n个盘子移动到C。因为必须大的在下小的在上,所以最终结果C盘上最下面的应该是标号为n的盘子,试想:

要取得A上的第n个盘子,就要把它上面的n-1个盘子拿开吧?拿开放在哪里呢?共有三个柱子:A显然不是、如果放在C上

了,那么最大的盘子就没地方放,问题还是没得到解决。所以选择B柱。当然,B上面也是按照大在下小在上的原则堆放的

(记住:先不要管具体如何移动,可以看成用一个函数完成移动,现在不用去考虑函数如何实现。这点很重要)。

  很明显:上一步完成后三个塔的状态:

状态1:   A:只有最大的一个盘子。B:有按规则堆放的n-1个盘子。C空的。

  上面的很好理解吧,好,其实到这里就已经完成一半了。(如果前面的没懂,请重看一遍。point:不要管如何移动!)

我们继续:

  这时候,可以直接把A上的最大盘移动到C盘,移动后的状态:

中间状态:  A:空的。B:n-1个盘子。C:有一个最大盘(第n个盘子)

  要注意的一点是:这时候的C柱其实可以看做是空的。因为剩下的所有盘子都比它小,它们中的任何一个都可以放在上面,也就是                    C柱上。

  所以现在三个柱子的状态:

中间状态:  A:空的。B:n-1个盘子。C:空的

  想一想,现在的问题和原问题有些相似之处了吧?。。如何更相似呢?。显然,只要吧B上的n-1个盘子移动到A,待解决的问题和原问题就相比就只是规模变小了

  现在考虑如何把B上的n-1个盘子移动到A上,其实移动方法和上文中的把n-1个盘从A移动到B是一样的,只是柱子的名称换了下而已。。(如果写成函数,只是参数调用顺序改变而已)。 

  假设你已经完成上一步了(同样的,不要考虑如何去移动,只要想着用一个函数实现就好),请看现在的状态:

状态2: A:有按顺序堆放的n-1个盘子。B:空的。C:按顺序堆放的第n盘子(可看为空柱)

就在刚才,我们完美的完成了一次递归。如果没看懂请从新看一遍,可以用笔画出三个状态、静下心来慢慢推理。

我一再强调的:当要把最大盘子上面的所有盘子移动到另一个空柱上时,不要关心具体如何移动,只用把它看做一个函数可以完成即可,不用关心函数的具体实现。如果你的思路纠结在这里,就很难继续深入了。

到这里,其实 基本思路已经理清了。状态2和状态0,除了规模变小 ,其它方面没有任何区别了。然后只要用相同的思维方式,就能往下深入。。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多