美文网首页
程序员的数学I

程序员的数学I

作者: 锅巴GG | 来源:发表于2016-02-10 23:00 被阅读74次

排列组合 I 解决计数问题的方法

  • 计数——与整数的对应关系

计数就是计数对象和整数的对应起来的过程,注意两点:

  1. 遗漏
  2. 重复

如果需要计数的对象多到无法数数,就需要找到和整数之间的对应规则,为此,我们必须理解计数对象具有怎么样的特性和结构

  • 思考:植树问题,在10米长的路上,从路的一端起每隔1米种一棵树,那么需要种多少棵树?

0,1,2,...10 不要忘记0哦,所以是11棵树
10/1的结果是间隔数
抽象 n米种树n+1棵

  • 思考:内存中排列着程序要处理的100个数据,从第一个数据开始编号为0,依此类推最后一个数据的编号是?

99号
归纳总结 第k个数据是k-1号

加法法则

加法法则就是将无“重复”元素的两个集合A,B相加,得到A和B并集的元素数

  • A并B的元素数 = A的元素数 + B的元素数
  • 加法法则只在集合中元素无重复的条件下成立

容斥原理

  • 思考:控制亮灯的扑克牌,一副牌有(1->K)13个级别,假设J,Q,K用11,12,13代替,在你面前放一个装置,往里面放1张牌,它就会根据牌的级别控制灯泡的亮灭。我们设放入的牌的级别为n(1-13的整数)
    1. 若n是2的倍数,则亮灯
    2. 若n是3的倍数,也亮灯
    3. 若n既不是2的倍数,也不是3的倍数,则灭灯
      往这个装置中依次放入13(1...13)张牌,其中亮灯的有多少张牌呢?

答案:6+4 -2 = 8
利用了容斥原理,2的倍数和3的倍数如果有重复的倍数,就是6,6的倍数有两次→6,12 2的倍数的个数6加上3的倍数的个数4,减去重复的倍数的个数2,就是答案

  • 容斥原理就是考虑了重复元素的加法法则
    集合A、B的元素总和 = A的元素数 + B的元素数 - A和B共同的元素数

乘法法则

根据两个集合进行配对的法则

  • 思考:一副牌中四种花色,每个花色13张牌,那么总共有几张牌?

4 * 13 = 52
A和B两个集合,所有元素分别结合起来,组合的总数就是相乘得到的结果

  • 思考:将三个骰子(1-6点)并列放置,形成3位数,一共能形成多少个数字?

没错,6 * 6 * 6 = 216

  • 思考:32个灯泡一排,每个灯泡可以亮灭,问共有多少种亮灭模式

每一种2个,2x2x2......2(共32个)
2^32=4294967296

置换

将n个事物按顺序进行排列称作置换(subsitution)

  • 思考:3张牌的置换,如果将A,B,C三张牌按照ABC,ACB,BAC等顺序排列,共有多少种排法?

6种
可以看出,第一张牌有3种选法,第二张牌有2种,第三张牌有1种,3 * 2 * 1 = 6
对,这就是阶乘1!=1 2!=2 3!=6 4!=24

排列组合II

  • 思考:从5张牌中任意取出3张进行排列,请问有多少种排列方法?

答案明天揭晓~

相关文章

  • 《程序员的数学I》

    简书不支持LaTex... 余数 周期性和分组 思考:奇数和偶数 奇数是被2除余1的整数偶数是被2整除(余0)的...

  • 程序员的数学I

    排列组合 I 解决计数问题的方法 计数——与整数的对应关系 计数就是计数对象和整数的对应起来的过程,注意两点:遗漏...

  • 程序员的数学I

    数序归纳法——如何征服无穷序列 高斯求和 思考题——存钱罐里的钱 第1天,往存钱罐里投入1元,存钱罐总金额为1元第...

  • 程序员的数学I

    递归——自己定义自己 GNU是什么的缩写?“GNU is Not Unix”这里面的GNU又是什么的缩写?“GNU...

  • 程序员的数学I

    排列组合II 思考:从5张牌中任意取出3张进行排列(permutation),请问有多少种排列方法? 排列和置换相...

  • 程序员的数学I

    递归——自己定义自己2 思考:和的定义 假设n为0以上的整数,使用递归的方式从0到n的整数之和。n=0时, S(n...

  • Atitit 程序员的数学艾提拉读后感 1.1.程序员的数

    Atitit 程序员的数学艾提拉读后感 [if !supportLists]1.1.[endif]程序员的数学 第...

  • 一份必不可少的程序员“内功”书单

    含PDF下载链接,后期持续更新 大话设计模式 大话数据结构 代码整洁之道 程序员的数学1-数学思维 程序员的数学2...

  • 《程序员的数学》轻松掌握“数学思维”,附下载链接

    对于程序员来说,数学很重要吗?如果数学不好,是否可以成为一名程序员呢?答案是肯定的。 不可否认,行业中许多程序员,...

  • 书单

    《3D数学基础》《代码大全2》《CLR Via C#》《程序员的数学》

网友评论

      本文标题:程序员的数学I

      本文链接:https://www.haomeiwen.com/subject/ctfukttx.html