迭代

迭代法

迭代法

⼀、概念

迭代法百度迭代法也称辗转法，是⼀种不断⽤变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为⼀次解法），即⼀次性解决

问题。迭代法⼜分为精确迭代和近似迭代。“⼆分法”和“⽜顿迭代法”属于近似迭代法。迭代算法是⽤计算机解决问题的⼀种基本⽅

法。它利⽤计算机运算速度快、适合做重复性操作的特点，让计算机对⼀组指令（或⼀定步骤）进⾏重复执⾏，在每次执⾏这组指令（或这

些步骤）时，都从变量的原值推出它的⼀个新值。

⼆、关键步骤

利⽤迭代算法解决问题，需要做好以下三个⽅⾯的⼯作：

1）确定迭代变量。在可以⽤迭代算法解决的问题中，⾄少存在⼀个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

2）建⽴迭代关系式。所谓迭代关系式，指如何从变量的前⼀个值推出其下⼀个值的公式（或关系）。迭代关系式的建⽴是解决迭代问题的

关键，通常可以使⽤递推或倒推的⽅法来完成。

3）对迭代过程进⾏控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程⽆休⽌地重复执⾏下去。迭代过

程的控制通常可分为两种情况：⼀种是所需的迭代次数是个确定的值，可以计算出来；另⼀种是所需的迭代次数⽆法确定。对于前⼀种情

况，可以构建⼀个固定次数的循环来实现对迭代过程的控制；对于后⼀种情况，需要进⼀步分析出⽤来结束迭代过程的条件。

三、⼀般结构

迭代变量赋值

while(循环条件)//可以表⽰为：！迭代终⽌条件

{

根据迭代关系式由迭代变量旧值计算出新值；

迭代变量新值取代旧值，为下⼀次做准备；

}

四、常见的迭代问题

1）猴⼦吃桃问题

#include

intmain(){

inti,x;

x=1;//迭代变量赋值

for(i=6;i>=1;i--)//

x=(x+1)*2;//迭代关系表达式，迭代过程中反复由原值推出新值

printf("⼩猴⼦共摘了%d个桃⼦n",x);//

return0;

}

2）求a的平⽅根

#include

#include

intmain()

{

floata,x0,x1;

scanf("%f",&a);

x1=a/2;//迭代变量赋值

do{

x0=x1;//新值变旧值

x1=(x0+a/x0)/2;//利⽤迭代关系表达式计算新值

}while(fabs(x1-x0)>1e-5);//注意将迭代结束条件取反

printf(“sqrt(%.2f)=%fn”,a,x1);

return0;

}

3）求sinx的近似值

#include

#include

#definePI3.14159

intmain()

{

inti;

doublex,t,s=0;

scanf_s("%lf",&x);

x=x*PI/180;//将输⼊的⾓度转换成弧度

t=x;//迭代变量赋初值

for(i=1;i<=100;i+=2)

{

s+=t;

t=-t*x*x/((2*i)*(2*i+i));//迭代关系表达式，旧值推出新值

}

printf("sin(%f)=%f",x,s);

return0;

}