程序员的数学基础课
黄申
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讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

04 | 数学归纳法:如何用数学归纳提升代码的运行效率?

黄申 2018-12-17
你好,我是黄申。
上次我们聊了迭代法及其应用,并用编程实现了几个小例子。不过你知道吗,对于某些迭代问题,我们其实可以避免一步步的计算,直接从理论上证明某个结论,节约大量的计算资源和时间,这就是我们今天要说的数学归纳法
平时我们谈的“归纳”,是一种从经验事实中找出普遍特征的认知方法。比如,人们在观察了各种各样动物之后,通过它们的外观、行为特征、生活习性等得出某种结论,来区分哪些是鸟、哪些是猫等等。比如我这里列出的几个动物的例子。
通过上面的表格,我们可以进行归纳,并得出这样的结论:
如果一个动物,身上长羽毛并且会飞,那么就是属于鸟;
如果一个动物,身上长绒毛、不会飞、而且吃小鱼和老鼠,那么就属于猫。
通过观察 个动物样本的 个特征,从而得到某种动物应该具有何种特征,这种方法就是我们平时所提到的归纳法。
我们日常生活中所说的这种归纳法和数学归纳法是不一样的,它们究竟有什么区别呢?具体数学归纳法可以做什么呢?我们接着上一节舍罕王赏麦的故事继续说。

什么是数学归纳法?

