大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > 什么是迭代跟递归算法?二者有什么区别?

什么是迭代跟递归算法?二者有什么区别?(3)

关键词:递归有什么区别算法迭代  阅读(1893) 赞(10)

[摘要]本文是对什么是迭代跟递归算法?二者有什么区别?的讲解,对学习C++编程技术有所帮助,与大家分享。

【效果】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。

斐波那契数列为:0、1、1、2、3、……,即:

以下是引用片段:
  fib(0)=0;
  fib(1)=1;
  fib(n)=fib(n-1)+fib(n-2) (当n>1时)。

写成递归函数有:

以下是引用片段:
  int fib(int n)
  { if (n==0) return 0;
  if (n==1) return 1;
  if (n>1) return fib(n-1)+fib(n-2);
  }

递归算法的执行进程分递推和回归两个阶段。在递推阶段,把较复杂的效果(规模为n)的求解推到比原效果复杂一些的效果(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必需先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必需先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),区分能立即失掉结果1和0。在递推阶段,必需求有终止递归的情况。例如在函数fib中,当n为1和0的情况。

在回归阶段,当获得最复杂情况的解后,逐级前往,依次失掉稍复杂效果的解,例如失掉fib(1)和fib(0)后,前往失掉fib(2)的结果,……,在失掉了fib(n-1)和fib(n-2)的结果后,前往失掉fib(n)的结果。

在编写递归函数时要留意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“复杂效果”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“复杂效果”层,它们各有自己的参数和局部变量。

由于递归惹起一系列的函数调用,并且可以会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写顺序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项动身,逐次由前两项计算出下一项,直至计算出要求的第n项。

【效果】 组分解绩

效果描画:找出从自然数1、2、……、n中任取r个数的一切组合。例如n=5,r=3的一切组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1

(4)5、3、2 (5)5、3、1 (6)5、2、1

(7)4、3、2 (8)4、3、1 (9)4、2、1

(10)3、2、1

分析所列的10个组合,可以采用这样的递归思想来思索求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的一切组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组分解绩转化成求m-1个数中取k-1个数的组分解绩。设函数引入义务数组a[ ]存放求出的组合的数字,商定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可以的选择,因还未去顶组合的其他元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下顺序中的函数comb。

【顺序】

以下是引用片段:
  # include
  # define MAXN 100
  int a[MAXN];
  void comb(int m,int k)
  { int i,j;
  for (i=m;i>=k;i--)
  { a[k]=i;
  if (k>1)
  comb(i-1,k-1);
  else
  { for (j=a[0];j>0;j--)
  printf(“%4d”,a[j]);
  printf(“\n”);
  }
  }
  }
  void main()
  { a[0]=3;
  comb(5,3);
  }

【效果】 背包效果

效果描画:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不跨越指定的限制重量,但选中物品的价值之和最大。

设n 件物品的重量区分为w0、w1、…、wn-1,物品的价值区分为v0、v1、…、vn-1。采用递归寻觅物品的选择方案。设前面已有了多种选择的方案,并保管了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在调查新方案,其物品选择情况保管于数组cop[ ]。假定当前方案已思索了前i-1件物品,如今要思索第i件物品;当前方案已包括的物品的重量之和为tw;至此,若其他物品都选择是可以的话,本方案能抵达的总价值的希冀值为tv。算法引入tv是当一旦当前方案的总价值的希冀值也小于前面方案的总价值maxv时,继续调查当前方案变成有意义的义务,应终止当前方案,立即去调查下一个方案。由于当方案的总价值不比maxv大时,该方案不会被再调查,这同时保证函数后找到的方案一定会比前面的方案更好。

关于第i件物品的选择思索有两种可以:

(1) 思索物品i被选择,这种可以性仅当包括它不会跨越方案总重量限制时才是可行的。选中后,继续递归去思索其他物品的选择。

(2) 思索物品i不被选择,这种可以性仅当不包括物品i也有可以会找到价值更大的方案的情况。

按以上思想写出递归算法如下:

以下是引用片段:
  try(物品i,当前选择已抵达的重量和,本方案可以抵达的总价值tv)
  { /*思索物品i包括在当前方案中的可以性*/
  if(包括物品i是可以接受的)
  { 将物品i包括在当前方案中;
  if (i
  try(i+1,tw+物品i的重量,tv);
  else
  /*又一个完整方案,由于它比前面的方案好,以它作为最佳方案*/
  以当前方案作为暂时最佳方案保管;
  恢复物品i不包括外形;
  }
  /*思索物品i不包括在当前方案中的可以性*/
  if (不包括物品i仅是可男思索的)
  if (i
  try(i+1,tw,tv-物品i的价值);
  else
  /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/
  以当前方案作为暂时最佳方案保管;
  }



相关评论