Hanoi(汉诺塔)

说明:

汉诺塔(河内塔)(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家 Edouard Lucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小 至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当 盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。

解法:

如果柱子标为ABC,要由A搬至C,在只有一个盘子时,就将它直接搬至C,当有两个盘子,就将B当作辅助柱。

如果盘数超过2个,将第三个以下的盘子遮起来,就很简单了,每次处理两个盘子,也就是:A->B、A ->C、B->C这三个步骤,而被遮住的部份,其实就是进入程式的递归处理。

事实上,若有n个盘子,则移动完毕所需之次数为2^n - 1,所以当盘数为64时,则所需次数为:$2^{64}$ - 1= 18446744073709551615,如果对这个数字没什么概念,就假设每秒钟搬一个盘子,那么需要5850亿年左右!

演算法:

Procedure HANOI(n, A, B, C) 
{
    IF(n == 1) 
    {
        PRINT("Move sheet " n " from " A " to " C);
    }
    ELSE
    { 
        HANOI(n-1, A, C, B);
        PRINT("Move sheet " n " from " A " to " C);
        HANOI(n-1, B, A, C); 
    }    
}

C:

#include <stdio.h>
void hanoi(int n, char A, char B, char C) 
{
    if(n == 1) 
    {
        printf("Move sheet %d from %c to %c\n", n, A, C);
    }
    else 
    {
        hanoi(n-1, A, C, B);
        printf("Move sheet %d from %c to %c\n", n, A, C);
        hanoi(n-1, B, A, C);
    }
}
int main() 
{
    int n;
    printf("请输入盘数:");
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Java:

public class Hanoi{
    int N;
    public static void hanoi(int n,char src,char mid,char goal){
        if(n==1){
            System.out.println(src + "——>" + goal);
            return;
        }
        hanoi(n-1,src,goal,mid);
        System.out.println(src + "——>" + goal);
        hanoi(n-1,mid,src,goal);
    }
    public static void main(String[] args){
        N = Integer.parseInt(args[0]);
        hanoi(N,'A','B','C');
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一“技”之长

iOS中第三方有序字典框架——M13OrderedDictionary

        M13OrderedDictionary是拥有字典和数组功能的第三方集合序列,开发者可以通过索引和键值来实现对其中元素的访问。其实现了NSArr...

4242
来自专栏非典型技术宅

iOS实践:一步步实现星级评分1. 创建星星2. 优化3. 灵异事件

1814
来自专栏Java与Android技术栈

当RxJava遇到AOP

公司打算开发一款全新的To C产品,因此我开始做一些搭建框架的事儿以及POC。新的产品能够使用一些比较新的技术,在新产品中我大量使用了Rx。这就导致了原先的AO...

952
来自专栏一个会写诗的程序员的博客

【Kotlin 反应式编程】第1讲 你好,Reactive Programming

【Kotlin 反应式编程】第1讲 你好,Reactive Programming

872
来自专栏木宛城主

PowerShell 获取Site Collection下被签出的文件

由于权限的设置,当文件被签出时导致别人不可见了,这对校验文件个数的人来说着实是件烦恼的事。幸好利用PowerShell,可以获取Site Collection下...

2027
来自专栏Spark生态圈

[Spark SQL] 源码解析之Optimizer

optimizer 以及之后的模块都只会在触发了action操作后才会执行。优化器是用来将Resolved LogicalPlan转化为optimized Lo...

1042
来自专栏函数式编程语言及工具

FunDA(9)- Stream Source:reactive data streams

    上篇我们讨论了静态数据源(Static Source, snapshot)。这种方式只能在预知数据规模有限的情况下使用,对于超大型的数据库表也可以说是不...

20910
来自专栏androidBlog

装饰者模式及其应用

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

3132
来自专栏大内老A

ASP.NET MVC的Model元数据与Model模板:将”ListControl”引入ASP.NET MVC

我们不仅可以创建相应的模板来根据Model元数据控制种类型的数据在UI界面上的呈现方法,还可以通过一些扩展来控制Model元数据本身。在某些情况下通过这两者的结...

3696
来自专栏算法+

声音变调算法PitchShift(模拟汤姆猫) 附完整C++算法实现代码

上周看到一个变调算法,挺有意思的,原本计划尝试用来润色TTS合成效果的。 实测感觉还需要进一步改进,待有空再思考改进方案。 算法细节原文,移步链接: http:...

60610

扫码关注云+社区

领取腾讯云代金券