上节我们提到,在棋盘上放麦粒的规则是,第一格放一粒,第二格放两粒,以此类推,每一小格内都比前一小格多一倍的麦子,直至放满 个格子。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(67)

  • oddrock
    递归把计算交给计算机,归纳把计算交给人,前者是拿计算机的计算成本换人的时间,后者是拿人的时间换计算机的计算成本

    作者回复: 精辟的总结👍

    2018-12-18
    145
  • cafu_chino
    老师下次可以提供Python的代码示例吗?对Java的使用不是很熟练

    作者回复: 可以,后期会整理出来

    2018-12-17
    24
  • 恋恋
    项目中还没碰到,但在以前做编程题时经常碰到找规律的问题,这时候只需抽象出一个公式即可。
    另外可否给老师提个建议,就是在github上建一个仓库,这样我们可以fork下来,用自己熟悉的编程语言把老师讲的思路写进代码里push上去,方便大家相互学习 ^_^

    作者回复: 这是个好建议,我先问下是否版权问题

    2018-12-17
    12
  • 陈诚
    个人觉得有时候虽然用迭代和递归都能解决问题,但是使用递归时,由于有数学归纳法保证递归关系的正确性,所以只要专注于解决2个相邻层的关系就可以了,然后使用数学归纳法的基本情况作为递归出口。当然,在实际编程中,递归会增加函数调用栈的开销,也是要考虑的一方面
    2018-12-17
    12
  • 陈诚
    我觉得加深学习数学效果的方式,就是自己实现一遍,我这里用C语言实现了一下递归求麦粒总数的问题以求抛砖引玉
    #include <stdio.h>
    #include <stdlib.h>

    struct result {
    long cur_grid_wheat;
    long sum_of_wheat;
    };

    struct result wheat(int grid)
    {
    struct result rst;

    if (grid == 1) {
    rst.cur_grid_wheat = 1;
    rst.sum_of_wheat = 1;
    } else {
    struct result last_rst;
    last_rst = wheat(grid - 1);
    rst.cur_grid_wheat = last_rst.cur_grid_wheat * 2;
    rst.sum_of_wheat = last_rst.sum_of_wheat + rst.cur_grid_wheat;
    }

    return rst;
    }

    int main(int argc, char *argv[])
    {
    struct result rst;
    int grid_index = 0;

    if (argc != 2) {
    printf("Usage: %s grid_index\n", argv[0]);
    return -1;
    }
    grid_index = atoi(argv[1]);

    rst = wheat(grid_index);

    printf("grid_index: %d\ncur_grid_wheat: %ld\nsum_of_wheat: %ld\n",
    grid_index, rst.cur_grid_wheat, rst.sum_of_wheat);

    return 0;
    }

    2018-12-19
    9
  • mikukuma
    数据归纳法通俗易懂的说法就是一个个经典的数学公式的证明。我们要去证明这个公式是否正确,需要根据两个步骤,1:n=1时,公式是否正确;2: 假设n = k-1成立,那么去证明n=k公式是成立的。就跟数学做证明题一样的思路。然后我们去做这些算法题的时候,就可以直接根据已经证明的公式,很快就能得到我们需要的答案。
    2018-12-17
    7
  • WL
    老师我感觉递归和归纳法还是有些区别的, 递归是自顶向下的拆解问题, 直到终止条件后再一层层返回结果, 但是归纳法好像没有自顶向下拆解问题的这个环节.
    2018-12-17
    6
  • 予悠悠
    可以给老师提个建议吗?课程里提到的关键概念可不可以加上英文名呢?例如这篇里提到的迭代,递归,正向递推,逆向递推

    作者回复: 好,后面会加注,感谢建议

    2019-01-19
    5
  • 鱼鱼鱼培填
    用Python实现数学归纳法,一开始使用math.pow()函数发现不对,Python中该函数会使用科学技术法导致结果出错
    #-*- coding:UTF-8 -*-
    class result(object):
    wheatNum = 0
    wheatTotalNum = 0

    class getWheatTotalNum(object):
    '''
    函数说明:使用递归嵌套, 进行数学归纳法证明
    Param: k - 表示放到第几格 result - 表示当前格子的麦粒数
    Return: boolean - 放到第K格时是否成立
    '''
    def prove(self, k, result):
    if k == 1:
    if (2 ** 1 - 1) == 1:
    result.wheatNum = 1
    result.wheatTotalNum = 1
    return True
    else:
    return False

    else:
    proveOfPreviousOne = self.prove(k - 1, result)
    result.wheatNum *= 2
    result.wheatTotalNum += result.wheatNum
    proveOfCurrentOne = False
    if result.wheatTotalNum == (2 ** k - 1):
    proveOfCurrentOne = True
    if (proveOfPreviousOne & proveOfCurrentOne):
    return True
    else:
    return False


    if __name__ == '__main__':
    grid = 64
    result = result()
    g = getWheatTotalNum()
    print(g.prove(grid, result))

    作者回复: 研究了细节,很赞👍

    2018-12-19
    1
    5
  • 田野
    关于这节课讲的内容在编程中具体的应用能这样理解不? 迭代法在实际应用中,如果迭代层次过深 ,会导致各种问题(耗时\内存占用等) ,遇到这种情况可以总结规律, 使用数学归纳法将其简化。(代码中不再使用迭代 使用数学归纳总结出来的结果)

    作者回复: 是的,特别是递归的实现比较耗资源

    2018-12-17
    5
  • 失火的夏天
    个人觉得动态规划就是归纳法思想的处理,一个问题分解为多个字问题的最优解
    2018-12-17
    4
  • lkj
    递归还有一个就是搜索目录文件,编程递归第一个练习就是这个
    递归过程判断事目录还是文件,目录就继续递归,文件就根据缩进打印,最终打印出目录结构

    作者回复: 是的👌

    2019-05-25
    3
  • microsnow
    <?php

    class Result
    {
        public $wheatNum = 0;
        public $wheatTotalNum = 0;
    }

    class Lession4_2
    {

        public $result = NULL;

        public function __construct()
        {
            $this->result = new Result();
        }

        public function getResult()
        {
            return $this->result;
        }

        public function prove($n)
        {
            if ($n == 1) {
                if ((pow(2, 1) - 1) == 1) {
                    $this->result->wheatNum = 1;
                    $this->result->wheatTotalNum = 1;
                    return true;
                } else {
                    return false;
                }
            } else {
                $proveOfPreviousOne = $this->prove($n - 1);
                $this->result->wheatNum *= 2;
                $this->result->wheatTotalNum += $this->result->wheatNum;
                $proveOfCurrentOne = false;
                if ($this->result->wheatTotalNum == (pow(2, $n) - 1)) $proveOfCurrentOne = true;
                if ($proveOfCurrentOne && $proveOfPreviousOne) {
                    return true;
                } else {
                    return false;
                }
            }
        }
    }

    $a = new Lession4_2();
    $result = $a->prove(13);
    $result = $a->getResult();

    作者回复: 我对php语言不熟悉,你能否贴一下运行的结果?

    2018-12-29
    1
    3
  • 未明。
    数字全变成了math_progress_error了
    2018-12-17
    3
  • 老师~我没有学习JAVA,只学了C++和python。。。请问能否多发几种语言的代码哈

    作者回复: 好的 后面我会统一加上

    2019-01-06
    2
  • fcb的鱼
    每节课后可以多留一些编程题,每节课就2个例子感觉不过瘾!
    2018-12-25
    2
  • 十指流玉
    老师您好!如果有一些程序我们自己归纳出了规矩,那如何快速的应用到程序中呢,还是说程序中本身就有一些函数就是归纳法的体现?

    作者回复: 这里你说的“有一些程序我们自己归纳出了规律”,具体是指什么?

    2018-12-25
    2
  • zh
    想起罗斯的故事,1-100 的所有数求和,罗斯的方法就是数学归纳法的简单应用。平时还没有需要用到归纳法,递归方法也很少用。

    作者回复: 你是说高斯的故事吧😀

    2018-12-24
    2
  • zack
    数据格式有问题 不知道是老师写错了还是给出了不兼容格式

    作者回复: 请问具体是哪个数据格式?

    2018-12-20
    2
  • TryTs
    老师,您讲这些数学知识的时候能不能更加深入一点,最好能够结合工程项目或者一些著名的库函数呢?

    作者回复: 后面会结合更多实际的项目。至于你说的库函数,具体是指哪方面?能否举个例子?

    2018-12-19
    2
收起评论
67
返回
顶部