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

05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?

黄申 2018-12-19
你好,我是黄申。上一节的结尾,我们用递归模拟了数学归纳法的证明。同时,我也留下了一个问题:既然递归的函数值返回过程和基于循环的迭代法一致,我们直接用迭代法不就好了,为什么还要用递归的数学思想和编程方法呢?这是因为,在某些场景下,递归的解法比基于循环的迭代法更容易实现。这是为什么呢?我们继续来看舍罕王赏麦的故事。

如何在限定总和的情况下,求所有可能的加和方式?

舍罕王和他的宰相西萨·班·达依尔现在来到了当代。这次国王学乖了,他对宰相说:“这次我不用麦子奖赏你了,我直接给你货币。另外,我也不用棋盘了,我直接给你一个固定数额的奖赏。”
宰相思考了一下,回答道:“没问题,陛下,就按照您的意愿。不过,我有个小小的要求。那就是您能否列出所有可能的奖赏方式,让我自己来选呢?假设有四种面额的钱币,1 元、2 元、5 元和 10 元,而您一共给我 10 元,那您可以奖赏我 1 张 10 元,或者 10 张 1 元,或者 5 张 1 元外加 1 张 5 元等等。如果考虑每次奖赏的金额和先后顺序,那么最终一共有多少种不同的奖赏方式呢?”
让我们再次帮国王想想,如何解决这个难题吧。这个问题和之前的棋盘上放麦粒有所不同,它并不是要求你给出最终的总数,而是在限定总和的情况下,求所有可能的加和方式。你可能会想,虽然问题不一样,但是求和的重复性操作仍然是一样的,因此是否可以使用迭代法?好,让我们用迭代法来试一下。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(113)

  • 黄申 置顶
    由于暂时无法追加回复,我这里再回复一下网友debugtalk

    我看了Python的实现,果然很简介👍
    奖金的题目没问题。整数的因子分解有点小瑕疵,少了一些可能。比如,输入8,少了
    [1, 2, 2, 2]
    [1, 2, 4]
    [1, 4, 2]
    [2, 1, 2, 2]
    2018-12-20
    10
  • 杨景胜
    从递归的两个原则到代码实现有点跳跃, 想了半天还是没想明白这个代码的逻辑啊~
    2018-12-19
    2
    17
  • debugtalk
    Python 实现赏金问题:https://github.com/debugtalk/geektime-notes/blob/master/programmers-mathematics/chapter5.md
    Python 实现思考题:https://github.com/debugtalk/geektime-notes/blob/master/programmers-mathematics/chapter5.py

    作者回复: 很棒 我稍后sync下来看

    2018-12-19
    1
    9
  • 李尧
     思考题:请大神帮忙看下,输出少了个 [1,8]
    输出:[2, 2, 2, 1] [2, 4, 1][4, 2, 1][8, 1]

    import java.util.ArrayList;

    /**
     * @Auther: yli
     * @Date: 2018/12/19 17:19
     * @Description:
     */
    public class Iteration {

        public static void recursion(long total, ArrayList<Long> result){

            if (total == 1){
                result.add(1L);
                System.out.println(result);
                return;
            }else {
                for(long i = 2; i <= total; i ++){
                    ArrayList<Long> newList = (ArrayList<Long>)(result.clone());
                    newList.add(Long.valueOf(i));
                    if(total%i !=0){
                       continue;
                    }
                    recursion(total/i, newList);
                }
            }
        }

        public static void main(String[] args){
            long total = 8;
            recursion(total, new ArrayList<Long>());
        }
    }

    作者回复: 循环的时候不能少了1,可以在结果中判断是否已经涵盖1,我稍微修改了一下
    public static void recursion(long total, ArrayList<Long> result) {

    if (total == 1) {
    if (!result.contains(1L)) result.add(1L);
    System.out.println(result);
    return;
    } else {
    for (long i = 1; i <= total; i++) {
    if ((i == 1) && result.contains(1L)) continue;
    ArrayList<Long> newList = (ArrayList<Long>) (result.clone());
    newList.add(Long.valueOf(i));
    if (total % i != 0) {
    continue;
    }
    recursion(total / i, newList);
    }
    }
    }

    2018-12-19
    2
    7
  • 文刂 氵共 超
    整数分解 - C++代码
    #include <vector>
    #include <iostream>
    #include <algorithm>

    using namespace std;

    // 输出函数
    void PrintResult(vector<int> &Result)
    {
      for (size_t i = 0; i < Result.size(); ++i)
      {
        cout << Result[i] << " ";
      }
      cout << endl;
    }

    //数组中是否存在某值
    bool IsExit(vector<int> &Result, int value)
    {
      vector<int>::iterator result = std::find(Result.begin(), Result.end(), value);
      if (result == Result.end())
      {
        return false;
      }
      else
      {
        return true;
      }
    }

    //整数分解
    void RecursionAlgo(int Num, vector<int> &Result)
    {
      if (Num == 1)
      {
        PrintResult(Result);
        return;
      }
      for (int i = 1; i <= Num; ++i)
      {
        //判断1是否在解中
        if (IsExit(Result, 1))
        {
          if (i == 1)
          {
            continue;
          }
        }
        if (Num%i == 0)
        {
          vector<int> newResult = Result;
          newResult.push_back(i);

          RecursionAlgo(Num/i, newResult);
        }
      }
    }

    int _tmain(int argc, _TCHAR* argv[])
    {
      int Totalmoney = 10;
      vector<int> Result;

      RecursionAlgo(Totalmoney, Result);
      return 0;
    }

    作者回复: 回答很棒,下次可以将运行结果也贴出来👍

    2018-12-19
    6
  • debugtalk
    感谢 Sean 的指正,之前整数因子分解的解答的确存在问题,没有完整考虑整数 1 在各种位置的情况。
    现已更正:https://github.com/debugtalk/geektime-notes/blob/master/programmers-mathematics/chapter5.py
    2018-12-20
    3
  • 松原
    黄老师,这句“递归和循环其实都是迭代法的实现”我不太理解。
    如果递归和循环都属于迭代法,那么就是说递归是从属于迭代法的。而我所理解的迭代法的核心是从1到n的递推,而递归是从n到1的逐步求解的过程,两者应该是并列的关系。希望老师能解答我的这个困惑。

    作者回复: 确实两者的递推方向是不一样的,不过递归在计算机的实现中,是使用的函数调用,在满足条件后,函数开始逐级返回,这时候又是正向递推了,所以我觉得这也是从1到n

    2018-12-19
    3
  • 杨景胜
    //因数分解
    public static void getMultiFactors(long multi,ArrayList<Long> result){
            if (multi == 1){
                result.add(multi);
                System.out.println(result);
            }else{
                for (long i = 2; i <= multi; i++) {
                    if(multi % i == 0){
                        ArrayList<Long> newResult = (ArrayList<Long>) result.clone();
                        newResult.add(i);
                        getMultiFactors(multi / i,newResult);
                    }
                }
            }
        }

    作者回复: 如果循环从2开始,可能会漏掉一些情况,请参考为我给另一位网友李尧的回复

    2018-12-19
    3
  • Sawyer
    老师好,我实现了一个算法,但是没有打印出来1的情况。
    还有个问题就是,如果使用老师的示例输入8,结果既有 2x4,又有 4x2 这不是重复了吗?
    static void getFactorization(long product, ArrayList<Long> result) {
        for (int i = 2; i <= product / 2; i++) {
            if (0 == product % i) {
                ArrayList<Long> newResult = (ArrayList<Long>) result.clone();
                newResult.add((long) i);
                getFactorization(product / i, newResult);
                newResult.add(product / i);
                System.out.println(newResult);
            }
        }
    }

    作者回复: 这里作为教学案例,可以遍历所有情况,包括4x2和2x4。至于1,需要特殊处理一下,你可以思考看看,或者看看之前读者的留言

    2019-03-12
    2
  • 悬炫
    JavaScript的实现:
    赏金问题:
    /**
     *
     * @description 赏金问题
     * @param {number} totalReward 奖赏总金额
     * @param {array} result 保存当前的解
     * @param {array} rewards 可供选择的面额
     * @returns void
     */
    function get(totalReward, result=[],rewards = [1, 2, 5, 10]) {
        // 当 totalReward = 0 时,证明它是满足条件的解,结束嵌套调用,输出解
        if (totalReward === 0) {
            console.log(result.toString());
            // 当 totalReward < 0 时,证明它不是满足条件的解,不输出
        } else if(totalReward<0) {
            return;
        } else {
            for (let index = 0; index < rewards.length; index++) {
                let newResult =[...result];// 由于有 4 种情况,需要 clone 当前的解并传入被调用的函数
                newResult.push(rewards[index]);// 记录当前的选择,解决一点问题
                get(totalReward - rewards[index], newResult);// 剩下的问题,留给嵌套调用去解决
            }
        }
    }




    2019-01-28
    2
  • Youngggg
    import copy
    def get(num, result=[]):
        sum = 1
        for index in result:
            sum = sum * index
        if sum == num:
            print(result)
            if 1 not in result:
                result.append(1)
                print(result)
            return
        elif sum > num:
            return
        else:
            i=1
            while i<=num:
                if num%i != 0:
                    i = i+1
                    continue
                if i == 1 & 1 in result:
                    i = i+1
                    continue
                new_result = copy.copy(result)
                new_result.append(i)
                i = i+1
                get(num, new_result)

    get(8, [])

    [1, 2, 2, 2]
    [1, 2, 4]
    [1, 4, 2]
    [1, 8]
    [2, 1, 2, 2]
    [2, 1, 4]
    [2, 2, 1, 2]
    [2, 2, 2]
    [2, 2, 2, 1]
    [2, 4]
    [2, 4, 1]
    [4, 1, 2]
    [4, 2]
    [4, 2, 1]
    [8]
    [8, 1]
    2018-12-25
    2
  • icy
    # -*- coding: utf-8 -*-
    """
    Created on Mon Dec 24 14:30:38 2018
    @author: icytanz
    """

    import copy

    def get_mul_factor(num,result=[]):
        if(num==1):
            total=copy.copy(result)
            if 1 not in total:
                total.append(1)
            print(total)
            return
        elif(num<1):
            return
        else:
            n=list(range(num+1))
            n.reverse()
            if 1 in result:
                m=range(len(n)-2)
            else:
                m=range(len(n)-1)
            for i in m:
                new_result=copy.copy(result)
                if num%n[i]==0:
                    new_result.append(n[i])
                    get_mul_factor(num//n[i],new_result)
                    
    if __name__=='__main__':
        get_mul_factor(2)
        #[2, 1]
        #[1, 2]
        
        get_mul_factor(1)
        #[1]
        
        get_mul_factor(4)
        #[4, 1]
        #[2, 2, 1]
        #[2, 1, 2]
        #[1, 4]
        #[1, 2, 2]
        
        get_mul_factor(6)
        #[6, 1]
        #[3, 2, 1]
        #[3, 1, 2]
        #[2, 3, 1]
        #[2, 1, 3]
        #[1, 6]
        #[1, 3, 2]
        #[1, 2, 3]
        
        get_mul_factor(8)
        #[8, 1]
        #[4, 2, 1]
        #[4, 1, 2]
        #[2, 4, 1]
        #[2, 2, 2, 1]
        #[2, 2, 1, 2]
        #[2, 1, 4]
        #[2, 1, 2, 2]
        #[1, 8]
        #[1, 4, 2]
        #[1, 2, 4]
        #[1, 2, 2, 2]
    2018-12-24
    2
  • hallon
    思考题,用js实现如下:
    function mul(totalReward, result) {
        //i从自身开始循环到1,每次递减1
        for(var i=totalReward; i>0; i--) {
            if(totalReward % i == 0) {//能整除i
                var newResult = result.concat();
                newResult.push(i);
                if(i == totalReward) {//i为自身的情况,结果就是[totalReward,1]
                    newResult.push(1);
                    console.log(newResult);
                } else if(i == 1) {//i为1的情况,结果就是[1,totalReward]
                    newResult.push(totalReward);
                    console.log(newResult);
                }else {//除以i之后,继续分解
                     mul(totalReward/i, newResult);
                }
            }
        }
    }
    测试:数字6和8
    var b = [];
    mul(6, b);
    mul(8, b);
    结果如下:
    [ 6, 1 ]
    [ 3, 2, 1 ]
    [ 3, 1, 2 ]
    [ 2, 3, 1 ]
    [ 2, 1, 3 ]
    [ 1, 6 ]

    [ 8, 1 ]
    [ 4, 2, 1 ]
    [ 4, 1, 2 ]
    [ 2, 4, 1 ]
    [ 2, 2, 2, 1 ]
    [ 2, 2, 1, 2 ]
    [ 2, 1, 4 ]
    [ 1, 8 ]
    2018-12-21
    2
  • 郑晨Cc
    package 二进制;

    import java.util.ArrayList;

    public class Lesson5Test {

    public int counter = 0;



    public void chosen(int num,ArrayList list){

    if(null==list){
    list = new ArrayList();
    list.add(1);
    list.add(num);
    }

    if(num==1){ //递归终止
    return;
    }

    for(int i=1;i<=num;i++ ){
    if(i==1){
    System.out.println(list);
    counter++;
    continue;

    }
    if(i==num){
    list.add(1);
    list.remove(0);
    System.out.println(list);
    counter++;
    continue;

    }

    if(num%i==0){
    int a = num/i;
    ArrayList list2 = new ArrayList(list);
    list2.remove(list.size()-1);
    list2.add(i);
    list2.add(a);
    chosen(num/i,list2);
    }
    }

    }

    public static void main(String[] args){

    Lesson5Test too = new Lesson5Test();

    too.chosen(8, null);
    System.out.println("总数:"+too.counter);

    }

    }


    控制台输出:
    [1, 8]
    [1, 2, 4]
    [1, 2, 2, 2]
    [2, 2, 2, 1]
    [2, 4, 1]
    [1, 4, 2]
    [4, 2, 1]
    [8, 1]
    总数:8
    2018-12-20
    2
  • miracle
    我来答下吧,案例中的n代表已经迭代的次数,在这个案例中,限制了每轮迭代只有四种选择
    2018-12-19
    2
  • Geek_zy
    public class RecusionTwo {
        public RecusionTwo(int n){
            this.n =n;
        }
        private static int n;

        public static void get(ArrayList<Integer> result){
            int product =1;
            for(int j=0;j<result.size();j++){
                product*=result.get(j);
            }
            if(product == n){
                System.out.println(result);
                return;
            }else if(product>n){
                return;
            }else {
                for (int i=1; i <= n; i++) {
                    int count = 1;
                    if(i==1){
                     for(int j=0;j<result.size();j++){
                         if(result.get(j)==1){
                             count++;
                         }
                     }
                    }
                    if(count>1){
                        continue;
                    }
                     ArrayList<Integer> newResult = (ArrayList<Integer>) result.clone();
                     newResult.add(i);
                     get( newResult);

                }
            }
        }

        public static void main(String[] args) {

            RecusionTwo recusionTwo = new RecusionTwo(8);
            get(new ArrayList<>());
        }
    }
    2019-04-28
    1
  • 方得始终
    参考老师和其他同学的留言, 下面是Pythoni实现的思考题, 应该是个较为简洁的版本.
    import copy

    def prod_factors(num, result=[]):
        if num == 1:
            print('x'.join([str(_) for _ in result]))
            if 1 not in result:
                result.append(1)
                print('x'.join([str(_) for _ in result]))
        elif num < 0:
            return
        else:
            for i in range(1, num+1):
                if (i == 1 and i not in result) or (i !=1 and num % i == 0):
                    newresult = copy.copy(result)
                    newresult.append(i)
                    prod_factors(num/i, newresult)


    prod_factors(8)
    1x2x2x2
    1x2x4
    1x4x2
    1x8
    2x1x2x2
    2x1x4
    2x2x1x2
    2x2x2
    2x2x2x1
    2x4
    2x4x1
    4x1x2
    4x2
    4x2x1
    8
    8x1

    作者回复: 同时考虑了1出现和不出现的情况 👍

    2018-12-29
    1
  • somenzz
    这里贴代码对Python这种缩进语言来讲很不友好啊,建议可以提交图片或者支持md格式。说下自己的思路:一个整数num 对 num 到 1 之间的整数 i 分别求余,如果余数为0,说明这是一个因子,将 i 添加到结果列表里,然后再让num 对 i 取整,得到 k ,对整数 K 再次递归求解。退出条件,如果 num == 1,那么将 1 添加到结果列表里,并打印结果列表。这里要注意下,如果 i == 1 ,也是退出条件,此时将 num 加入结果列表并打印。因为,一个大于1的数据除以1,永远得不到1 ,也就达不到前面的退出条件。源代码见 https://github.com/somenzz/geekbang/blob/master/mathOfProgramer/chapter05_recursion_1.py

    作者回复: 少了一些可能。比如,输入8,少了
    [1, 2, 2, 2]
    [1, 2, 4]
    [1, 4, 2]
    [2, 1, 2, 2]

    2018-12-20
    1
  • 文刂 氵共 超
    使用C++实现赏金问题
    #include <vector>
    #include <iostream>

    using namespace std;

    // totalmoney : 总金额
    // select : 钱币面额的选择列表
    // Result : 结果列表
    void RecursionAlgo(int Totalmoney, vector<int> &Select, vector<int> &Result)
    {
    //每次递归需要用总金额减去使用的面额,直到Totalmoney=0,表示找到解
    if (Totalmoney == 0)
    {
    for (size_t i = 0; i < Result.size(); ++i)
    {
    cout << Result[i] << " ";
    }
    cout << endl;
    return;
    }
    //Totalmoney < 0, 不符合标准 返回
    else if (Totalmoney < 0)
    {
    return;
    }
    else
    {
    for (size_t i = 0; i < Select.size(); ++i)
    {
    vector<int> newResult = Result;
    newResult.push_back(Select[i]);
    RecursionAlgo(Totalmoney-Select[i], Select, newResult);
    }
    }
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    int Totalmoney = 10;

    int ia[] = {1, 2, 5, 10};
    vector<int> Select(ia, ia+4);
    vector<int> Result;

    RecursionAlgo(Totalmoney, Select, Result);
    return 0;
    }
    2018-12-19
    1
  • cocu
    这个案例中的n到底是什么,是奖励总金额,还是取的纸币数?

    作者回复: 这里我统一回答一下,是当前迭代的次数,也就是取的纸币数量

    2018-12-19
    1
收起评论
99+
返回
顶部