种豆资源网
当前位置：首页 > 百科 > 百科综合 / 正文

汉诺塔(益智玩具)

(2019-05-08 03:10:44) 百科综合
汉诺塔(益智玩具)

汉诺塔(益智玩具)

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

基本介绍

  • 中文名称：汉诺塔
  • 外文名称：Tower of Hanoi
  • 又称：河内塔

由来及传说

由来

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，
假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：
18446744073709551615秒
这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

印度传说

和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏西洋棋的发明人──宰相西萨·班·达依尔。国王问他想要什幺，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的僕人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。
那幺，宰相要求得到的麦粒到底有多少呢？总数为
1+2+2^2 + … +2^63=2^64-1
等于移完汉诺塔所需的步骤数。我们已经知道这个数字有多幺大了。人们估计，全世界两千年也难以生产这幺多麦子！

相关预言

有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。

其他相关

宇宙寿命

如果移动一个圆盘需要1秒钟的话，等到64个圆盘全部重新落在一起，宇宙被毁灭是什幺时候呢？
让我们来考虑一下64个圆盘重新摞好需要移动多少次吧。1个的时候当然是1次，2个的时候是3次，3个的时候就用了7次......这实在是太累了
因此让我们逻辑性的思考一下吧。
3个的时候能够移动最大的3盘时如图所示。
到此为止用了7次。
汉诺塔(益智玩具)
接下来如右图，在上面再放上3个圆盘时还要用7次（把3个圆盘重新放在一起需要的次数）。
因此，4个的时候是
“3个圆盘重新摞在一起的次数”+1次+“3个圆盘重新摞在一起需要的次数”
=2x“3个圆盘重新摞在一起的次数”+1次
=15次。
那幺，n个的时候是
2x“（n-1）个圆盘重新摞在一起的次数”+1次。
由于1 个的时候是1次，结果n个的时候为（2的n次方减1）次。
1个圆盘的时候 2的1次方减1
2个圆盘的时候 2的2次方减1
3个圆盘的时候 2的3次方减1
4个圆盘的时候 2的4次方减1
5个圆盘的时候 2的5次方减1
........
n个圆盘的时候 2的n次方减1
也就是说，n=64的时候是（2的64次方减1）次。
因此，如果移动一个圆盘需要1秒的话，
宇宙的寿命=2的64次方减1（秒）
2的64次方减1到底有多大呢？动动计算器，答案是一个二十位的数字约是
1.84467440*10^19
用一年=60秒x60分x24小时x365天来算的话，大约有5800亿年吧。
太阳及其行星形成于50亿年前，其寿命约为100亿年。
汉诺塔问题在数学界有很高的研究价值，而且至今还在被一些数学家们所研究。
也是我们所喜欢玩的一种益智游戏，它可以帮助开发智力，激发我们的思维。

经典题目

