迭代法详解

迭代法（iteration）也称辗转法，是一种不断用变量的旧值递推出新值的解决问题的方法，迭代算法一般用于数值计算。累加，累乘都是迭代算法的基础应用。

利用迭代法解题的步骤：

1）确定迭代模型

根据问题描述，分析出前一个（或几个）值与下一个值的迭代关系数学模型。

2）建立迭代关系式

递推数学模型一般是带下标的字母，算法设计中要将其转化为“循环不变式”----迭代关系式，迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量。

3）对迭代过程进行控制。

确定在什么时候结束迭代过程。

迭代过程是通过小规模问题的解逐步求解大规模问题的解，表面上看正好与递归相反，但也找到了大规模问题与小规模问题的关系。

本节的例子是用迭代完成的，也都可以用递归完成。相信尝试后，定能体会到递归的简便之处。

1，递推法（recursion）是迭代算法的最基本表现形式。一般来讲，一种简单的递推方法，就是从小规模的问题解出大规模问题的一种方法，也称其为“正推“。如”累加“。

兔子繁殖问题：一对兔子从出生后第三个月开始，每月生一对兔子，小兔子每到第三个月有开始生兔子，问一年中每个月各有多少兔子？

我们通常用的迭代：

print(a,b)

for(i=1;i<=10;i++)

 {

    c=a+b;

　　print(c);

　　a=b;

　　b=c;

}

另一种构造不变式的方法：

1　　2　　　　3　　　　4　　　　5　　　　6　　　　7　　　　8

a　　b　　c=a+b　　 a=b+c　　b=a+c c=a+b

这样，一次循环其实是递推了三步，循环次数就要减少了。

#include<stdio.h>

int main()
{
    
    int i,a=1,b=1;
    int c;
    printf("%d %d ",a,b);
    for(i=1;i<=4;i++)
    {
        c=a+b;
        a=b+c;
        b=c+a;
        printf("%d %d  %d  ",c,a,b); //注意输出顺序是c,a,b
    }
}

上面输出的共2+3*4=14项，这样的算法不太完美。

另一种思路，

1 2 　　3　　　　4　　　　5

a　　b　　a=a+b b=a+b　　 a=a+b

#include<stdio.h>

int main()
{
    
    int i,a=1,b=1;
    int c;
    printf("%d %d ",a,b);
    for(i=1;i<=5;i++)
    {
        a=a+b;
        b=a+b;
        printf("%d %d  ",a,b);
    }
}

2.倒推法（inverted recursion)对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。

猴子吃桃问题：一只小猴子摘了若干桃子，每天吃现有的桃的一半多一个，到第十天时就只有一个桃子了，求原有多少个桃？

数学模型

a10=1,a9=(1+a10)*2 ,a8=(1+a9)*2...

递推公式为：

ai=(1+a(i+1) )*2 ; i=9 ,8 .. .1

由于每一天的桃子树只依赖前一天的桃子数，所以只用一个迭代变量代表桃子数就可以了。

int main()
{
    int i,a;
    a=1;
    for(i=9;i>=1;i--)
        a=(a+1)*2;
    printf("%d",a);
}

输出如图所示的杨辉三角形（限定用一个一维数组完成）

　　 1 　　1

1 　　　1 1　　1

1 2　　 1 1 2 1 杨辉三角存储格式

#include<iostream>
using namespace std;

int main()
{

    int n,i,j,a[100];
    cin>>n;
    cout<<1<<endl;
    a[1]=a[2]=1;
    cout<<a[1]<<ends<<a[2]<<endl;
    for(i=3;i<=n;i++)
    {
        a[1]=a[i]=1;
        for(j=i-1;j>1;j--)
             a[j]=a[j]+a[j-1];
        for(j=1;j<=i;j++)
            cout<<a[j]<<ends;
        cout<<endl;
    }
}

若求n层的杨辉三角，则数组最多存储n个数据（第n层有n个数据）就可以了。

第i层有i列需要求解i个数据，若从第一列向后计算，求第i行时，由于用一个一维数组存储，每求出一个数将覆盖第i-1行对应列存储的

值，这将导致下一个数无法计算，而从第i个元素倒着向前计算就能正常进行，则可避免这种情况出现。

a[j]=a[j]+a[j-1]; j=i-1,i-2, ... 2

迭代法 详解

迭代法详解