一、作用

k =1,2,...n 迭代是逐步计算，可以用计算机中的循环来实现，最典型的迭代法应用就是二分查找（要求被查找的区间是有序的）。

二、使用

1.题目

舍罕王赏麦：一个棋盘共有 64 个格子，第一个格子放 1 个麦粒，第 2 个格子放 2 个麦粒，第 3 个格子放 4 个麦粒，....，后面的格子放的麦粒数是前面一个格子的 2 倍，求 64 个格子一共可存放多少麦粒？

2.什么是迭代

不断地用旧的变量值，递推计算新的变量值。迭代的思想很容易用计算机中的循环来实现。

舍罕王赏麦的例子中，递推关系是：

3.代码

/**
 * 舍罕王赏麦（迭代的思想）
 *
 * @param grid
 * @return：麦子总数
 */
public static long getNumberOfWheat(int grid) {
    long sum = 0; // 麦子总数
    long numOfWheatInGrid = 0; // 当前格子里的麦子数
    numOfWheatInGrid = 1; // 第1个格子里的麦粒数
    sum += numOfWheatInGrid;
    // 正向迭代
    for (int i = 2; i <= grid; i++) {
        // 当前格子里的麦粒数=前一格子中麦粒数*2
        numOfWheatInGrid *= 2;
        // 累积麦粒总数
        sum += numOfWheatInGrid;
    }
    return sum;

}

代码中需注意：

• 每个格子中的麦粒数及总的麦粒数用 Java 中的long型存储
  因为计算的结果太大了，查出了 Java int型的范围
• 只计算到了 63 格
  因为计算 64 格之后，总数已经超过 Java long型的范围

三、其他应用

1.求数值的精确或近似解

典型的方法包括二分法和牛顿迭代法

eg：题目

计算某个给定正整数 n （n>1）的平方根。

1）数学建模

正整数 n 的平方根和 n 的关系如下：

本题的目的是在 [1,n] 之间找到一个数 y ，使得该数的平方无限逼近于 n 。可采用二分法来实现。

假设要找 10 的平方根

• 看 [1,10] 的中间值 11/2 的平方
  11/2 的平方 > 10 ，故 y 在 [1,11/2] 范围内；
• 看 [1,11/2] 的中间值 13/4 的平方
  13/4 的平方 > 10，故 y 在 [1,13/4] 范围内；
• 看 [1,13/4] 的中间值 17/8 的平方
  17/8 的平方 < 10，故 y 在 [17/8,13/4] 范围内；
• 继续向下寻找，直到误差在允许范围内

2）代码

/**
 * 计算正整数 n 的平方根
 * @param n
 * @param deltaThreshold：误差的阈值
 * @param maxTry：二分查找的最大次数
 * @return
 */
public static double getSqureRoot(int n, double deltaThreshold, int maxTry) {
    // 排除一些不合法情况
    if (n <= 1) {
        return -1.0;
    }
    double left = 1;
    double right = n;
    for (int i = 0; i < maxTry; i++) {
        double mid = (left + right) / 2;
        double square = mid * mid;
        // 计算误差
        double delta = Math.abs((square / n) - 1);
        if (delta <= deltaThreshold) {
            // 误差在允许范围内：直接将结果返回
            return mid;
        } else {
            // 继续迭代
            if (square < n) {
                left = mid;
            } else {
                right = mid;
            }
        }

    }
    return -2.0;
}

注意：

• 使用 deltaThreshold 控制解的精度
  理论上可通过二分法无限迭代求得精确解，但考虑到实际应用中耗费的大量时间和计算资源，我们并不需要完全精确的解。

• 使用 maxTry 控制迭代次数
  处于良好的编程习惯，避免使用 while(true) 造成死循环

2.在一定范围内查找目标值

典型的方法包括二分查找。二分法关键的前提是所查找的区间是有序的，这样才能在每次折半的时候，确定被查找对象属于左半边还是右半边

eg：题目

从字典中查找某一特定元素：从 String[] dic = {"hello","every","body","haha","geek"};中查找hello

1）数学建模

将字典排序（二分法要求待查区间是有序的），然后按照二分法查找

2）代码

/**
 * 在字典中查找某一单词
 *
 * @param dictionary
 * @param wordToFind
 * @return
 */
public static boolean search(String[] dictionary, String wordToFind) {
    // 排除一些不合法情况
    if (dictionary == null || dictionary.length == 0) {
        return false;
    }
    // 将字典排序
    Arrays.sort(dictionary);
    // 二分法查找
    int left = 0;
    int right = dictionary.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (dictionary[mid].equals(wordToFind)) {
            return true;
        } else if (dictionary[mid].compareTo(wordToFind) > 0) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return false;

}

3.机器学习中的迭代

相关算法很多：K-均值、PageRank 的马尔科夫链、梯度下降法等。迭代法之所以在机器学习中广泛应用是因为：很多机器学习的过程，就是根据已知的数据和一定的假设，求一个局部最优解。迭代法可帮助学习算法逐步搜索，直至发现这种解。

参考文献

极客时间_程序员必备数学基础