1、漢諾塔問題教師：天津市南開中學(xué)濱海生態(tài)城學(xué)校 鄧彩紅中國地圖出版社 選修1 算法與程序設(shè)計 第三單元第三節(jié) 樊塔問題找一找三幅圖片有什么相同的地方？圖片調(diào)用規(guī)模由小到大的自身火眼金睛生活中有沒有這樣的實例呢？任務(wù)1小試牛刀請一位同學(xué)挑戰(zhàn)移動三個盤子a柱子上從下到上按金字塔狀疊放著n個不同大小的圓盤，現(xiàn)在把所有圓盤一個一個移動到柱子c上，可以借助 b 柱，但是每次移動同一根柱子上只能出現(xiàn)小盤子在大盤子上方abc任務(wù)2請兩位同學(xué)挑戰(zhàn)移動四個盤子任務(wù)3請獲勝同學(xué)挑戰(zhàn)移動五個盤子有什么簡單的方法可以完成任務(wù)呢？有什么簡單的方法可以完成把4個圓盤從A柱移到C柱的任務(wù)呢？ 先請A同學(xué)將前三個圓盤從A柱移到

2、B柱。 我將第四個圓盤從A柱移到C柱。 再請A同學(xué)將前三個圓盤從B柱移到C柱。我不需要知道如何移動三個圓盤，只需要完成最簡單的移動一個圓盤即可。古老傳說相傳在印度婆羅門神廟內(nèi)的有一塊黃銅板上插著三根鉆石棒，印度的主神梵天在創(chuàng)造世界的時候，在其中一根鉆石棒上按從大到小的順序放了枚純金的圓盤。一個叫婆羅門的僧人，不分日夜地將枚金盤移到另一根鉆石棒上，移動的過程中一次只能移動一個金盤，且大盤不能放在小盤上。神說等到婆羅門完成這項工作，世界將在一聲霹靂中毀滅 計算機(jī)如何解密傳說？1 分析問題傳說解密2 畫流程圖3 編寫代碼4 檢測結(jié)果1 分析問題傳說解密2 畫流程圖3 編寫代碼4 檢測結(jié)果 待選區(qū) 繪

3、圖區(qū)1 分析問題傳說解密2 畫流程圖3 編寫代碼4 檢測結(jié)果#編寫程序要求：#根據(jù)每條語句的解釋，將語句中的下劃線“_”替換為正確的語句代碼def move(n,A,B,C): # 定義move(n,A,B,C)函數(shù)：將n個圓盤從A柱借助B柱移到C柱 if =1: #判斷A柱上是否只有一個圓盤 print(移動一個圓盤從,A,到,C) else: move(n-1,A,C,B) #將A柱前（n-1）個圓盤借助C柱移到B柱 move(1, , , ) #將A柱最底下的1個圓盤借助B柱移到C柱 move( , , , ) #將B柱上的（n-1）個圓盤借助A柱移到C柱move( , , , ) #調(diào)

4、用move(n,A,B,C)函數(shù)，將4個圓盤從a柱借助b柱移到c柱nABCn-1BAC4abc函數(shù)本身調(diào)用三次1 分析問題傳說解密2 畫流程圖3 編寫代碼4 檢測結(jié)果010203適用條件遞歸法通過重復(fù) 將問題分解為同類的子問題 而解決問題的方法可以把要解決的復(fù)雜問題分解為一個規(guī)模較小的簡單問題。簡單問題的解決方法與復(fù)雜問題的解決方法相同，當(dāng)簡單問題的規(guī)模小到一定程度就能很容易的解決。遞歸法不能永無止境的調(diào)用下去。結(jié)束條件：圓盤個數(shù)為0。求年齡有5個人坐在一起，第五個人比第4個人大2歲，第四個人比第3個人大2歲，第三個人比第2人大兩歲，第2個人比第一個人大兩歲，第一個人10歲。求第五個人多大？求階乘已知N!=1*2*3*.*(N-1)*N，1！=1求6！為多少？一個密碼箱的密碼為4位數(shù)字，只記得第一位是2，求密碼箱的密碼？學(xué)以致用010203密碼破譯 求階乘 求年齡獲取謎底f（n）為移動n個盤子的最少步數(shù)， 則有： f（1）=1 f（n）=2f（n-1）+1根據(jù)數(shù)學(xué)推導(dǎo)我們可以得出： f（n）=2n-1，僧人要移動64個盤子，每移動一次需要一秒，不眠不休他最短多長時間內(nèi)能