程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?

黄申 2018-12-14
你好,我是黄申。
今天我们来说一个和编程结合得非常紧密的数学概念。在解释这个重要的概念之前,我们先来看个有趣的小故事。
古印度国王舍罕酷爱下棋,他打算重赏国际象棋的发明人宰相西萨·班·达依尔。这位聪明的大臣指着象棋盘对国王说:“陛下,我不要别的赏赐,请您在这张棋盘的第一个小格内放入一粒麦子,在第二个小格内放入两粒,第三小格内放入给四粒,以此类推,每一小格内都比前一小格加一倍的麦子,直至放满 64 个格子,然后将棋盘上所有的麦粒都赏给您的仆人我吧!”
国王自以为小事一桩,痛快地答应了。可是,当开始放麦粒之后,国王发现,还没放到第二十格,一袋麦子已经空了。随着,一袋又一袋的麦子被放入棋盘的格子里,国王很快看出来,即便拿来全印度的粮食,也兑现不了对达依尔的诺言。
放满这 64 格到底需要多少粒麦子呢?这是个相当相当大的数字,想要手动算出结果并不容易。如果你觉得自己厉害,可以试着拿笔算算。其实,这整个算麦粒的过程,在数学上,是有对应方法的,这也正是我们今天要讲的概念:迭代法(Iterative Method)。

到底什么是迭代法?

