跟黄申老师学数学(python实现)-01迭代法

摘要：在排好序的单词列表中查找某个单词优化和的初始化，从开始，这样避免只有时的优化减少了内存溢出的风险优化循环时，。

迭代法（Iterative Method），简单来说，其实就是不断地用旧的变量值，递推计算新的变量值。循环。

求数值的精确/近似解

二分法（Bisection method）

牛顿迭代法（Newton’s method）

在一定范围内查找目标值

二分查找

机器学习中的迭代算法

K-均值算法（K-means clustering）

PageRank 的马尔科夫链（Markov chain）

梯度下降法（Gradient descent）

求方程的精确/近似解

二分法

#"""计算某个给定正整数 n（n>1）的平方根，如果不使用编程语言"""
# delta_threshold:允许的误差的阈值
# max_try：最大尝试次数
def get_squre_root(n,delta_threshold=0.000000000000001,max_try=1000):
    if n <= 1:
        return -1
    min = 1.0
    n = float(n)
    max = n
    mid = (max+min)/2.0
    print(mid)
    for i in range(max_try):
        _n = mid * mid
        delta = _n-n
        if delta == 0:
            print("精确值")
            return mid
        
        abs_delta = abs(delta)
        if abs_delta <= delta_threshold:
            print("近似值")
            return mid
        else:
            if delta>0:
                max = mid
            else:
                min = mid
            mid = (max+min)/2.0
            print(mid)
    return min

get_squre_root(16)

牛顿迭代法
之后补充

查找匹配记录
快速查找记录，除了用字典，还可以用著名的 二分查找法（前提是有序）。这也是迭代逼近的典型案例。

二分查找，第一版

#在排好序的单词列表中查找某个单词
#@ param words_list,target_word
#@ return bool
def search(words_list,target_word):
    if not words_list:
        return False
    
    min = 1
    max = len(words_list)
    while True:
        mid = (max + min)/2
        mid_word = words_list[mid]
        if target_word == mid_word:
            print(mid)
            return True
        elif target_word > mid_word:
            min = mid
        else:
            max = mid

        if max <= min:
            return False

    return False
# words_list = ["i","love","my","wife","than","myself"s","body","."]
words_list = ["e"]
words_list = sorted(words_list)
print(words_list)
print(search(words_list,"i"))

二分查找，改完bug后，第二版

#在排好序的单词列表中查找某个单词
#@ param words_list,target_word
#@ return bool
# 优化1: min和max的初始化，从0开始，这样避免只有len(list)=1时的bug
# 优化2: mid = min + (max - min)/2 ,减少了内存溢出的风险
def search(words_list,target_word):
    if not words_list:
        return False
    
    min = 0
    max = len(words_list) - 1
    while True:
        mid = min + (max - min)/2
        mid_word = words_list[mid]
        if target_word == mid_word:
            print(mid)
            return True
        elif target_word > mid_word:
            min = mid
        else:
            max = mid

        if max <= min:
            return False

    return False
words_list = ["i","love","my","wife","than","myself"s","body","."]
# words_list = ["e"]
words_list = sorted(words_list)
print(words_list)
print(search(words_list,"i"))

二分查找，再改bug后，第三版（应该没bug了吧。。）

#在排好序的单词列表中查找某个单词
#@ param words_list,target_word
#@ return bool
# 优化1: min和max的初始化，从0开始，这样避免只有len(list)=1时的bug
# 优化2: mid = min + (max - min)/2 ,减少了内存溢出的风险
# 优化3: 循环时，min = mid + 1。和max = mid - 1。减少重复检查边界
# 优化4: 跳出循环的条件改为max < min，避免最后一步出现max=min=target的潜在bug
def search(words_list,target_word):
    if not words_list:
        return False
    
    min = 0
    max = len(words_list) - 1
    while True:
        mid = min + (max - min)/2
        mid_word = words_list[mid]
        if target_word == mid_word:
            print(mid)
            return True
        elif target_word > mid_word:
            min = mid + 1
        else:
            max = mid - 1

        if max < min:
            print(max)
            return False

    return False
words_list = ["i","love","my","wife","than","myself"s","body","."]
# words_list = ["e"]
words_list = sorted(words_list)
print(words_list)
print(search(words_list,"i"))

迭代法的特点是“分而治之”，不断重复一个相似的行为，一步步地缩小目标范围。计算机很适合处理这种重复的工作，而人类并不擅长，所以有时候不敏感。在编程的时候，可以特意留意这一差异。