有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n）。
首先我们肯定是把上面n-1个盘子移动到柱子C上，然后把最大的一块放在B上，最后把C上的所有盘子移动到B上，由此我们得出表达式：
H⑴ = 1
H(n) = 2*H(n-1）+1 (n>1）
那幺我们很快就能得到H(n）的一般式：
H(n) = 2^n - 1 (n>0)
并且这种方法的确是最少次数的，证明非常简单，可以尝试从2个盘子的移动开始证，你可以试试。
进一步加深问题（解法原创*_*）：
假如现在每种大小的盘子都有两个，并且是相邻的，设盘子个数为2n，问：⑴假如不考虑相同大小盘子的上下要多少次移动，设移动次数为J(n）；⑵只要保证到最后B上的相同大小盘子顺序与A上时相同，需要多少次移动，设移动次数为K(n）。
⑴中的移动相当于是把前一个问题中的每个盘子多移动一次，也就是：
J(n) = 2*H(n) = 2*（2^n - 1） = 2^(n+1）-2
在分析⑵之前
，我们来说明一个现象，假如A柱子上有两个大小相同的盘子，上面一个是黑色的，下面一个是白色的，我们把两个盘子移动到B上，需要两次，盘子顺序将变成黑的在下，白的在上，然后再把B上的盘子移动到C上，需要两次，盘子顺序将与A上时相同，由此我们归纳出当相邻两个盘子都移动偶数次时，盘子顺序将不变，否则上下颠倒。
现在回到最开始的问题，n个盘子移动，上方的n-1个盘子总移动次数为2*H(n-1），所以上方n-1个盘子的移动次数必定为偶数次，最后一个盘子移动次数为1次。
讨论问题⑵，
综上两点，可以得出，要把A上2n个盘子移动到B上，首先可以得出上方的2n-2个盘子必定移动偶数次，所以顺序不变，移动次数为：
J(n-1） = 2^n-2
然后再移动倒数第二个盘子，移动次数为2*J(n-1）+1 = 2^(n+1）-3，
最后移动最底下一个盘子，所以总的移动次数为：
K(n) = 2*（2*J(n-1）+1）+1 = 2*（2^(n+1）-3）+1 = 2^(n+2）-5
开天闢地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖（移动圆片的次数）大约是1.84467440*10^19，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。

算法介绍

其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n – 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B。
⑴按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
⑵接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较大的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
⑶反覆进行⑴⑵操作，最后就能按规定完成汉诺塔的移动。
所以结果非常简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
汉诺塔问题也是程式设计中的经典递归问题，下面我们将给出递归和非递归的不同实现原始码。

程式实现

Python

def hanoi(n, a, b, c):    if n == 1:        print(a, '-->', c)    else:        hanoi(n - 1, a, c, b)        print(a, '-->', c)        hanoi(n - 1, b, a, c)# 调用hanoi(5, 'A', 'B', 'C')

C语言

#include <stdio.h>#include <windows.h>void Hanoi(int n, char a,char b,char c);void Move(int n, char a, char b);int count;int main(){    int n=8;    printf("汉诺塔的层数:\n");    scanf(" %d",&n);    Hanoi(n, 'A', 'B', 'C');    Sleep(20000);    return 0;}void Hanoi(int n, char a, char b, char c){    if (n == 1)    {        Move(n, a, c);    }    else    {        Hanoi(n - 1, a, c, b);        Move(n, a, c);        Hanoi(n - 1, b, a, c);    }}void Move(int n, char a, char b){    count++;    printf("第%d次移动 Move %d: Move from %c to %c !\n",count,n,a,b);}
FORTRAN
 C HANOI LIST      PROGRAM MAIN        INTEGER N        PRINT *, "ENTER THE AMOUNT OF STEP:"        READ *, N        CALL HANOI(N,'A','B','C')      END      RECURSIVE SUBROUTINE HANOI(N,START,STATION,AIM)        INTEGER N        CHARACTER :: START, STATION, AIM        IF (N.EQ.1) THEN          CALL MOVE(START,AIM)        ELSE          CALL HANOI(N-1,START,AIM,STATION)          CALL MOVE(START,AIM)          CALL HANOI(N-1,STATION,START,AIM)        END IF      END SUBROUTINE      SUBROUTINE MOVE(START, AIM)        CHARACTER :: START, AIM        PRINT *, START, " -> ", AIM      END SUBROUTINE
汉诺塔问题的非递归实现
#include<stdio.h>#include<math.h>#include<stdlib.h>//第0位置是柱子上的塔盘数目intzhua[100]= {0},zhub[100]= {0},zhuc[100]= {0};charcharis(charx,intn)//左右字元出现顺序固定，且根据n值奇偶尔不同{    switch(x)    {    case'A':        return(n%2==0)?'C':'B';    case'B':        return(n%2==0)?'A':'C';    case'C':        return(n%2==0)?'B':'A';    default:        return'0';    }}voidprint(charlch,charrch)//列印字元{    if(lch=='A')    {        switch(rch)        {        case'B':            zhub[0]++;            zhub[zhub[0]]=zhua[zhua[0]];            zhua[zhua[0]]=0;            zhua[0]--;            break;        case'C':            zhuc[0]++;            zhuc[zhuc[0]]=zhua[zhua[0]];            zhua[zhua[0]]=0;            zhua[0]--;            break;        default:            break;        }    }    if(lch=='B')    {        switch(rch)        {        case'A':            zhua[0]++;            zhua[zhua[0]]=zhub[zhub[0]];            zhub[zhub[0]]=0;            zhub[0]--;            break;        case'C':            zhuc[0]++;            zhuc[zhuc[0]]=zhub[zhub[0]];            zhub[zhub[0]]=0;            zhub[0]--;            break;        default:            break;        }    }    if(lch=='C')    {        switch(rch)        {        case'A':            zhua[0]++;            zhua[zhua[0]]=zhuc[zhuc[0]];            zhuc[zhuc[0]]=0;            zhuc[0]--;            break;        case'B':            zhub[0]++;            zhub[zhub[0]]=zhuc[zhuc[0]];            zhuc[zhuc[0]]=0;            zhuc[0]--;            break;        default:            break;        }    }    printf("\t");    inti;    printf("(");    for(i=1; i<=zhua[0]; i++)        printf("%d",zhua[i]);    printf(")");    printf("(");    for(i=1; i<=zhub[0]; i++)        printf("%d",zhub[i]);    printf(")");    printf("(");    for(i=1; i<=zhuc[0]; i++)        printf("%d",zhuc[i]);    printf(")");    printf("\n");}voidHannuo(intn){//分配2^n个空间    bool*isrev;    isrev=(bool*)malloc(sizeof(bool)*(int)pow（2,n));    for(inti=1; i<pow（2,n);i++)isrev[i]=false;//循环计算是否逆序for(intci=2; ci<=n; ci++){    for(intzixh=(int)pow（2,ci-1）；zixh<pow（2,ci);        zixh+=4）//初始值重複一次，自增值可加4，减少循环次数。              isrev[zixh]=isrev[(int)pow（2,ci)-zixh];//该位置为中间位置，且奇次幂逆序，偶数幂不逆序        isrev[(int)pow（2,ci)]=((ci-1）%2==0)?false:true;    }                            charlch='A',rch;    rch=(n%2==0?'B':'C');    printf("%d\t",1）；           printf("%c->%c",lch,rch);    print(lch,rch);    for(intk=2; k<pow（2,n); k++){    if(k%2==0)            rch=charis(lch,n);        else            lch=charis(rch,n);        printf("%d\t",k);        if(isrev[k])        {            printf("%c->%c",rch,lch);            print(rch,lch);        }        else        {            printf("%c->%c",lch,rch);            print(lch,rch);        }    }}intmain(){    intn;    printf("Inputthenum:");    scanf("%d",&n);    zhua[0]=n;    for(inti=1; i<=n; i++)        zhua[i]=n-i+1;    Hannuo(n);    return0;}
汉诺塔汉诺塔

递归

#include <iostream>using namespace std; template<int n>                                void hanoi(char a, char b, char c){    hanoi<n - 1>(a, c, b);    printf("%c -> %c\n", a, c);    hanoi<n - 1>(b, a, c);}template<>void hanoi<1>(char a, char b, char c){    printf("%c -> %c\n", a, c);}////////////////////////////////////////////////template<int n, char a, char b, char c>    class hanoi1{public:    static int hanoi(){        hanoi1<n-1, a, c, b>::hanoi();        printf("%c -> %c\n", a, c);        hanoi1<n-1, b, a, c>::hanoi();    }};template<char a, char b, char c>class hanoi1<1, a, b ,c>{public:    static int hanoi(){        printf("%c -> %c\n", a, c);    }};int main(){     #define N 4    cout<<"类模板偏特化：";    hanoi1<N,'A','B','C'>::hanoi();    cout<<endl;        cout<<"函式模板全特化：";    hanoi<3>('A','B','C');     exit(0);}

C#

using System;class HANOI{    private static int time = 0;    static void Main(string[] args)    {        Hanoi(3, "x", "y", "z");        Console.WriteLine(time + " Times");        Console.ReadKey();    }    public static void Hanoi(int n, string x, string y, string z)    {        if (n == 1)        {            Console.WriteLine(x + "--->" + z);            time++;        }        else        {            Hanoi(n - 1, x, z, y);            Hanoi(1, x, y, z);            Hanoi(n - 1, y, x, z);        }    }}

Java

public class Hanoi {    /**    *     * @param n 盘子的数目    * @param origin 源座    * @param assist 辅助座    * @param destination 目的座    */    public void hanoi(int n, char origin, char assist, char destination) {        if (n == 1) {            move(origin, destination);        } else {            hanoi(n - 1, origin, destination, assist);            move(origin, destination);            hanoi(n - 1, assist, origin, destination);        }    }    // Print the route of the movement    private void move(char origin, char destination) {        System.out.println("Direction:" + origin + "--->" + destination);    }    public static void main(String[] args) {        Hanoi hanoi = new Hanoi();        hanoi.hanoi(3, 'A', 'B', 'C');    }}

php

简单的用php实现了汉诺塔问题的求解，使用递归调用，但是用php实现要是盘子的个数很多的话，运行起来会很慢的...
汉诺塔主要是有三个塔座X，Y，Z，要求将三个大小不同，依小到大编号为1，2.....n的圆盘从X移动到塔座Z上，要求
（1）：每次只能移动一个圆盘
（2）：圆盘可以插到X，Y，Z中任一塔座上
（3）：任何时候不能将一个较大的圆盘压在较小的圆盘之上
主要是运用了递归的思想，这里使用php做个简单的实现......
　<?php　function hanoi($n,$x,$y,$z){　    if($n==1){　        move($x,1,$z);　    }else{　        hanoi($n-1,$x,$z,$y);　        move($x,$n,$z);　        hanoi($n-1,$y,$x,$z);　    }　}　function move($x,$n,$z){　    echo'movedisk'.$n.'from'.$x.'to'.$z.'<br>';　}　hanoi(10,'x','y','z');　?>

pascal

var m:integer;procedure move(getone,putone:char);begin writeln(getone,'->',putone) end;procedure hanoi(n:integer;one,two,three:char);beginif n=1 then move(one,three) elsebeginhanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three)endend;beginreadln(m);write('the step to moving disks:');writeln;hanoi(m,'A','B','C')end.

Lua

function hanoi(num, a,b,c)  if (num == 1) then        print(a .."-->"..c)  else         hanoi(num-1, a,c,b)        print(a .."-->"..c)    hanoi(num-1, b,a,c)   endendhanoi(3,'A','B','C')

易语言

子程式 汉诺塔盘子运动
.参数 盘子数，整数型
.参数 柱子甲，文本型
.参数 柱子乙，文本型
.参数 柱子丙，文本型
.如果 （盘子数 = 1）
' 如果只有一个盘，则直接将它从柱子一移动到柱子三
移动 （1，柱子甲，柱子丙）
.否则
' 把1 ~ n - 1个盘从柱子一移动到柱子二，用柱子三作为中转
汉诺塔盘子运动 （盘子数 － 1，柱子甲，柱子丙，柱子乙）
' 把第n个盘从柱子一移动到柱子三
移动 （盘子数，柱子甲，柱子丙）
' 把1 ~ n - 1个盘从柱子二移动到柱子三，用柱子一作为中转
汉诺塔盘子运动 （盘子数 － 1，柱子乙，柱子甲，柱子丙）
.如果结束
.子程式 移动
.参数 盘子号，整数型
.参数 甲柱子，文本型
.参数 乙柱子，文本型
路径 = 路径 + “步骤” + 到文本 （步骤） + “：” + “把” + 到文本 （盘子号） + “号圆盘从柱子 ” + 甲柱子 + “ 移动到” + 乙柱子 + “上 ” + #换行符
步骤 = 步骤 + 1
.子程式 _计算图形按钮_被单击
.局部变数 盘子总数，整数型
.局部变数 现在柱子，文本型
.局部变数 中间柱子，文本型
易语言--hanoi易语言--hanoi
.局部变数 目标柱子，文本型
' 把盘子编辑框.内容传给现在柱子
现在柱子 = 盘子编辑框.内容
' 把中间编辑框.内容传给中间柱子
中间柱子 = 中间编辑框.内容
' 把目标编辑框.内容传给目标柱子
目标柱子 = 目标编辑框.内容
.如果真 （到数值 （现在柱子） ≤ 0 或 到数值 （中间柱子） ≤ 0 或 到数值 （目标柱子） ≤ 0 或 到数值 （个数编辑框.内容） ≤ 0 或 到数值 （个数编辑框.内容） > 10）
信息框 （“柱子或圆盘数量只能是大于0小于10的数字！”，#错误图示，“出现错误了：”）
返回 ()
.如果真结束
盘子总数 = 到数值 （个数编辑框.内容）
结果编辑框.内容 = “”
路径 = “”
' 首次调用汉诺塔盘子运动 （）程式
汉诺塔盘子运动 （盘子总数，现在柱子，中间柱子，目标柱子）
结果编辑框.内容 = 路径
步骤 = 1

JavaScript

var hanoi=function(n,from,ass,to){  if(n>0){    hanoi(n-1,from,to,ass);    move(n,from,to);    hanoi(n-1,ass,from,to);  }}var move=function(n,from,to){ console.log("移动第"+n+"个从"+from+"到"+to);}hanoi(3,"A","B","C");

标 签：

搜索
随机推荐

Powered By 种豆资源网||