河内塔(Tower of Hanoi).ppt

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,數學遊戲一,河內塔,(,Tower of Hanoi,),河內塔,(,Tower of Hanoi,),法國數學家,Edouard,Lucas,在,1883,年所提出,傳說在古老的印度，有一座神廟，據說它是宇宙的中心。在廟宇中放置了一塊上面插有三根長木樁的木板，在其中的一根木樁上，從上至下被放置了,64,片直徑由小至大的盤子。古印度教的天神指示祂的僧侶們將,64,片的盤子移至三根木樁中的其中一根上。它們可以根據底下的規則由一個位置搬移到另外一個位置：,一次只能移動一個盤子。,大盤子永遠不能放在小盤子的上面。,這一疊盤子可以藉由另外一根木樁移到另外一個位置。,直到有一天，僧侶們能將,64,片的盤子依規則從指定的木樁上全部移動至另一根木樁上，那麼，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界,！,河內塔,(Tower of Hanoi),移動盤子,1,從木樁,A,到木樁,B,移動盤子,2,從木樁,A,到木樁,C,移動盤子,1,從木樁,B,到木樁,C,總共需要,3=2,2,-1,次,N=2,1.,2.,3.,A,B,C,河內塔,(,Tower of Hanoi,),移動盤子,1,從木樁,A,到木樁,C,移動盤子,2,從木樁,A,到木樁,B,移動盤子,1,從木樁,C,到木樁,B,移動盤子,3,從木樁,A,到木樁,C,移動盤子,1,從木樁,B,到木樁,A,移動盤子,2,從木樁,B,到木樁,C,移動盤子,1,從木樁,A,到木樁,C,總共需要,7=2,3,-1,次,N=3,1.,2.,3.,4.,5.,6.,7.,A,B,C,河內塔,(,Tower of Hanoi,),規律（假設,A,是來源木樁，,C,是目的木樁，,B,是暫時存放的木樁）,先將,1,至,(n-1),號盤子,從,A,經由,C,搬至,B,將第,n,號盤子由,A,搬至,C,再將,1,至,(n-1),號盤子,從,B,經由,A,搬至,C,亦即將搬,n,個盤子的動作分解成三大步,第一步,搬動,n-1,個盤子,第二步 搬動一個盤子（第,n,個）,第三步 搬動,n-1,個盤子,河內塔,(Tower of Hanoi),最少搬動次數為何,?,假設至少須,T(n,),次的移動來完成,最少的總移動次數,T(n,)=T(n-1)+1+T(n-1),T(n,),=2,n,-1,搬動,64,個盤子需要的次數,2,64,-1,=18,446,744,073,709,551,615,1.84x10,19,若每秒搬一次，則總共需,584,942,417,355,年，大約是,5850,億年，這是非常非常遙遠的事，科學家估計地球約已存在,2,000,000,000,年，也沒有一種生物能活這麼久，所以我們大可放心的睡覺。,