迭代（Iteration）算法

概述：

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

主要步骤：

1. 确定迭代模型
2. 建立迭代关系式（主要工作）：递推数学模型一般是带下标字母，算法设计中要将其转化为：“循环不变式”--迭代关系式。而所谓的迭代关系式就是一个直接或间接地不断旧值递推新值的表达式
3. 对迭代过程进行控制：一般分为两种情况，一种是已知或可以计算出来所需的迭代次数，这时可以构建一个固定次数的循环来实现对迭代过程的控制。另外是所需的迭代次数无法确定，需要分析出迭代过程的结束条件，甚至于要考虑有可能得不到目标解的情况，避免出现迭代过程的死循环。

递推法

基础概念：

递推法算法是最基本的表现形式，从小规模的问题推解出大规模问题的一种方法，也称其“正推”。如累加过程就是求出前n-1项和的基础上推出前n项和的，递推公式是Sn=Sn-1 +An。由于无须保存每次的累加结果。所以用一个迭代变量s存储每次的累加结果，累加对象存储在变量a中，这样的递推公式就抽象成 “循环不变” 的累加式： S=s+a

Case1：

一对兔子从出生后第三个月开始，每月生一对小兔子，小兔子到第三月又开始生下一代小兔子，假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少对兔子？

问题分析：

用枚举法：将问题的求解过程以及各种不同情况一一列举出来，从中发现解决问题的方法。

因为一对兔子是要第三个月才可以生，那么第三个月存在两对，而另外一对要第三个月才能出生，因此列出兔子第三个月的对数就是两个月兔子对数的和。过程如下：

数学建模：

y1=y2=1，yn=yn-1+yn-2，n=3，4，5........ 其实可以发现是斐波那契数列

算法设计：

a，表示成每月的前2个月的对数，b表示前1一个月的兔子的对数，它们的初值均为1，这样3月份兔子对数为 c =a+；

求4月份兔子的对数时，先将4月份前2个月和前1月兔子的对数存储在变量a，b中，即a=b，b=c，再将4月份兔子的对数继续保存在变量c中，即c=a+b+.......当然这要操作，在变量中的数据被覆盖之前应先行输出已求解的结果。

算法1如下：

main(){
    int i,a=1,b=1;
    coout<<a<<b;
    for(i=1;1<=10;i=i+1){
        c=a+b;
        cout<<c;
        a==b;
        b==c;
    }
}
复制代码

构造“不变式”不止一种，当然也可以做如下表：

由上表可知：只是做了“c=a+b a=b+c b=a+c”，循环该不变式，这样一次循环其实是递推了3步，循环次数自然而然就要减少了

算法2如下：

main(){
int i,a=1,b=1;
    cout<<a<<b;
    for(i=1;1<=4;i++){  
        c=a+b;
        a=b+c;
        b=a+c;
        cout<<a<<b;
    }
}
复制代码

可是算法2最后输出的并不是12项，而是2+3*4=12项，这样的算法不算太好。因此，我们发现前面算法1，2基本思路都是基于这样一个事实：前三个月的数据输出后就无法保存了，从而构造了循环的“不变式”。其实一个赋值语句的执行过程是众所周知的---赋值过程是先计算后赋值，这样以上递推过程就无须引入第三个变量。 因此如下表递推迭代表达式：

由此可以知道循环不变式为“a=a+b b=a+b”

算法3如下：

main(){
int i,a=1,b=1;
    cout<<a<<b;
    for(i=1;1<=5;i++){  
        a=a+b;
        b=a+b;
        cout<<a<<b;
    }
}
复制代码

总结：

后两种解法是在通过有限的变量，存储信息的基础上，在递推过程中发现“重复的周期”，实际上用的比较少。如果从周期角度讨论，case的算法和其他循环算法的周期都是“1”。