漢諾塔(益智玩具)

漢諾塔：漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著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

.局部變數 目標柱子，文本型

' 把盤子編輯框.內容傳給現在柱子

現在柱子 = 盤子編輯框.內容

' 把中間編輯框.內容傳給中間柱子

中間柱子 = 中間編輯框.內容

' 把目標編輯框.內容傳給目標柱子

目標柱子 = 目標編輯框.內容

.如果真 （到數值 （現在柱子） ≤ 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");