递回关系-河内塔.ppt

《递回关系-河内塔.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、遞迴關係－河內塔(河內塔問題)相傳在創世紀時代，河內(Hanoi)的一座寺廟裡豎立者三根銀棒，有六十四個大小都不同的金盤(金盤正中央有一小孔)”大盤在下，小盤在上”依序套在同一根銀棒上。問題2問題2(河內塔問題)造物主命僧侶把64個金盤全部移到另一根銀棒上，並且規定：每一次只能移動一個金盤，在移動的過程中，較大的金盤不可套在較少的金盤上。當金盤全數搬完，世界末日將降臨，忠誠者得到好報，不忠者受到懲罰。試問搬完64個金盤最少需多少次?移動最少次數次移動最少次數次(河內塔問題)問題37153163移動最少次數次移動最少次數

2、次(河內塔問題)3個金盤為例移動1次移動1次移動1次移動1次移動1次移動1次移動1次(河內塔問題)4個金盤為例移動7次移動1次移動7次(河內塔問題)問題3金盤數n123456…次數an137153163設an代表搬完n個金盤所需的最少次數，列表計算，仔細觀察、歸納：建立遞迴關係式：如圖所示，根據搬動的規則，先將A棒上面n－1個金盤先搬到銀棒B上，則需要搬動an－1次。再將A棒上面最底的第n個金盤搬到銀棒C上，則需要搬動1次。最後再將B棒上的n－1個金盤搬到銀棒C上，則亦需要搬動an－1次。an＝an－1＋1＋an－1所以合計搬完

3、n個金盤所需的最少次數遞迴關係式an=2an1+1，其中a1=1請按我可以再請按我某些與自然數有關的問題，往往隱含固定的規律，處理這一類的問題通常分成三個步驟：依據題設條件構造一個數列an建立相鄰項間的遞迴關係(亦稱為遞迴方程式)解遞迴方程式，求出一般項an(用n表示)an代表搬完n個金盤所需的最少次數，問題3遞迴關係式an＝2an－1＋1其中a1＝1當金盤全數搬完，世界末日將降臨，忠誠者得到好報，不忠者受到懲罰。試問搬完64個金盤最少需多少次?a64＝2a63＋1＝2(2a62＋1)＋1＝22(2a61＋1)＋2＋1＝23

4、(2a60＋1)＋22＋2＋1……＝263＋262＋…＋23＋22＋2＋1＝264－1＝18,446,744,073,709,551,615一般項an＝2n－1假設移動一次花了一秒，將六十四層塔全部移到另一底盤，總共需移動a64次，需a64秒，而a64=264-1=18,446,744,073,709,551,615秒，約需58萬億年。