思路: 這里使用遞回法
n==1的時候，直接把它從x移到z位置即可，
如果是n層，我們首先把上面的n- 1層移到y位置,然后把最 下面的那個最大的盤子，移到z位置,然后把y上面放的上面n-1層移到z位置即即可，
我們在移動上面n-1層盤子的時候，先把上面n-2層移到z位置,然后把第n- 1層那個最大的放到y位置,然后把z上面的n-2層移到y位置即可，
我們在移動上面n-2層盤子的時候，先把上面n- 3層移到y位置,然后把最大的那個第n- 2層移到z位置,然后把y上面放的n- 3層放到z位置即可，
我們在移動上面n-3層盤子的時候，........... .遞回就完事了!
我們在移動上面2層盤子的時候，首先把上面那個放到y(z)上面,然后把第二層放到z(y)上面，再把y(z) 上面的那一層移到z(y)上面即可，我們在移動上面那一層的時候，n==1
由遞推方程的知識可知，該程序的時間復雜性為O(2^n)，64層就要移動2^64-1次盤子，不過這次我們使用程式觀察這個變化
這個程式記錄了1到36個盤子的時候，Hanoi tower的移動次數，執行時間，為了保證效率，不列印中間結果，只列印最終結果
public class Hanoi {
/**
* author:ZhaoKe
* college: CUST
*/
public long count = 0; public void hanoi(int n,char a,char b,char c) {
//Hanoi塔問題其實就這幾行 if (n == 1) { this.count++; }else { this.hanoi(n-1, a, c, b); this.count++; this.hanoi(n-1, b, a, c); } } public static void main(String[] args) {
//程式看起來挺長，大部分代碼都是為計算時間服務的 Hanoi ha = new Hanoi(); long begin = System.currentTimeMillis(); //獲得當前系統時間 long end = begin; //回圈之前，這里end作為上一輪回圈的結束時間，雖然回圈還沒開始 for (int i = 1; i <= 36; i++) { ha.count = 0; //回圈開始，執行次數置0 begin = end; //回圈開始，起始時間是上一輪回圈的結束時間 ha.hanoi(i, 'a', 'b', 'c'); //其實Hanoi塔問題只要這一句就夠了，其他陳述句都是為了計算運行時間 end = System.currentTimeMillis(); //程式結束時間 System.out.println(i+"個盤子，一共有" +ha.count+ "步"); System.out.println("程式運行時間：" + (end - begin) + " ms"); //程式運行時間，單位毫秒ms } } }
運行結果是怎樣的呢？
前面盤子比較少的時候就省略了，運行時間都小于1ms，程式顯示基本為0ms，
程式運行時間：14 ms 24個盤子，一共有16777215步 程式運行時間：15 ms 25個盤子，一共有33554431步 程式運行時間：66 ms 26個盤子，一共有67108863步 程式運行時間：68 ms 27個盤子，一共有134217727步 程式運行時間：238 ms 28個盤子，一共有268435455步 程式運行時間：239 ms 29個盤子，一共有536870911步 程式運行時間：914 ms 30個盤子，一共有1073741823步 程式運行時間：973 ms 31個盤子，一共有2147483647步 程式運行時間：3681 ms 32個盤子，一共有4294967295步 程式運行時間：3887 ms 33個盤子，一共有8589934591步 程式運行時間：14602 ms 34個盤子，一共有17179869183步 程式運行時間：15504 ms 35個盤子，一共有34359738367步 程式運行時間：58773 ms 36個盤子，一共有68719476735步 程式運行時間：61197 ms
可見十分恐怖了，
對照一下列印中間結果多么消耗性能，這里只列印最終結果：
如果將執行的每一步都列印出來的話(使用System.out.println("........."))，n=26的時候就使用了427009ms，比如
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71868.html
標籤：其他
上一篇：哈希表和碰撞演算法