迭代法（Iterative Method），简单来说，其实就是不断地用旧的变量值，递推计算新的变量值。循环。
具体应用 求数值的精确/近似解 二分法（Bisection method）牛顿迭代法（Newton’s method）在一定范围内查找目标值 二分查找机器学习中的迭代算法 K-均值算法（K-means clustering）PageRank 的tzdrg（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 minget_squre_root(16)复制代码 牛顿迭代法之后补充 查找匹配记录
快速查找记录，除了用字典，还可以用著名的 二分查找法（前提是有序）。这也是迭代逼近的典型案例。 二分查找，第一版 #在排好序的单词列表中查找某个单词#@ param words_list,target_word#@ return booldef 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 Falsewords_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的潜在bugdef 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 Falsewords_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"))复制代码 思考
迭代法的特点是“分而治之”，不断重复一个相似的行为，一步步地缩小目标范围。计算机很适合处理这种重复的工作，而人类并不擅长，所以有时候不敏感。在编程的时候，可以特意留意这一差异。
WechatIMG37.jpeg