1. 首頁 > 生活百科 > >

二級結論高中數學 遞歸數列( 二 )

越眾創業網


1.首先，n-1個磁盤在C的幫助下成功地從A移動到B2，然后第n個磁盤從A移動到C3，最后，n-1個磁盤在A的幫助下成功地從B移動到C
那么如何編寫代碼呢？我們知道這個函數 。
Hanoi(n，' A '，' B '，' C ')表示N個圓盤通過B成功地從A移動到C 。
所以hanoi(n-1，' A '，' C '，' B ')的意思是n-1個磁盤在C的幫助下成功地從A移動到B 。
Hanoi(n-1，' B '，' A '，' C ')表示n-1個磁盤通過A成功地從B移動到C 。
所以上面的三個步驟可以用這樣的代碼來表達 。
1，hanoi(n-1，' A '，' C '，' B')2，System.out.println("從"+A+"移動到"+C ")；3，河內(n-1，“B”，“A”，“C”)
所以最終完整的代碼如下
1//表示的是把n個圓盤借助柱子B成功的從A移動到C2publicstaticvoidhanoi(intn,charA,charB,charC){3if(n==1){4//如果只有一個，直接從A移動到C即可5System.out.println("從"+A+"移動到"+C);6return;7}8這里是遞歸調用9}//表示的是把n個圓盤借助柱子B成功的從A移動到Cpublicstaticvoidhanoi(intn,charA,charB,charC){if(n==1){//如果只有一個，直接從A移動到C即可System.out.println("從"+A+"移動到"+C);return;}//表示先把n-1個圓盤成功從A移動到Bhanoi(n-1,A,C,B);//把第n個圓盤從A移動到CSystem.out.println("從"+A+"移動到"+C);//表示把n-1個圓盤再成功從B移動到Chanoi(n-1,B,A,C);}通過上面的分析，你是不是覺得遞歸很簡單？所以我們寫遞歸的時候，完全可以套用上面的模板，先寫終止條件，再寫遞歸的邏輯調用 。還有一點很重要，就是一定要理解遞歸函數中每個參數的含義，這樣在邏輯處理和函數調用時才能得心應手 。一定不能一步一步把函數調用拆開來想，這樣很有可能你會崩潰 。
4、二叉樹的遍歷
我們來看最后一個常見的例子，就是二叉樹的遍歷 。前面說了，有興趣的話可以看看373，數據結構-6，還有樹 。我們主要看二叉樹的前、中、后三種遍歷方法 。
1.我們來看一下前導遍歷(根節點的開始) 。他的命令是
節點→左子樹→右子樹
讓我們應用模板來看看 。
publicvoidpreOrder(TreeNodenode){if(終止條件)//(必須要有)return;邏輯處理//（不是必須的）遞歸調用//(必須要有)}終止條件是節點等于空，通過邏輯處理可以直接打印出當前節點的值 。遞歸調用是先打印左子樹，再打印右子樹 。讓我們來看看 。
publicstaticvoidpreOrder(TreeNodenode){if(node==null)return;System.out.printf(node.val+"");preOrder(node.left);preOrder(node.right);}直接看中序遍歷和后續遍歷 。
2.中序遍歷(根節點在中間)
左子樹→根節點→右子樹
publicstaticvoidinOrder(TreeNodenode){if(node==null)return;inOrder(node.left);System.out.println(node.val);inOrder(node.right);}3.按逆序遍歷(根節點在末尾)
左子樹→右子樹→根節點
publicstaticvoidpostOrder(TreeNodetree){if(tree==null)return;postOrder(tree.left);postOrder(tree.right);System.out.println(tree.val);}5.鏈表的反向打印
這個我就不說了，看看就知道了 。
publicvoidprintRevers(ListNoderoot){//（終止條件）if(root==null)return;//（遞歸調用）先打印下一個printRevers(root.next);//（邏輯處理）把后面的都打印完了在打印當前節點System.out.println(root.val);}支流污染問題通過上面的分析，我們對遞歸有了更深的理解 。但是總覺得少了點什么 。其實我們可以用另一種方式來認識遞歸，那就是N樹 。在遞歸中，如果我們只調用自己一次，我們可以把它看成一棵二叉樹(這是我對自己的看法，我們可以把它看成一棵只有一個子節點的樹) 。如果我們稱自己兩次，我們可以把它想象成一棵二叉樹 。如果我們叫自己N次，我們可以把它想成一棵N叉樹 。就像下面這樣，到了葉子節點就開始反彈 。
如果遞歸處理不當，可能會導致分支污染和結果錯誤 。為什么會這樣？我先解釋一下，因為除了基本類型是值傳遞，其他很多類型基本都是引用傳遞 。看一下上圖 。比如我開始調用的時候傳入了一個list對象，調用第一個分支后，修改了列表中的數據，所以后續的所有分支都可以感知到，實際上對后續的分支造成了污染 。
我們先來看一個例子 。
給定數組nums = [2，3，5]，固定值target=8 。找出數組sums中能使數字之和成為目標的所有組合 。我們畫張圖看看吧 。
圖中的紅色表示組合成功 。這里只畫了選擇2的分支 。因為圖形太大，所以沒有畫出選擇3和選擇5的分支 。仔細一看，這不就是3-tree嗎？好，我們用遞歸 。我們先來看看函數的定義 。
privatevoidcombinationSum(Listcur,intsums[],inttarget){}取出遞歸模板 。
privatevoidcombinationSum(Listcur,intsums[],inttarget){if(終止條件){return;}//邏輯處理//因為是3叉樹，所以這里要調用3次//遞歸調用//遞歸調用//遞歸調用//邏輯處理}這種解決方案不太靈活 。如果nums的長度是3，我們遞歸調用它3次 。如果nums的長度是n，那么我們要調用它n次...所以我們可以直接把它寫成for循環的形式，如下

推薦閱讀