什么是迭代法（Iterative Method）？

就是不断地用旧的变量值，递推计算新的变量值。

小故事:

古印度国王舍罕酷爱下棋，他打算重赏国际象棋的发明人宰相西萨·班·达依尔。这位聪明的大臣指着象棋盘对国王说：“陛下，我不要别的赏赐，请您在这张棋盘的第一个小格内放入一粒麦子，在第二个小格内放入两粒，第三小格内放入给四粒，以此类推，每一小格内都比前一小格加一倍的麦子，直至放满 64 个格子，然后将棋盘上所有的麦粒都赏给您的仆人我吧！”国王自以为小事一桩，痛快地答应了。可是，当开始放麦粒之后，国王发现，还没放到第二十格，一袋麦子已经空了。随着，一袋又一袋的麦子被放入棋盘的格子里，国王很快看出来，即便拿来全印度的粮食，也兑现不了对达依尔的诺言。

通过一个函数来计算最后麦子的数量.

用计算机语言其实特别适合

function getNumberOfWheat(grid){
numberOfWheatInGrid = 0; // 当前格子里麦粒的数量 
let numberOfWheatInGrid = 1; // 第一个格子里麦粒的数量 

// 先放一粒米
sum += numberOfWheatInGrid; 

for (let i = 2; i <= grid; i ++) {         
    numberOfWheatInGrid *= 2;
    // 当前格子里麦粒的数量是前一格的2倍 
    sum += numberOfWheatInGrid; 
    // 累计麦粒总数 
    } 
    return sum;
}

// 计算64格的数量
console.log(getNumberOfWheat(64))

具体应用？

• 求数值的精确或者近似解。典型的方法包括二分法（Bisection method）和牛顿迭代法（Newton’s method）。

• 在一定范围内查找目标值。典型的方法包括二分查找。

• 机器学习算法中的迭代。相关的算法或者模型有很多，比如 K- 均值算法（K-means clustering）、PageRank 的马尔科夫链（Markov chain）、梯度下降法（Gradient descent）等等。迭代法之所以在机器学习中有广泛的应用，是因为很多时候机器学习的过程，就是根据已知的数据和一定的假设，求一个局部最优解。而迭代法可以帮助学习算法逐步搜索，直至发现这种解。

实践二分法求方程的精确或者近似解

题: 找 10 的平方根

思路: 我们需要先看 1 到 10 的中间数值，也就是 ¹¹⁄₂=5.5。5.5 的平方是大于 10 的，所以我们要一个更小的数值，就看 5.5 和 1 之间的 3.25。由于 3.25 的平方也是大于 10 的，继续查看 3.25 和 1 之间的数值，也就是 2.125。这时，2.125 的平方小于 10 了，所以看 2.125 和 3.25 之间的值，一直继续下去，直到发现某个数的平方正好是 10

/** * 
 * @Description: 计算大于1的正整数之平方根 
 * @param n-待求的数, deltaThreshold-误差的阈值, maxTry-二分查找的最大次数
 * @return double-平方根的解 
 * */

function getSqureRoot(n, deltaThreshold, maxTry) {
    // 参数不符合条件,返回-1
    if (n <= 1) { return -1.0; }

    let min = 1.0;
    let max = n;
    
    // 开始使用尝试次数与预想的进度开始迭代查找结果
    for (let i = 0; i < maxTry; i++) {
        // 取一个中间数
        let middle = (min + max) / 2;
        // 开始平方
        let square = middle * middle;

        // 看平方结果是否满足我们的需求
        // Math.abs为取绝对值
        let delta = Math.abs((square / n) - 1);

        // 进度符合,返回正确的值
        if (delta <= deltaThreshold) {
            // 找到符合条件的平方根
            return middle;
        } else {
            // 平方后的结果大于 待求的数字n
            if (square > n) {
                // 重新定义max
                max = middle;
            } else {
                // 小于则重新定义min
                min = middle;
            }
        }
    }
    // 所有迭代运行完,没有结果返回 -2
    return -2.0;
}



// 开始求解

  let number = 10;

  // 求10的平方根
  // 进度为 0.000001
  // 最多迭代 10000 次
  let squareRoot = getSqureRoot(number, 0.000001, 10000);


  if (squareRoot == -1) {
   console.log("请输入大于1的整数");
  } else if (squareRoot == -2) {
   console.log("未能找到解");
  } else {
   console.log(`${number}的平方根是${squareRootString}`);
  }

故事的结局

第1个格子里的小麦有1粒

第2个格子里的小麦有2粒

第3个格子里的小麦有4粒

第4个格子里的小麦有8粒

第5个格子里的小麦有16粒

第6个格子里的小麦有32粒

第7个格子里的小麦有64粒

第8个格子里的小麦有128粒

第9个格子里的小麦有256粒

第10个格子里的小麦有512粒

第11个格子里的小麦有1024粒

第12个格子里的小麦有2048粒

第13个格子里的小麦有4096粒

第14个格子里的小麦有8192粒

第15个格子里的小麦有16384粒

第16个格子里的小麦有32768粒

第17个格子里的小麦有65536粒

第18个格子里的小麦有131072粒

第19个格子里的小麦有262144粒

第20个格子里的小麦有524288粒

第21个格子里的小麦有1048576粒

第22个格子里的小麦有2097152粒

第23个格子里的小麦有4194304粒

第24个格子里的小麦有8388608粒

第25个格子里的小麦有16777216粒

第26个格子里的小麦有33554432粒

第27个格子里的小麦有67108864粒

第28个格子里的小麦有134217728粒

第29个格子里的小麦有268435456粒

第30个格子里的小麦有536870912粒

第31个格子里的小麦有1073741824粒

第32个格子里的小麦有2147483648粒

第33个格子里的小麦有4294967296粒

第34个格子里的小麦有8589934592粒

第35个格子里的小麦有17179869184粒

第36个格子里的小麦有34359738368粒

第37个格子里的小麦有68719476736粒

第38个格子里的小麦有137438953472粒

第39个格子里的小麦有274877906944粒

第40个格子里的小麦有549755813888粒

第41个格子里的小麦有1099511627776粒

第42个格子里的小麦有2199023255552粒

第43个格子里的小麦有4398046511104粒

第44个格子里的小麦有8796093022208粒

第45个格子里的小麦有17592186044416粒

第46个格子里的小麦有35184372088832粒

第47个格子里的小麦有70368744177664粒

第48个格子里的小麦有140737488355328粒

第49个格子里的小麦有281474976710656粒

第50个格子里的小麦有562949953421312粒

第51个格子里的小麦有1125899906842624粒

第52个格子里的小麦有2251799813685248粒

第53个格子里的小麦有4503599627370496粒

第54个格子里的小麦有9007199254740992粒

第55个格子里的小麦有18014398509481984粒

第56个格子里的小麦有36028797018963968粒

第57个格子里的小麦有72057594037927936粒

第58个格子里的小麦有144115188075855872粒

第59个格子里的小麦有288230376151711744粒

第60个格子里的小麦有576460752303423488粒

第61个格子里的小麦有1152921504606846976粒

第62个格子里的小麦有2305843009213693952粒

第63个格子里的小麦有4611686018427387904粒

第64个格子里的小麦有9223372036854775808粒

国王一共给了18446744073709551615粒麦子

微信公众号

本文链接：