浙江龙网

  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，最终打印出来的结果不会改变，所以这个分支污染不会造成最终的结果误差 。

推荐阅读


上一篇：干性胸膜炎如何治疗 胸膜炎的症状

下一篇：出国办理签证需要多少钱 意大利签证怎么办*