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

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

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

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

例 3 : 验证谷角猜想。日本数学家谷角静夫在研讨自然数时发现了一个奇特现象:关于恣意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以失掉自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。

要求:编写一个顺序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全进程打印出来。

分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以失掉两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 言语把它描画出来就是:

以下是引用片段:
  if n 为偶数 then
  n=n/2
  else
  n=n*3+1
  end if

这就是需求计算机重复执行的迭代进程。这个迭代进程需求重复执行多少次,才干使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来终了迭代进程的条件。细心分析标题要求,不美观出,对恣意给定的一个自然数 n ,只需经过有限次运算后,可以失掉自然数 1 ,就已经完成了验证义务。因此,用来终了迭代进程的条件可以定义为: n=1 。参考顺序如下:

以下是引用片段:
  cls
  input "Please input n=";n
  do until n=1
  if n mod 2=0 then
  rem 假定 n 为偶数,则调用迭代公式 n=n/2
  n=n/2
  print "—";n;
  else
  n=n*3+1
  print "—";n;
  end if
  loop
  end

迭代法

迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的方式x=g(x),然后按以下步骤执行:

(1) 选一个方程的近似根,赋给变量x0;

(2) 将x0的值保管于变量x1,然后计算g(x1),并将结果存于变量x0;

(3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。

若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就以为是方程的根。上述算法用C顺序的方式表示为:

【算法】迭代法求方程的根

以下是引用片段:
  { x0=初始近似根;
  do {
  x1=x0;
  x0=g(x1); /*按特定的方程计算新的近似根*/
  } while ( fabs(x0-x1)>Epsilon);
  printf(“方程的近似根是%f\n”,x0);
  }

迭代算法也常用于求方程组的根,令

X=(x0,x1,…,xn-1)

设方程组为:

xi=gi(X) (I=0,1,…,n-1)

则求方程组根的迭代算法可描画如下:

【算法】迭代法求方程组的根

以下是引用片段:
  { for (i=0;i
  x=初始近似根;
  do {
  for (i=0;i
  y=x;
  for (i=0;i
  x=gi(X);
  for (delta=0.0,i=0;i
  if (fabs(y-x)>delta) delta=fabs(y-x);
  } while (delta>Epsilon);
  for (i=0;i
  printf(“变量x[%d]的近似根是 %f”,I,x);
  printf(“\n”);
  }

详细运用迭代法求根时应留意以下两种可以发作的情况:

(1) 假定方程无解,算法求出的近似根序列就不会收敛,迭代进程会变成死循环,因此在运用迭代算法前应先调查方程能否有解,并在顺序中对迭代的次数给予限制;

(2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会招致迭代失败。

递归

递归是设计和描画算法的一种有力的工具,由于它在复杂算法的描画中被经常采用,为此在进一步引见其他算法设计方法之前先讨论它。

能采用递归描画的算法通常有这样的特征:为求解规模为N的效果,设法将它分解成规模较小的效果,然后从这些小效果的解方便地构造出大效果的解,并且这些规模较小的效果也能采用异常的分解和综合方法,分解成规模更小的效果,并从这些更小效果的解构造出规模较大效果的解。特别地,当规模N=1时,能直接得解。



相关评论