您的位置: 首页  >  文章  >  迭代法

迭代法

分类: 文章 • 2024-01-08 11:01:58

  刚认识女朋友时候，那段时间很流行微信红包（好吧，一直都很流行），每天早上发一个小红包浪漫一下，时间久了女朋友也厌烦了每天固定的一元小红包，开玩笑说着让我第一天发一元，第二天两元，第三天四元，以此类推，每天都比前一天的红包数额多一倍。

  我毅然决然的拒绝了。
  因为那将是很恐怖的后果，这里面就包含着我们这次要讲的重点：迭代法（Iterative Method）。

迭代法定义

  那么何为迭代法？迭代法就是不断用旧的变量值，递推计算新的变量值。我们来说的形象一些，假设前一天的红包金额就是旧的变量值，可以记作Xn-1 ；当前的金额为Xn ，它们的递推关系：f(Xn) = f(Xn-1) * 2 , f(1) = 1
  编程实现，以JavaScript为例。

function getMuchMoney(day){
    var sum = 0;                //总金额
    var muchMoneyOfPacket = 0;  //当前红包金额
    
    muchMoneyOfPacket = 1;      //设置第一天红包金额
    sum += muchMoneyOfPacket;

    for(var i=0; i<day; i++){
        muchMoneyOfPacket *=2;      //当前红包金额是前一天的两倍
        sum += muchMoneyOfPacket;   //累加总金额
    }
    return sum;      
}

console.log(getMuchMoney(30));	//2147483647（元）

从代码看出，一个月30天累计的金额就已经达到了这么一长串数值，位数都不想数。

迭代法的应用

  1. 求数值的精确或者近似解。典型的方法包括二分法（Bisection method）和牛顿迭代法（Newton’s method）。
  2. 在一定范围内查找目标值。典型的方法包括二分查找。
  3. 机器学习算法中的迭代。相关的算法或者模型很多，譬如K-均值算法（K-means
    clustering）、PageRank的马尔科夫链（Markov chain）、梯度下降法（Gradient
    descent）…迭代法之所以在机器学习中有如此广泛的应用，是因为很多时候机器学习的过程就是根据已知的数据和一定的假设，求一个局部最优解。迭代法可以帮助学习算法逐步搜索直至发现这种解。

求数值的精确或者近似解

  计算某个给定正整数n(n > 1)的平方根，如果不使用编程语言的自带函数该如何实呢假设有正整数n，它的平方根一定小于n本身，并且大于1,。那么问题可以转换成，在1到n之间，找一个数字等于n的平方根。现在就是用迭代法中常见的二分法，每次查看区间内的中间值，检验它是否符合标准。

假设我们要找到10的平方根。

  1. 我们需要看1到10的中间数，也就是11/2=5.5
  2. 5.5的平方根大于10，要找一个比5.5更小的值，就看1到5.5的中间数3.25
  3. 3.25的平方根也大于10，继续查看1到3.25的中间数2.125
  4. 2.125的平方根小于10，就需要查看2.125到3.25的中间数
  5. 以此类推，直至发现一个数正好是10 的平方根，然而多数时候都只能找个近似值

JavaScript演示。

function getSqureRoot(n,deltaThreshold,maxTry){
    if(n <= 1){
        console.log("请输入大于1的整数！")
    }
    var min = 1,
        max = n;
    for(var i=0; i<maxTry; i++){
        var middle = (min + max) / 2,
            square = middle * middle,
            delta = Math.abs((square / n) - 1);
        if(delta <= deltaThreshold){
            return middle;
        }else{
            if(square > n){
                max = middle;
            }else{
                min = middle;
            }
        }
    }
}
console.log(getSqureRoot(16,0.0001,100));

  代码中deltaThreshold代表误差阈值，也就是用来控制精度，二分会无限次迭代得出精确值，但这样会很耗费时间和资源，这是没有必要的。

  maxTry代表迭代的次数，避免陷入死循环。

查找匹配记录

  二分法中的迭代式逼近，不仅可以帮助我求得近似解，还可以帮助我查找匹配的记录。
大家都使用过同义词/近义词词典吧，当需要查“西红柿”这个词的同义词，在词典中可以查到“番茄”、“tomato”等。譬如，在处理文章时候，将“番茄”、“tomato”作为“西红柿”的扩展，这样在用户搜索“西红柿”相关文章的时候，也能够确保出现“番茄”、“tomato”的文章返回给用户。
  这样一个要求的实现，可以使用哈希表，但这里我们探讨的是二分查找进行字典查询的思路。

  1. 将整个字典先进行排序（假设从小到大）。二分法中很关键的前提条件是，所查找的区间是有序的，这样才能在每次折半的时候，确定被查找对象属于左边还是右边。
  2. 使用二分法逐步定位到被查找的单词。每次迭代时候，都在搜索区间的中间点，如果这个中间点上的单词和待查找单词一致就返回；如果不一致，要看被查单词比中间点上的单词是小还是大。如果小，那说明被查单词如果存在字典中，就一定在左边，否则就在右边。
  3. 以此类推，迭代式查找，知道范围缩小到一个单词，如果还是没找到就说明不存在。

我们简单来个实例，在a到g之间查找f，查找过程如下图。
迭代法

求数值的解和查找匹配记录的区别

二分查找进行字典查询的思路和二分法求解平方根是一致的，主要区别有两个方面：

1. 每次判断是否终结迭代的条件不同。求平方根时候，需要判断某个数的平方是否和输入的数据一致；字典查询需要判断字典中某个单词是否和待查的单词相同。
2. 二分查找需要确保被搜索的空间是有序的。

相关推荐