欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

迭代(一):迭代算法的基本思想

程序员文章站 2022-07-11 16:54:00
迭代法也称辗转法,是一种不断用变量的旧值推出新值的过程。它是解决问题的一种基本方法,通过让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 迭代算法的基本思想是:为求一个问题的解x,可由给定的一个初值x0,根据某一迭代公式得到一个新的值 ......

      迭代法也称辗转法,是一种不断用变量的旧值推出新值的过程。它是解决问题的一种基本方法,通过让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。

      迭代算法的基本思想是:为求一个问题的解x,可由给定的一个初值x0,根据某一迭代公式得到一个新的值x1,这个新值x1比初值x0更接近要求的值x;再以新值作为初值,即:x1→x0,重新按原来的方法求x1,重复这一过程直到|x1-x0|<ε(某一给定的精度)。此时可将x1作为问题的解x。

      利用迭代算法解决问题,需要做好以下三个方面的工作:

      (1)确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值推出新值的变量,这个变量就是迭代变量。

      (2)建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键。

      (3)对迭代过程进行控制。在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。

      迭代也是用循环结构实现,只不过要重复的操作是不断从一个变量的旧值出发计算它的新值。其基本格式描述如下:

迭代变量赋初值;

while (迭代终止条件)

{

      根据迭代表达式,由旧值计算出新值;

      新值取代旧值,为下一次迭代做准备;

}

【例1】验证谷角猜想

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

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

      (1)编程思路

      定义迭代变量为n,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时,n=n/2 ;当 n 为奇数时, n=n*3+1 。

      这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。由于对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,从而完成验证工作。因此,用来结束迭代过程的条件可以定义为: n==1 。

(2)源程序

#include <iostream>

using namespace std;

int main()

{

   unsigned int data; 

   cout<<"请输入一个自然数:"; 

   cin>>data; 

   while(data!=1) 

   { 

        if((data%2==0)) 

              {

            cout<<data<<"/2=";

                     data/=2; 

                     cout<<data<<endl;

              }

        else 

        { 

            cout<<data<<"*3+1=";

                     data=data*3+1; 

            cout<<data<<endl; 

        } 

   } 

   return 0;

}

【例2】求平方根

      用迭代法求某个数的平方根。已知求平方根的迭代公式为:

迭代(一):迭代算法的基本思想

      (1)编程思路

      用迭代法求某个数a的平方根的算法为:

      (1)先自定一个初值x0,作为a的平方根值,例如,取a/2作为x0的初值。利用迭代公式求出一个x1。此值与真正的a的平方根值相比,误差可能很大。

      (2)把新求得的x1代入x0中,准备用此新的x0再去求出一个新的x1。

      (3)利用迭代公式再求出一个新的x1的值,也就是用新的x0又求出一个新的平方根值x1,此值将更趋近于真正的平方根值。

      (4)比较前后两次求得的平方根值x0和x1,如果它们的差值小于指定的值(如0.000001),即达到要求的精度,则认为x1就是a的平方根值,执行步骤5;否则执行步骤2,即循环进行迭代。  

      (5)迭代结束,输出结果x1。

(2) 源程序

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

    double x0,x1,a ;

       cin>>a;

    x0 =a/2;          // 迭代初值

    x1 =0.5*(x0 + a/x0);

    do

       {

         x0 = x1;  // 为下一次迭代作准备

         x1 = 0.5*(x0 + a/x0);

    } while (fabs(x1-x0)>0.000001);

    cout<<x1<<endl;       // 输出结果

       return 0 ;

}