/*补充-这个算法看上去很简洁~却折腾了九九半天时间~最终终于折腾出来了~注释也只能简单写写~*/

/*说明
  河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于
1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;
1883年法国数学家Edouard Lucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,
是由三支砖石棒(Pag)所支撑,开始是神在第一根棒上放置64个由上至下依次由小至大的金
盘(Disc),并命令僧侣将所有金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子
在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也
就是世界末日来临之时。
    解法:
    如果柱子标记,要由A搬至C,在只有一个盘子时,就将它直接搬至C,当有两个盘子,就将
B当作辅助柱。如果盘子数超过两个,将第三个以下的盘子遮起来,就很简单了,每次处理两
个盘子,也就是:A->B、A->C、B->C这三个步骤,而被遮住的部份,其实就是进入程式递回处
理。事实上,若有n个盘子,则移动完毕所需之次数为2^n-1,所以当盘子数为64时,则所需次
数为2^64-1=18446744073709551615为5.053090248594782e+16年,也就是约50万亿世纪
就假设每秒钟搬一个盘子好了,也要约5850亿年左右。
*/

#include<stdio.h>
void hanoi(int n,char A,char B,char C);
int main()
{
    int n=0;

    printf("请输入盘数:");
    scanf("%d",&n);

    hanoi(n,'A','B','C');

    return 0;
}
void hanoi(int n,char A,char B,char C)//n是代表执行盘子所在层数
{
    //--A代表需要移动的盘子所在柱子编号-B代表辅助柱编号--C代表移动的目标柱子编号
    if (n!=1)//当执行层数不为1时
    {
        hanoi(n-1,A,C,B);//A柱和B柱之间执行操作
        printf("Move sheet %d from %c to %c\n",n,A,C);//输出执行操作
        hanoi(n-1,B,A,C);//B柱和C柱之间执行操作
    }

   else 
        printf("Move sheet %d from %c to %c\n",n,A,C);//其实默认柱子为(A,B,C)也就是说A柱和C柱之间执行操作
}

PPPS：原来代码有bug~在prinf那里加个else就可以了~还是感谢4楼指点~

[此贴子已经被作者于2017-2-15 17:40编辑过]

就是要追求简洁，复杂了不好。九版再写个九连环解法及扣法如何？思维方式都差不多的，也要不了多少行。不同的是可能要两个函数互相递归。

我在网上看过一遍九连环的代码~没怎么研究过~这个还是有时间再去敲敲~

我输入4个盘子，第四步不对，应该a到b

收到的鲜花

• 九转星河 于 2017-02-15 16:50 送鲜花  10朵   附言：多谢提醒~

我在原基础上改了一下~等下我再看看~

还是这位朋友眼尖啊~

看来还是不能改代码~提供原版的~

/*说明
  河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于
1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;
1883年法国数学家Edouard Lucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,
是由三支砖石棒(Pag)所支撑,开始是神在第一根棒上放置64个由上至下依次由小至大的金
盘(Disc),并命令僧侣将所有金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子
在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也
就是世界末日来临之时。
    解法:
    如果柱子标记,要由A搬至C,在只有一个盘子时,就将它直接搬至C,当有两个盘子,就将
B当作辅助柱。如果盘子数超过两个,将第三个以下的盘子遮起来,就很简单了,每次处理两
个盘子,也就是:A->B、A->C、B->C这三个步骤,而被遮住的部份,其实就是进入程式递回处
理。事实上,若有n个盘子,则移动完毕所需之次数为2^n-1,所以当盘子数为64时,则所需次
数为2^64-1=18446744073709551615为5.053090248594782e+16年,也就是约50万亿世纪
就假设每秒钟搬一个盘子好了,也要约5850亿年左右。
*/

#include<stdio.h>
void hanoi(int n,char A,char B,char C);
int main()
{
    int n=0;

    printf("请输入盘数:");
    scanf("%d",&n);

    hanoi(n,'A','B','C');

    return 0;
}
void hanoi(int n,char A,char B,char C)//n是代表执行盘子所在层数
{
    if (n==1)
        printf("Move sheet %d from %c to %c\n",n,A,C);//其实默认柱子为(A,B,C)也就是说A柱和C柱之间执行操作
    //--A代表需要移动的盘子所在柱子编号-B代表辅助柱编号--C代表移动的目标柱子编号
    else//当执行层数不为1时
    {
        hanoi(n-1,A,C,B);//A柱和B柱之间执行操作
        printf("Move sheet %d from %c to %c\n",n,A,C);//输出执行操作
        hanoi(n-1,B,A,C);//B柱和C柱之间执行操作
    }


}

[此贴子已经被作者于2017-2-15 16:43编辑过]

刚刚从网上参考了九连环的资料~还没有写注释~不过有参考网址~
http://wenku.baidu.com/view/6679c2d1195f312b3169a569.html
~~~~

/*参考http://wenku.baidu.com/view/6679c2d1195f312b3169a569.html*/
#include<stdio.h>
#include<windows.h>
int upstep=0;
int downstep=0;
void DownRing(int n);
void UpRing(int n);
int main()
{
    int rings=0;

    /*clrscr*/
    system("cls");

    printf("请输入环数:");
    scanf("%d",&rings);

    puts("Starting...");
    DownRing(rings);
    puts("\nEnding...");

    printf("\nup=%d,\tdown=%d\n",upstep,downstep);

    return 0;
}

void DownRing(int n)
{
    if (n>2)
        DownRing(n-2);

    printf("DW:%d\t",n);
    ++downstep;/*getch();*/
    if (n>2)
        UpRing(n-2);
    if (n>1)
        DownRing(n-1);
}

void UpRing(int n)
{
    if (n>1)
        UpRing(n-1);

    if (n>2)
        DownRing(n-2);

    printf("UP:%d\t",n);

    ++upstep;

    if (n>2)
        UpRing(n-2);
}

[此贴子已经被作者于2017-2-15 17:35编辑过]

废话，，，，，，，，，，，

看来一楼原来的递归算法出现了逻辑漏洞~细看没有写else的确是低级错误啊~怎能让久久尴尬~~~~~~

这个代码比较强，我过去写的时候用了四个函数嵌套尴尬了~~~