迭代法

什么是迭代法

迭代法，简单来说，其实就是不断地用旧的变量值，递推计算新的变量值。迭代法的思想很容易通过计算机语言中的循环语言来实现。我们可以通过循环语句，让计算机重复执行迭代中的递推步骤，推导出变量的最终值。

基本步骤

确定用于迭代的变量。
建立迭代变量之间的递推关系
控制迭代的过程

迭代法的具体应用

• 求数值的精确或者近似解。典型的方法包括二人法和牛顿迭代法
• 在一定范围内查找目标值。二分查找
• 机器学习算法中的迭代。

  求方程的精确或近似解

  不用自带的函数求平方根

import math
# delta_threshold 控制解的精度
# max_try 控制循环的次数
def get_square_root(number, delta_threshold=0.000001, max_try=10000):
    if number <= 1:
        return -1
    min = 1
    max = number
    for i in range(max_try):
        middle = (min + max) / 2
        square = middle * middle
        delta = math.fabs(square / number - 1)
        if (delta <= delta_threshold):
            return round(middle, 2)
        elif square > number :
            max = middle
        else:
            min = middle
    return -2

查找匹配记录

二分法中的迭代式逼近，可以帮助我们查找匹配的记录

# 二分查找
def search(dictionary, word):
    if dictionary is None:
        return False
    if len(dictionary) == 0:
        return False
    left, right = 0, len(dictionary) - 1
    while(left <= right):
        middle = int((left + right ) / 2)
        if dictionary[middle] == word:
            return middle
        elif dictionary[middle] > word:
            right = middle - 1
        else:
            left = middle + 1
    return False