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

02 | 余数:原来取余操作本身就是个哈希函数

黄申 2018-12-12
你好,我是黄申。今天我们来聊聊“余数”。
提起来余数,我想你肯定不陌生,因为我们生活中就有很多很多与余数相关的例子。
比如说,今天是星期三,你想知道 50 天之后是星期几,那你可以这样算,拿 50 除以 7(因为一个星期有 7 天),然后余 1,最后在今天的基础上加一天,这样你就能知道 50 天之后是星期四了。
再比如,我们做 Web 编程的时候,经常要用到分页的概念。如果你要展示 1123 条数据,每页 10 条,那该怎么计算总共的页数呢?我想你肯定是拿 1123 除以 10,最后得到商是 112,余数是 3,所以你的总页数就是 112+1=113,而最后的余数就是多出来,凑不够一页的数据。
看完这几个例子,不知道你有没有发现,余数总是在一个固定的范围内
比如你拿任何一个整数除以 7,那得到的余数肯定是在 0~6 之间的某一个数。所以当我们知道 1900 年的 1 月 1 日是星期一,那便可以知道这一天之后的第 1 万天、10 万天是星期几,是不是很神奇?
你知道,整数是没有边界的,它可能是正无穷,也可能是负无穷。但是余数却可以通过某一种关系,让整数处于一个确定的边界内。我想这也是人类发明星期或者礼拜的初衷吧,任你时光变迁,我都是以 7 天为一个周期,“周”而复始地过着确定的生活。因为从星期的角度看,不管你是哪一天,都会落到星期一到星期日的某一天里。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(121)

  • Only now
    尾号限行啊!

    作者回复: 这个例子👍

    2018-12-12
    104
  • miracle
    既然提到了hash+salt 建议可以稍微多聊一点,在现实场景中更容易碰到
    2018-12-12
    80
  • 我来也
    关于文中的例子有点不解:
    "假如说,我们要加密数字 625,根据刚才的规则,我们来试试。假设随机数我选择 590127。那百、十和个位分别加上这个随机数,就变成了 590133,590129,590132。然后,三位分别除以 7 求余后得到 5,1,4。最终,我们可以得到加密后的数字就是 415。因为加密的人知道加密的规则、求余所用的除数 7、除法的商、以及所引入的随机数 590127,所以当拿到 415 的时候,加密者就可以算出原始的数据是 625。是不是很有意思?"
    正向加密可以理解.
    反向解密感觉有点问题呀.
    --------------
    625中间的数字2: (2 + 590127)%7 = 1. 但是(9 + 590127)%7 = 1
    --------------
    那么625和695最终加密后的结果都是415啊.
    那就不一定能还原出来原始的值了啊.
    --------------
    另外,如果最后一位数字加密后的结果是0, 交换位置后, 会有麻烦吧.

    作者回复: 这里还要用到除法中的商

    2018-12-12
    74
  • 西北偏北
    取模定义:
    除法是被除数除以除数,结果包含商和余数,记做:a/b
    只求余数的除法,叫取模。记做 a%b

    应用举例:
    取模运算的特点,无论a多大,只要b固定,那么a%b的余数总是在一个有限范围内。这种特点相当于将a进行了降维和分类,跟方便我们认知世界。
    比如今天是星期一,10000天后是星期几。就可以通过求余数来计算。因为今天是星期一,所以相对于今天的7天后,肯定也是星期一。
    那1w天中,7的整数倍日期,肯定也都是星期一,唯一要看的,就是最终余数多少,那就相当于距离星期一几天。所以1w天后是星期几变成了
    公式:(星期一 + 1w%7) 由于1w%7 = 4 ,说明是星期一的四天后,于是相对于今天1w天后是星期五

    取模增加随机性:
    连续的整数,在取模时,其余数也是周期连续的。比如:10%7 = 3 , 11%7=4 。余数算作一分钟分类,某些情况下,我们不希望原始数据的连续性,
    在分类后也连续。为了增加几个班同学之间随机组合,增加交流。比如你不希望一个班(他们的学号相同),被分配到连续的组里。
    那可以在取模之间,对原始数据做一些规则转换,让连续的原始数据变得不连续。比如给原始数据加一个随机数。
    公式为:(a + random) % b
    注意在一次分类活动中,random是固定的,不是每个数来都重新来个random。random就相当于hash算的中的hash因子。
    当然为了使得原始连续数据不连续还有其他很多种方式,比如数据的不同位树互换等等。


    文章谬误:
    文章中所说的加密算法,再缺乏商时,无法完成解密,因为数据被降维了。

    作者回复: 是的 需要保留商,原文没有强调这点

    2018-12-27
    39
  • 蒋宏伟
    个人觉得余数用分类来形容有些不恰当,当更恰当的词是均分。分类,每类数量不一定相同,当均分,每类数量是相同的。

    作者回复: 确实分类这个词有歧义,常规的取余是均分

    2018-12-15
    32
  • acheng
    最大公约数,模幂运算(DES、AES、RSA),凯撒密码,孙子定理,都是以模运算为基础的。
    2018-12-12
    25
  • Transient
    在各种进制转换的过程中也需要用到余数。例如:十进制的100转换成二进制,就可以使用循环取余。还有就是在求水仙花数的时候,取十进制上每一位的数值的过程中可以使用取余运算

    作者回复: 是的,融汇贯通,赞👍

    2018-12-12
    19
  • 小花小黑的铲屎官
    模运算最大的特点就是不可逆,https就是利用这个原理通过非对称加密协商出对称密钥的。
    2018-12-12
    16
  • plasmatium
    我用余数最多的就是前端动画循环,比如要控制动作循环,数据放一个数组里,假设数组长度是17那么只要arr[i%17];i++; 就行了,不需要那种判断i有没有等于17,等于就置零,否则加一,那样太丑了

    作者回复: 是的 :)

    2019-02-04
    9
  • smarttime
    老师能不能再深入些,这些太表面化了,另同问加密之后怎么解密的,规则没说3个数字除以7商要相同吧!多讲些实际应用,文章字数有些少!

    作者回复: 好的 在后面的文章中我多用一些实例

    2018-12-13
    9
  • 羊毛犬 ส็็็็็็
    @我来也 比如621中的1用 (1+590127) %7 会得到0。 但是如果固定是三位数的话,在解密时候就可以提前给首位补0。
    python 版本:(多位数,用反转 代替 对调一三位)

    ```
    # coding:utf-8

    DIVIDEND = 7
    RAND = 590127

    def encrypt(num):
        if not isinstance(num, int):
            raise TypeError("num is not 'int' object")
        # int转为list
        num = map(int, str(num))
        
        # 对每位加上随机数
        num = map(lambda i:i+RAND, num)
        # 保存商和求余
        quotient, num = zip(*[(i//DIVIDEND, i%DIVIDEND) for i in list(num)])
        # 反转
        num = list(num)[::-1]
        print(list(num))
        # list 转回 int
        num = map(str, num)
        # num = int(''.join(list(num)))
        num = ''.join(list(num)) # 首位余数0则会去除,所以用str

        # 返回加密数据和商
        return (num, quotient)


    def decrypt(num, quotient):
        #if not isinstance(num, int):
        # raise TypeError("num is not 'int' object")
        # int转为list
        num = map(int, str(num))
        
        # 反转
        num = list(num)[::-1]
        # 商和余求值
        for i,v in enumerate(num):
            num[i] = v + quotient[i] * DIVIDEND
        # 对每位减去随机数
        num = map(lambda i:i-RAND, num)
        
        # list 转回 int
        num = map(str, num)
        num = int(''.join(list(num)))
        
        return num

    if __name__ == '__main__':
        num = 8251
        print('加密', num)
        en_num, q = encrypt(num)
        print(f"加密后{en_num}, 商为{q} \n解密...")
        de_num = decrypt(en_num, q)
        print(de_num)

    ```

    作者回复: 感谢提供这么详尽的代码,另外Web版留言区好像也支持缩进格式了👍

    2019-02-14
    6
  • 逍遥思
    公式中,size指的是有限空间的数目而不是大小吧?100个有限空间,每个容量不小于1万

    作者回复: 对 是空间的数量 原文有歧义 稍后修改

    2018-12-17
    6
  • 石头
    public static int encryptionNum(int num) {
            System.out.println("加密前:" + num);
            // 1.取余 并 加上随机数
            int bit = num % 10;
            int tenBit = num % 100 / 10;
            int hundredBit = num % 1000 / 100;
            System.out.println(bit + "\t" + tenBit + "\t" + hundredBit);
            bit = bit + MAX;
            tenBit = tenBit + MAX;
            hundredBit = hundredBit + MAX;
            System.out.println(bit + "\t" + tenBit + "\t" + hundredBit);
            // 2.每个位数 除以7 取余代替原来的个十百
            bit = bit % MULTIPLE;
            tenBit = tenBit % MULTIPLE;
            hundredBit = hundredBit % MULTIPLE;
            System.out.println(bit + "\t" + tenBit + "\t" + hundredBit);
            // 3.swap 第一位和第三位
            int temp;
            temp = bit;
            bit = hundredBit;
            hundredBit = temp;
            System.out.println(bit + "\t" + tenBit + "\t" + hundredBit);
            int result = bit + tenBit * 10 + hundredBit * 100;
            System.out.println("加密结果为:" + result);
            return result;
        }
      public static int decryptNum(int num) {
            System.out.println("解密前:" + num);
            // 1.取余
            int bit = num % 10;
            int tenBit = num % 100 / 10;
            int hundredBit = num % 1000 / 100;
            // 2.交互位数
            int temp;
            temp = bit;
            bit = hundredBit;
            hundredBit = temp;
            // 3.乘回7的倍数
            // 这里可能有bug 只能针对当前的MAX值 如果换了一个随机值 要考虑 是否要+1
            int temp2 = (MAX / MULTIPLE) + 1;
            bit = bit + temp2 * MULTIPLE;
            tenBit = tenBit + temp2 * MULTIPLE;
            hundredBit = hundredBit + temp2 * MULTIPLE;
            // 4.减去随机数
            bit = bit - MAX;
            tenBit = tenBit - MAX;
            hundredBit = hundredBit - MAX;
            System.out.println(bit + "\t" + tenBit + "\t" + hundredBit);
            int result = bit + tenBit * 10 + hundredBit * 100;
            System.out.println("解密结果为:" + result);
            return result;
        }
    2018-12-12
    6
  • Solomon
    为老师最后的学习笔记点赞
    2018-12-12
    6
  • Lambert
    可以运用在周易罗盘排盘,十天干和十二地支组成六十甲子,模为60,可以排出现在是哪个布局

    作者回复: 这个例子很赞

    2019-01-17
    5
  • 他在她城断了弦
    之前的腾讯一面问到了快速存储定位大量数据的问题!!当时面试官提示了说用取余操作,今天再看到这感觉真是醍醐灌顶!!
    2018-12-20
    5
  • gltjk
    有的校验码算法也用了余数,比如身份证号末位就是前 12 位分别乘系数求和后模 11 算出来的,余数是 0 时还写成了X。

    作者回复: 没错 余数的应用很多

    2018-12-13
    1
    5
  • ncubrian
    随机数MAX每次都不一样的话,后面要找某个标号的记录,必须要能知道当初用的随机数吧?

    作者回复: 是的,需要记录下来

    2018-12-12
    5
  • 别喜欢我这种无赖
    散列就是一大堆没有规律排列的数字,对吧

    作者回复: 可以说是把一堆数字按照一定的规律分组。

    2019-02-20
    4
  • 计算机内存啊~按页式存储,段式存储,段页式之类的~

    作者回复: 对的 很好的例子

    2019-01-05
    4
收起评论
99+
返回
顶部