迭代算法总结

迭代法又称为辗转法，它是一种不断用旧的变量值递推得到新值的过程。

迭代法和递推法的不同：

 （1）迭代法使用while循环求解，递推法使用for循环求解。

 （2）迭代法在结束时得到一个解或一组解，递推法的循环控制变量改变一次就得到一个解，循环得到一系列的解。

迭代法分为精确迭代和近似迭代

精确迭代

① 最大公约数与最小公倍数

    辗转相除法..

②十进制转化为二进制整数

    除二取余法

③质因数的分解

  任给一个整数M，编写程序对其进行质因数分解

  分析：

（1）  如果M不等于1，则从x=2开始，让M除以x，如果不能被整除，则x是其中的一个因子，将x存入a中，并用商代替M

（2）如果M能被x整除，转步骤（1），否则x加一

（3）如果M不为1，则转步骤（1）执行，否则，算法结束。

#include<stdio.h>
int main()
{
int a[16],m,m0,x=2,i=0,j;
printf("请输入一个待分解的因数");
scanf("%d",&m0);
m=m0;
while(m!=1)
{
while(m%x==0)
{
i++;
a[i]=x;
m=m/x;
}
x=x+1;
}
printf("因式分解：%d=",m0);
for(j=1;j<i;j++)
{
printf("%d*",a[j]);
}
printf("%d",a[i]);
printf("n");
}

④角谷猜想

  对于一个自然数n，如果n为偶数，则将其除以2，如果n是奇数，则将其乘以3，然后加1，按照上述运算有限次后，总可以得到自然数1.

  例如：21->64->32->16->8->4->2->1;

  代码略

近似迭代法

  近似迭代与精确迭代相对，它是指利用迭代算法只能得到近似的解。

 ①求一个数的平方根

已知平方根迭代公式为Xn+1=（Xn+a/Xn)/2；设X0=a/2。编写程序输入a值计算其平方根。迭代的结束条件为|Xn-1-Xn|<10的-6次方。

#include<stdio.h>
#include<math.h>
int main()
{
double a,x0,x1;
printf("请输入一个整数：");
scanf("%lf",&a);
if(a<0)
{
printf("输入错误，请重新输入");
}
else
{
x0=a/2;
x1=(x0+a/x0)/2;
do{
x0=x1;
x1=(x0+a/x0)/2;
}while(fabs(x0-x1)>=1e-6);
}
printf("%lf的平方根为:%lfn",a,x1);
return 0;
}

②二分法

利用二分法求方程3*x*x*x-13x+2=0在区间[1,9]的根

二分法定义：

（1）对于在区间[a,b]上连续，且f(a)*f(b)<0，则y=f(x)在区间a，b有零点存在，求出中间值c=（a+b）/2;判断f(a)*f(b)的正负。

（2）如果f(a)*f(c)<0,令b=c。否则令a=c；

（3）如果|f(c)|>EPS(精度) 且|a-b|>EPS，则转步骤（1）执行，否则停止执行，将c作为近似值。

#include<stdio.h>
#include<math.h>
#define EPS 1e-6
double f(double x)
{
return 3*x*x*x-13*x+2;
}
int main()
{
double a,b,c;
printf("请输入一个区间（如：1 4）：");
scanf("%lf %lf",&a,&b);
printf("方程的解:x=");
if(fabs(f(a))<=EPS)
{
printf("%lgn",a);
}
else if(fabs(f(b))<=EPS)
{
printf("%lgn",b);
}
else if(f(a)*f(b)>0)
{
printf("输入错误，请重新输入");
}
else
{
while(fabs(f(c))>EPS&&fabs(b-a)>EPS)
{
c=(a+b)/2;
if(f(a)*f(c)<0)
{
b=c;
}
else
{
a=c;
}
}
printf("%lgn",c);
}
return 0;
}