#一、基本策略

1. 迭代算法

概要

迭代法也称“辗转法”,是一种不断用变量的旧值递推出新值的解决问题的方法。

基本步骤

  1. 确定迭代模型

    根据问题描述,分析得出前一个(或几个)值与其下一个值的迭代关系数学模型。这样的迭代关系,最终会迭代出求解的目标。

  2. 建立迭代关系式

    直接或间接地不断由旧值递推出新值的表达式,存储新值的变量称为迭代变量。

  3. 对迭代过程进行控制

    确定在什么时候结束迭代过程,一种是已知或可以计算出来所需迭代次数,另一种是所需的迭代次数无法确认,需要分析出迭代过程的结束条件。

相关方法

  1. 递推法

    递推算法是迭代算法的最基本的表现形式,从小规模问题推解出大规模问题的一种方法。

    1
    2
    3
    4
    5
    6
    7
    // 斐波那契数列
    int i, a = 1, b = 1 ,c;
    for (int i = 1; i <=10 ; i ++) {
    c = a + b ;
    a = b;
    b = c;
    }
  2. 倒推法

    1
    2
    3
    4
    5
    6
    7
    // 一只小猴子摘了若干桃子,每天吃现用桃子的一半多一个。
    // 到第十天时就只有一个桃子了,求原有多少个桃?
    int s = 1;
    for (int i = 9; i > 0; i--) {
    s = 2 * (s + 1);
    }
    System.out.println(s);