算法每日一题（四）

LNH_Sniper

问题：一块板上有三根针：A、B、C。A针上套有64个大小不等的圆盘，大的在下，小的在上。要把这64个圆盘从A针移动到C针上，每次只能移动一个圆盘，移动可以借助B指针进行，但在任何时候，任何针上上的圆盘都必须保持大盘在下，小盘在上。请编写一个程序，给出移动步骤。

提示：经典的递归问题。

仰望天上的光

...汉诺塔问题。。。64个盘。。。这个输出太长了，在console上看不到最前面的哦

仰望天上的光

1. #include<stdio.h>
   
2. 
   
3. void move(int n,char from,char pass,char to){
   
4.         if(n>0){
   
5.                 move(n-1,from,to,pass);
   
6.                 printf("从%c移动一个盘子到%c\n",from,to);
   
7.                 move(n-1,pass,from,to);
   
8.         }
   
9. }
   
10. int main(){
    
11.         move(64,'A','B','C');
    
12. }

复制代码

LNH_Sniper

题目分析：1.先将第1-63个盘子移动到B指针上，要保证大盘在下小盘在上。
                  2.再将最底下的最大盘子移到C针上
                  3.最后将B指针上的63个盘子移到C指针上。

1. 
   

复制代码

1. 
   
2. #include "stdio.h"
   
3. 
   
4. void move( int n, char x, char y, char z )
   
5. {
   
6. if( n == 1 )
   
7. printf("%c-->%c\n",x,z);
   
8. else
   
9. {
   
10. move( n - 1, x, z, y );
    
11. printf("%c-->%c\n",x,z);
    
12. move( n - 1, y, x, z );
    
13. }
    
14. }
    
15. 
    
16. int main( void )
    
17. {
    
18. int n;
    
19. printf("input diskes number:\n");
    
20. scanf("%d",&n);
    
21. printf("The step to moving %d diskes:\n",n);
    
22. move( n, 'A', 'B', 'C' );
    
23. getchar();
    
24. return 0;
    
25. }
    
26. 可以清晰看到结果

复制代码

asd82937121

一下端了63个盘子？？？

asd82937121

求解释 求解释

LNH_Sniper

asd82937121 发表于 2011-7-8 09:43

                               
登录/注册后可看大图

求解释 求解释

之前提出的问题可以划分为如下两个问题：
1.将A针上的第1~62个盘子借助C针移到B针上。
2.将B针上额63个盘子借助A针移到C针上。
解决上述两个问题又可以如此来做
问题1.
a.将A针上的第1~62个盘子借助B针移到C针上，要保证大盘在下，小盘在上。
b.再将第63个盘子移动到B针上。
c.最后将C针上的62个盘子借助A针移动到B针上。
为题2.
a.将B针上的第1~62个盘子借助C针移动到A针上，要保证大盘在下，小盘在上。
b.再将第63个盘子移到C针上。
c.最后将A针上的62个盘子借助B针移到C针上。

chao_prince

                               
登录/注册后可看大图

这个问题在盘子比较多的情况下，很难直接写出移动步骤。我们可以先分析盘子比较少的情况。假定盘子从大向小依次为：盘子1，盘子2，...，盘子64。

如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。
如果有2个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到c；将盘子2移动到c。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。
如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。
如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。
上述的思路可以一直扩展到64个盘子的情况：可以借助空座C将盘子1上的63个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的63个盘子移动到C。

1. void Move(char chSour, char chDest)
   
2. {
   
3. /*打印移动步骤*/
   
4. printf("\nMove the top plate of %c to %c",chSour, chDest);
   
5. }
   
6. Hanoi(int n, char chA, char chB, char chC)
   
7. {
   
8. /*检查当前的盘子数量是否为1*/
   
9. if(n==1) /*盘子数量为1，打印结果后，不再继续进行递归*/
   
10. Move(chA,chC);
    
11. else/*盘子数量大于1，继续进行递归过程*/
    
12. {
    
13. Hanoi(n-1,chA,chC,chB);
    
14. Move(chA,chC);
    
15. Hanoi(n-1,chB,chA,chC);
    
16. }
    
17. }
    
18. main()
    
19. {
    
20. int n;
    
21. /*输入盘子的数量*/
    
22. printf("\nPlease input number of the plates: ");
    
23. scanf("%d",&n);
    
24. printf("\nMoving %d plates from A to C:",n);
    
25. 
    
26. /*调用函数计算，并打印输出结果*/
    
27. Hanoi(n,'A','B','C');
    
28. }

复制代码

前几天，有事，没来。。今天的补上了。

其中，Hanoi函数的第一个参数表示盘子的数量，第二个参数表示源座，第三个参数表示借用的座，第四个参数代表目的座。比如Hanoi(n-1,A,C,B)表示借助C座把n- 1个盘子从A座移动到B座。
Move函数的第一个参数表示源座，第二个参数代表目的座。Move函数的功能是将源座最上面的一个盘子移动到目的座上。

asd82937121

感谢楼上两位， 我昨天想了好久，初步理解了程序，不过我觉得当初把这算法转换为程序实在是太**了

zjc78361

学习学习

雪是梅之香

用Python就是这么简单

1. def hanoi(n,X,Y,Z):
   
2.     if n==1:
   
3.         print(X,'->',Z)
   
4.     else:
   
5.         hanoi(n-1,X,Z,Y)#将n-1个盘子移动到Y上
   
6.         print(X,'->',Z)#将最底下的盘子移到Z上
   
7.         hanoi(n-1,Y,X,Z)#将Y上的n-1个盘子移动到Z上
   
8. 
   
9. n=int(input('请输入汉诺塔的层数：'))
   
10. hanoi(n,'X','Y','Z')

复制代码

zjc78361

好难得样子