河內塔遊戲

                                       校名:翠屏國中

                                   指導老師:林菁蓉、黃景良

一、旨趣:藉由動手操作過程中,訓練學生探究推理及構思的能力。

二、實驗器材:三根柱子,四個大小規格不同的圓盤。

三、活動過程:1.大盤在下,小盤在上。每次只能移動一個圓盤。

2.將套在一根柱子的圓盤全部移至另一根柱子上的最少次數。

3.先挑戰移動放3個圓盤的柱子,再挑戰放4個圓盤的柱子,2者皆挑戰成功者過關。

四、原理探討:相傳在創世紀時代,河內(Hanoi)的一座寺廟裡堅立著三根銀棒,有64個大小都不同的金盤(金盤正中央有一小孔)大盤在下、小盤在上’’依序套在同一根銀棒上,造物主命僧侶把64個金盤全部移到另一根銀棒上,並且規定:每一次只能移動一個金盤,在移動的過程中,較大的金盤不可套在較小的金盤上,當金盤全部搬完,世界末日將降臨,忠誠者得到好報,不忠者受到懲罰。同學們可依活動過程推論一下世界末日何時來臨?利用「數學歸納法」及「遞迴關係式」。

五、推廣:若遊戲規則上在加註規則每次移動圓盤僅能將圓盤移動至旁邊位置,不可跳著移動,則最少移動次數?

 

                 河內塔解析            /翠屏國中/

(一)實驗

假設f(n)表示n個圓盤,依原來的排列次序全部移至另一根小木條上,所需最少次數,則:

f1)=1

f2)=3 (如圖操作模式)

 

 

 

                                                                        

   

 

開始                一次                  二次                   三次

 

 f(3)= ?

 我們來操作看看:

 

 

 


 

                                 

 

開始                一次                   二次                三次

 

 


 

 

 

 


四次(移動大盤一次)       五次                   六次                 七次

 

由上圖知,移動3個圓盤所需的最少次數為

f(3)= f(2)+ 1+ f(2)               

= 2 f(2) + 1                         

= 2 ×3 + 1 = 7

因此最少為7次 

 

 

 

f(4) =?

我們來操作看看:  

                      

     

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


由上圖知,移動4個圓盤所需的最少次數為

f(4)= f(3)+ 1+ f(3)               

= 2 f(3) + 1                         

= 2 ×7 + 1 = 15

因此最少為15次 

(二)推導:

步驟(一):把上面3個金盤全數移到第二根上(由上知,最少需f(3)次)

步驟(二):把最底下的大金盤移到第三根上(需1次)

步驟(三):把第二根的3個金盤全數移到第3根上(最少需f(3)次)

所以f(4)=f(3)+1+f(3)=2f(3)+1=2*7+1=15

(三)推論:

仿(二)的推

f(n)=f(n-1)    +   1    + f(n-1)  = 2f(n-1)+1

 


步驟(一) 步驟(二)  步驟(三)

 

因此可得<<f(n)>>的遞迴式:  f(1)=1       (起始值)

                           f(n)=2f(n-1)+1(遞迴關係式)            (A)

(四)結論:

利用遞迴關係式算式:

f(1)=1

f(2)=2f(1)+1=3

f(3)=2f(2)+1=7

f(4)=2f(3)+1=15

觀察前幾項,我們推測 f(n)=-1

現在用數學歸納法證明:

滿足(A)是之f(n)必為f(n)=-1(n=123

(i)                  n=1f(1)=-1=1 所以,當n=1時,f(n)=-1成立。

(ii)                n=k時,f(k)=-1成立,則由遞迴關係式知:

f(k+1)=2f(k)+1=2(-1)+1=-1

所以n=k+1時,f(n)=-1也成立。

由數學歸納法知:f(n)=-1對n=123都成立。

 

因此,將64個金盤移到另一根銀棒上,最少需搬-1次。

如果一次移動費時1秒,整個工程需費時18,446,744,073,709,551,615 秒,

這個世界似乎還蠻安全的!

 

 

 

 

 

 

 

 

/翠屏國中/