综合技术

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

微信扫一扫,分享到朋友圈

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

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

迭代算法的基本思想是:为求一个问题的解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 ;

}

阅读原文...


微信扫一扫,分享到朋友圈

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

博客园-原创精华区

小白的Python 学习笔记(八)推导式详解

上一篇

Hacker hits Symantec and accesses passwords

下一篇

评论已经被关闭。

插入图片

热门分类

往期推荐

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

长按储存图像,分享给朋友