一、單Hanoi塔

image.png

上圖為 3 階 Hanoi 塔

假設(shè)有三個(gè)命名為 A B C 的塔座 ，在塔座A上插有n個(gè)直徑大小不相同，由小到大編號(hào)為1 ，2 ，3 ，··· ，n的圓盤，要求將A座上的圓盤移至塔座C

并按同樣的順序疊排

圓盤移動(dòng)必須遵守下列規(guī)則：

1、每次只能移動(dòng)一個(gè)圓盤 。
2、圓盤可以插在任意一個(gè)塔座上 。
3、任何時(shí)刻都不能將一個(gè)較大的圓盤放在一個(gè)較小的圓盤上。
問把所有的圓盤從A柱移動(dòng)到C柱總計(jì)需要多少次移動(dòng)？

一種遞歸的求解方法是分三步解決這個(gè)問題。
第一步：使用同樣的方法將n-1個(gè)盤子從A柱移動(dòng)到B柱；
第二步：利用1次移動(dòng)將最下面的大盤子從A柱移動(dòng)到C柱；
第三步：還是用第一步的方法將B柱上的n-1個(gè)盤子移到C柱，用偽碼描述如下：

算法：Hanoi(A,C,n)

1.   if n=1 then move(A,C)
   

2.  else Hanoi(A,B,n-1)
   

3.         move(A,C)
   

4.         Hanoi(B,C,n-1)
   

使用這個(gè)算法，設(shè)總的移動(dòng)次數(shù)為T(n)，行2與行4有兩次遞歸調(diào)用，每次調(diào)用的輸入實(shí)例規(guī)模是n-1，因此移動(dòng)次數(shù)為T(n-1)，行3有1次移動(dòng)，從而得到如下遞推方程：
T(n) = 2 T(n-1) + 1
初值 T(1) = 1
T(n) = 2 T(n-1) + 1
T(n-1) = 2 T(n-2) + 1
......
T(2) = 2 T
T(1) = 1

T(n) = 2( 2 T(n-2) +1 ） + 1 = 2 2 T(n-2) + 2 + 1 = 2^(n-1) T(1) + 1 = 2^(n-1) + 1
所以移動(dòng)次數(shù)為2^(n-1) + 1次

二、雙Hanoi塔
雙Hanoi塔問題是Hanoi塔問題的一種推廣，與Hanoi塔的不同點(diǎn)在于：2n個(gè)圓盤，分成大小不同的n對(duì)，每對(duì)圓盤完全相同。初始，這些圓盤按照從大到小的次序從下到上放在A柱上，最終要把他們?nèi)恳频紺柱，移動(dòng)的規(guī)則與Hanoi塔相同。
（1）設(shè)計(jì)一個(gè)移動(dòng)的算法并給出偽碼描述。
（2）計(jì)算你的算法所需要的移動(dòng)次數(shù)。

解：
（1）算法設(shè)計(jì)思想：分治策略。先遞歸地將上面的2(n-1)個(gè)盤子從A柱移動(dòng)到B柱；用2次移動(dòng)將最大的2個(gè)盤子從A柱移動(dòng)到C柱；遞歸地將B柱的2(n-1)個(gè)盤子從B柱移動(dòng)到C柱。
偽碼描述是：
BiHanoi(A,C,n) //從A到C移動(dòng)2n只盤子

1. if n=1 then BiMove(A,C)     //從A到C移動(dòng)2只盤子
   

2. else BiHanoi(A,B,n-1)
   

3.      BiMove(A,C)
   

4.      BiHanoi(B,C,n-1)
   

（2）設(shè)2n個(gè)盤子的移動(dòng)次數(shù)是T(n),則第2行和第4行的遞歸調(diào)用的子問題規(guī)模是n-1，第3行是2次移動(dòng)，于是有
T (n) = 2 T(n-1) + 2
T(1) = 2
解得 T(n) = 2^(n+1) -2