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

相关文章

来自专栏跟着阿笨一起玩NET

C# 通过HttpWebRequest在后台对WebService进行调用

http://www.cnblogs.com/macroxu-1982/archive/2009/12/23/1630415.html

1082
来自专栏专知

【Leetcode235】关关的刷题日记66 –Lowest Common Ancestor of a BST

关关的刷题日记66 – Leetcode 235 Lowest Common Ancestor of a Binary Search Tree 题目 ? 题目的...

2498
来自专栏GIS讲堂

点图层叠加与事件响应

用过百度地图的童鞋一定很羡慕百度地图POi的展示,地图切片+事件响应,以前一直在考虑这个问题,今天,将我的思考结果做一个汇报给大家。下面,将我的实现思路说明一下...

803
来自专栏JetpropelledSnake

Python实现简单的三级菜单

话不多说,直奔代码 # 要处理的字典 dic1 = { '北京': { '东城': { ...

4709
来自专栏与神兽党一起成长

在XMLSignature中使用BouncyCastle做RSA

There is an article shows demo code for making XMLSignature by using Java XML Di...

632
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

1182
来自专栏码匠的流水账

聊聊sentinel的SimpleHttpCommandCenter

sentinel-transport-simple-http-0.1.1-sources.jar!/com/alibaba/csp/sentinel/trans...

481
来自专栏有刻

Java 小记 - 时间的处理与探究

时间的处理与日期的格式转换几乎是所有应用的基础职能之一,几乎所有的语言都会为其提供基础类库。作为曾经 .NET 的重度使用者,赖其优雅的语法,特别是可扩展方法这...

1495
来自专栏林德熙的博客

Visual studio C# 代码使用 NotNull

我们经常看到有代码使用 NotNull 特性,这时如果我们输入可空参数,Resharper 就会告诉我们,输入了空参数。

1001
来自专栏码匠的流水账

聊聊springboot session timeout参数设置

本文主要介绍下spring boot中对session timeout参数值的设置过程。

2372

扫码关注云+社区