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 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊pg jdbc的queryTimeout及next方法

本文主要介绍一下pg jdbc statement的queryTimeout及resultSet的next方法

2631
来自专栏Spark生态圈

[Spark SQL] 源码解析之Optimizer

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

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

FunDA(9)- Stream Source:reactive data streams

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

20610
来自专栏Java与Android技术栈

Scrypt 不止是加密算法,也是莱特币的挖矿算法

Scrypt不仅计算所需时间长,而且占用的内存也多,使得并行计算多个摘要异常困难,因此利用rainbow table进行暴力攻击更加困难。Scrypt 没有在生...

1294
来自专栏木宛城主

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

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

1937
来自专栏后端之路

源码解析之ConcurrentHashMap

前言 相信有并发经验的小伙伴对于ConcurrentHashMap不会陌生。 上一篇我们描述了cow容器 cow容器之CopyOnWriteArrayList,...

3715
来自专栏大内老A

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

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

3486
来自专栏一英里广度一英寸深度的学习

SparkSQL 电影评价数据分析

Dataset调用createOrReplaceTempView生成临时表,session内有效。 spark.sql执行sqll操作,可以选择创建的临时表。

1593
来自专栏非典型技术宅

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

1544
来自专栏androidBlog

装饰者模式及其应用

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

1862

扫码关注云+社区