迭代法,简单来说,其实就是不断地用旧的变量值,递推计算新的变量值
我这么说可能还是比较抽象,不容易理解。我们还回到刚才的故事。大臣要求每一格的麦子都是前一格的两倍,那么前一格里麦子的数量就是旧的变量值,我们可以先记作 ;而当前格子里麦子的数量就是新的变量值,我们记作 。这两个变量的递推关系就是这样的:
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(87)

  • 云韵 置顶
    求一个数的平方根的那段代码中的第18行(double delta = Math.abs((square / n) - 1);
    )不太能看明白,为什么这么做?老师和专栏朋友们可以帮忙解决一下吗?谢谢。

    作者回复: 我这里使用了误差占原值的百分比,来控制迭代的结束

    2018-12-14
    1
    32
  • miracle
    class Lesson3_3里面第22行改成 int middle = left + (right - left)/2 会更合适一点,不然有可能会溢出

    作者回复: 对 很好的补充

    2018-12-14
    68
  • 晓嘿
    老师
    “唐瑞甫

    2
    class Lesson3_3里面第22行改成 int middle = left + (right - left)/2 会更合适一点,不然有可能会溢出
    2018-12-14
     作者回复
    对 很好的补充”

    这个我看着跟你写的那个是一样的啊,换算完也是(left+right)/2啊,这个22行的代码会溢出吗,在什么情况下

    作者回复: 确实从数学的角度看是一样的,但是计算机系统本身有局限性。如果left和right都是接近系统设定的最大值,那么两者相加会溢出。如果只加两者差值的一半,那么不会超过两者中较大的值,自然也不会溢出

    2018-12-14
    37
  • Jerry银银
    老师,心里有点疑惑:感觉迭代法、数学归纳法有相关性,而且跟编程里面的循环和递归都有相关,您能否简要概括一下他们之间关系和联系呢?

    作者回复: 这是个很好的问题,确实有些地方让人容易糊涂。我这里谈谈自己的理解。
    数学里的迭代法,最初是用来求解方程的根,通过不断的更新变量值来逼近最终的解。其思想也被用来计算数列、二分查找等等。我把这种迭代法称为广义的。
    而数学归纳法呢,是从理论上证明某个命题成立,从而避免了迭代中的重复计算。下一篇会具体介绍。
    而递归就是指“递推”和“回归”,它的递推和数学归纳法非常类似,因此数学归纳法中的递推可以直接翻译为递归的编程。而循环也有递推,不过通常和递归是反向的。
    此外,人们常常把编程中的基于循环的实现叫做迭代的实现,用于和递归的实现加以区分。我个人觉得这种迭代的叫法是狭义的。广义的迭代既可以使用循环,也可以使用递归来实现,就像我第3讲的求根和二分查找等,也可以用递归来实现。

    2018-12-14
    32
  • Wing·三金
    目前正在做机器学习最优化方面的研究,所以对迭代法应用很多,几乎可以说是科研人员的必备手段了。

    迭代法最困难的地方除了设置「迭代的规则」,另一个难点就是设置「迭代的终止条件」。前者专业性比较强就不多说,后者很大程度上依赖于coder的经验。因为机器学习中往往只要求足够精确的近似解,而如果一昧追求精度可能时间复杂度太大;如果以最大迭代次数为终止条件又可能得不到满意的解。因此实践中往往二者一起用,而且精度和迭代次数都需要根据一定的理论支撑去设定(不过更多的时候是从业界认可的经验出发)。

    作者回复: 很好的心得体会👍

    2018-12-15
    19
  • WL
    没太看懂怎么用二分法查找同义词, 文章中讲的算法好像用二分法查询指定的单词, 不知道我这么理解对不对

    作者回复: 对 其实是精确匹配,匹配后就可以拿到这个词对应的同义或近义词

    2018-12-14
    17
  • 柚子
    程序论递归和迭代区别,突然有个想法,好像将结束条件写在方法里就是递归,将结束条件写在方法外就是迭代。哈哈😄

    作者回复: 在编程里,递归的主要特征是方法或函数自己调用自己,因此一般结束条件放在方法内。而基于循环的迭代,如果递推是方法实现的,那确实结束条件是在方法外

    2018-12-14
    1
    15
  • 彩色的沙漠
    快速排序,用的也是二分迭代思想,把一个数组分成两个独立部分。分别进行排序,直到两边都是有序

    作者回复: 是的,采用了分而治之的思想

    2018-12-19
    6
  • 瘦马
    迭代的基本思想就是不断用旧的变量推算出新的变量,直到获得有效结果。
    迭代使用的步骤:
    1、确定变量
    2、确定变量的推导方式
    3、控制迭代
    2018-12-14
    6
  • Shawn
    既然提到了求平方根就不得不说一下神奇的魔术字:0x5f3759df

    作者回复: 确实是个申请的数字,还研究了好久背后的数学知识

    2019-03-23
    4
  • 耿森
    在贷款还款计算中,如果贷款方式是等额本金,那么每期的还款金额是根据上一期来计算的,要用到迭代法😄

    作者回复: 厉害了,非常好的生活实例

    2018-12-29
    4
  • silence
    迭代就是将问题相同的部分抽离出来,把不容易解决的大问题切割成一个个小问题

    作者回复: 递归式的迭代可以将大问题逐步简化为小问题

    2018-12-14
    4
  • 代码世界没有爱情
    python实现:
    def f(x):
        y = x
        if x > 1 and isinstance(x, int):
            flag, num = 1, 0
            global middle
            while num <= 100:

                middle = (x + flag) / 2
                if middle * middle > y:
                    x = middle
                elif middle * middle < y:
                    flag = middle
                else:
                    print('exactly value:', middle)

                    break
                num += 1
            else:
                print('deferenct value:', middle)
        elif x ==1:print('exactly value:', 1)
        else:
            print('TypeError')

    f(81)
    2018-12-17
    3
  • 我不是王子
    老师,求平方根的第18行我也没看懂,可以详细讲解一下吗,为什么是(square / n) - 1再求绝对值呢

    作者回复: 这是算相对误差,比如n是100,那么误差为1的时候,误差相对于n的百分比为1%。

    2018-12-15
    3
  • 蒋宏伟
    迭代法
    why
    利用计算机适合重复计算的特点
    how
    f(0)=
    确定迭代的变量
    f(n) = g(f(n-1))
    建立迭代变量之间的递推关系
    g =
    控制迭代的过程
    what
    让计算机重复执行,推导出最终值
    类比
    for
    while
    应用
    在一定范围内查找目标值(缩小)
    通过二分法定位 BUG
    通过二分法实现 Math.sqrt
    重复执行递推计算结果(增加)
    计算国际象棋放置的麦粒数
    2018-12-15
    3
  • Eleven
    举个例子,假如我们要找到 10 的平方根。我们需要先看 1 到 10 的中间数值,也就是 11/2=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。
    老师,我想问一下,这个地方为什么是从11开始二分?

    作者回复: 因为这里是从1开始,所以(10+1)/2=5.5。之所以从1开始而不是0,是假设我们已经知道0~1之间的数,平方也是小于1,不可能到10。

    2019-11-09
    2
  • (+曦+)
    7皇后问题
    2018-12-14
    2
  • 指间砂的宿命
    二分法很少手写,程序中更多使用循环语句,不过对于有序数据查找二分法倒是相对高效,工作中倒是很少用,特别是有数据库的情况下指定key很多时候都是直接让数据库返回了

    作者回复: 有些数据库的索引,具体实现的时候可能会用到二分查找

    2018-12-14
    2
  • 好大一颗TREE
    这和定义的数据类型有关,即两个无线趋近于Int类型的数字相加会大于int类型的最大值
    2019-06-16
    1
  • Geek_zy
    老师,之前看过递归,分治思想这些问题。所以就有复习了一下。得到一下总结:
    迭代是一种解决问题的思想,然后递归和循环都是实现这种思想的编程手段。
    包括分治思想也是他也是一种思想,正好迭代这种编程手段可以来实现这种思想。
    不知道我的理解有什么问题没有,望老师指教。

    作者回复: 理解是对的。数学里的迭代法更为通用,而编程里的“迭代法”一般特指基于循环的实现。

    2019-04-25
    1
收起评论
87
返回
顶部