03迭代法
一、作用
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型存储
因为计算的结果太大了，查出了 Javaint型的范围 - 只计算到了 63 格
因为计算 64 格之后，总数已经超过 Javalong型的范围
三、其他应用
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 的马尔科夫链、梯度下降法等。迭代法之所以在机器学习中广泛应用是因为：很多机器学习的过程，就是根据已知的数据和一定的假设，求一个局部最优解。迭代法可帮助学习算法逐步搜索，直至发现这种解。
