1. 首頁 > 生活百科 > >

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

越眾創業網


privatevoidcombinationSum(Listcur,intsums[],inttarget){//終止條件必須要有if(終止條件){return;}//邏輯處理(可有可無，是情況而定)for(inti=0;i我們一步一步來看 。
1.終止條件是什么？
當target等于0時，說明我們找到了一組組合，我們會把它們打印出來，這樣終止條件就好寫了 。代碼如下所示
if(target==0){System.out.println(Arrays.toString(cur.toArray()));return;}2、邏輯處理和遞歸調用
當我們逐個選擇時，如果要選擇的值大于目標值，我們就不選擇它 。如果它沒有比target大，我們會將其添加到列表中，表明我們已經選擇了他 。如果我們選擇了他，那么在遞歸調用時，我們將從目標值中減去選擇的值 。代碼如下所示
//邏輯處理//如果當前值大于target我們就不要選了if(target終止條件和遞歸調用已經寫出 。感覺代碼很簡單 。讓我們結合起來看看完整的代碼 。
privatevoidcombinationSum(Listcur,intsums[],inttarget){//終止條件必須要有if(target==0){System.out.println(Arrays.toString(cur.toArray()));return;}for(inti=0;i我們也使用上述數據進行打印和測試 。
publicstaticvoidmain(String[]args){newRecursion().combinationSum(newArrayList(),newint[]{2,3,5},8);}運行結果如下
我們的思路沒有出問題，這難道不是一個驚喜嗎？為什么結果是錯的？事實上，這是一個典型的分支污染 。我們再來看一下圖 。
當我們選擇2時，它是一個分支，當我們選擇3時，它是另一個分支 。這兩個分支的數據應該是互不干擾的，但實際上當我們往下走選擇2的分支時，選擇2的分支的數據會被攜帶在列表中 。當我們再次選擇選擇3的分支時，這些數據仍然存在于列表中，所以污染了選擇3的分支 。一種解決方案是為每個分支創建一個新的列表，如下所示，這樣任何一個分支的修改都不會影響到其他分支 。
讓我們再看一下代碼 。
privatevoidcombinationSum(Listcur,intsums[],inttarget){//終止條件必須要有if(target==0){System.out.println(Arrays.toString(cur.toArray()));return;}for(inti=0;ilist=newArrayList(cur);//把數據加入到集合中list.add(sums[i]);//遞歸調用combinationSum(list,sums,target-sums[i]);}}我們看到第13行重新創建了一個列表 。我們再打印一次，看看結果 。結果完全正確 。每組數據的總和是8 。
上述每個分支都創建了一個新的列表，所以任何分支修改都只會影響當前分支，而不會影響其他分支 。也算是一種解決辦法吧 。但是每次都是重新創建數據，運行效率很差 。我們知道，當執行分支1時，分支1的數據將被帶入列表 。當執行分支2時，我們實際上并不需要分支1的數據，所以有一種方法是在從分支1執行到分支2時，刪除分支1的數據 。這就是經常提到的回溯算法 。讓我們來看看 。
privatevoidcombinationSum(Listcur,intsums[],inttarget){//終止條件必須要有if(target==0){System.out.println(Arrays.toString(cur.toArray()));return;}for(inti=0;i讓我們再看一下打印的結果 。他們絕對正確 。
遞歸分支污染對結果的影響分支污染通常會給結果帶來致命的誤差，但這不是絕對的 。我們再舉一個例子 。生成一個長度為2 n的數組，數組的取值范圍為0到(2 n)-1 。例如，如果n是3，則生成
[0,0,0][0,0,1][0,1,0][0,1,1][1,0,0][1,0,1][1,1,0][1,1,1]我們畫張圖看看吧 。
這不是二叉樹嗎？我們已經講了很多關于遞歸的內容 。我們直接看代碼 。
privatevoidbinary(int[]array,intindex){if(index==array.length){System.out.println(Arrays.toString(array));}else{inttemp=array[index];array[index]=0;binary(array,index+1);array[index]=1;binary(array,index+1);array[index]=temp;}}上面的代碼很容易理解 。首先是終止條件，然后是遞歸調用 。在調用之前，數組[index]的值將被保存并最終恢復 。我們來測試一下 。
newRecursion().binary(newint[]{0,0,0},0);看看打印結果 。
結果絕對正確 。我們再改一下代碼 。
privatevoidbinary(int[]array,intindex){if(index==array.length){System.out.println(Arrays.toString(array));}else{array[index]=0;binary(array,index+1);array[index]=1;binary(array,index+1);}}我們再來看看打印結果 。
結果和上面一模一樣 。一開始沒有保存array[index]的值，最后也沒有恢復，但是結果一點都不差 。原因是上面代碼第5行的array[index]=0 。這是因為，即使數組[index]在前一個分支執行時被污染，在下一個分支中也會被再次修改 。即使改成任何數字，也不會影響最后的結果 。例如，當最后一個分支完成時，我們將其更改為100 。你在努力 。
privatevoidbinary(int[]array,intindex){if(index==array.length){System.out.println(Arrays.toString(array));}else{array[index]=0;binary(array,index+1);array[index]=1;binary(array,index+1);//注意，這里改成100了array[index]=100;}}當我們看到第10行的時候，我們把數組[index]改成100，最終打印出來的結果不會改變，所以這個分支污染不會造成最終的結果誤差 。

推薦閱讀