數據結構考研分類復習真題 第三章 答案[7]

　　設Hn為n個盤子的Hanoi塔的移動次數(假定n個盤子從鋼針X移到鋼針Z可借助鋼針Y)
　　則  Hn =Hn+  //先將n個盤子從X移到Y第n個盤子移到Z再將那n個移到Z
　　=（Hn+）+
　　= Hn++
　　=（Hn+）++
　　= Hn+++
　　·
　　·
　　·
　　= k Hnk+k +k +…+ +
　　=n H+n+n+…++
　　因為H=所以原式Hn=n+n+…++=n
　　故總盤數為n的Hanoi塔的移動次數是n

　　運行結果為            （注運行結果是每行一個數為節省篇幅放到一行）

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22715.html