算法每日一题（四）

LNH_Sniper

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

提示：经典的递归问题。

仰望天上的光

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

仰望天上的光

#include<stdio.h>

void move(int n,char from,char pass,char to){
        if(n>0){
                move(n-1,from,to,pass);
                printf("从%c移动一个盘子到%c\n",from,to);
                move(n-1,pass,from,to);
        }
}
int main(){
        move(64,'A','B','C');
}

LNH_Sniper

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

#include "stdio.h"

void move( int n, char x, char y, char z )
{
if( n == 1 )
printf("%c-->%c\n",x,z);
else
{
move( n - 1, x, z, y );
printf("%c-->%c\n",x,z);
move( n - 1, y, x, z );
}
}

int main( void )
{
int n;
printf("input diskes number:\n");
scanf("%d",&n);
printf("The step to moving %d diskes:\n",n);
move( n, 'A', 'B', 'C' );
getchar();
return 0;
}
可以清晰看到结果

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。

void Move(char chSour, char chDest)
{
/*打印移动步骤*/
printf("\nMove the top plate of %c to %c",chSour, chDest);
}
Hanoi(int n, char chA, char chB, char chC)
{
/*检查当前的盘子数量是否为1*/
if(n==1) /*盘子数量为1，打印结果后，不再继续进行递归*/
Move(chA,chC);
else/*盘子数量大于1，继续进行递归过程*/
{
Hanoi(n-1,chA,chC,chB);
Move(chA,chC);
Hanoi(n-1,chB,chA,chC);
}
}
main()
{
int n;
/*输入盘子的数量*/
printf("\nPlease input number of the plates: ");
scanf("%d",&n);
printf("\nMoving %d plates from A to C:",n);

/*调用函数计算，并打印输出结果*/
Hanoi(n,'A','B','C');
}

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

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

asd82937121

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

zjc78361

学习学习

雪是梅之香

用Python就是这么简单

def hanoi(n,X,Y,Z):
    if n==1:
        print(X,'->',Z)
    else:
        hanoi(n-1,X,Z,Y)#将n-1个盘子移动到Y上
        print(X,'->',Z)#将最底下的盘子移到Z上
        hanoi(n-1,Y,X,Z)#将Y上的n-1个盘子移动到Z上

n=int(input('请输入汉诺塔的层数：'))
hanoi(n,'X','Y','Z')

zjc78361

好难得样子