数学、概率问题

发表于 | 更新于: | 分类于

1079 活字印刷

输入：”AAB”
输出：8
解释：可能的序列为 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int numTilePossibilities(String tiles) {
    int rst = 0;
    int[] cnt = new int[26];
    for(char c:tiles.toCharArray()){
        cnt[c-'A']++;
    }
    return back(cnt);    
}
private int back(int[] cnt){   
   int sum = 0;
    // 长度为1的 a,b
    // 长度为2的 aa,ab,ba
    // 长度为3的 aab,aba,baa
    for(int i =0;i<26;i++){
        if(cnt[i]==0)continue;
        sum++;
        cnt[i]--;
        sum+=back(cnt);
        cnt[i]++;
    }
    return sum;
}

方法1
If we have a string of size n with i unique characters, and each character repeats m[i] times, the number of unique permutations is:

n! / (m[1]! m[2]! .. * m[i]!)
要计算出所有组合的排列数的累加

称硬币的最少次数
http://sighsmile.github.io/2017-08-02-weighing-puzzle/
相当于把硬币分为三份：天平两侧各一份，其余硬币为一份。如果天平是平衡的，则假币在其余硬币那一份中；如果不平衡，则假币在天平某一侧的一份中，若假币更轻，则假币在更轻的一份中，否则在更重的一份中。因此，容易想到基于三进制的编号来解决这道问题。

!!172 Factorial Trailing Zeroes 阶乘后面后几个0

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

2一定比5多，算一下这些数一共有多少个5.

1
2
3
4
5
6
7
8
public int trailingZeroes(int n) {
   int rst = 0;
    while(n != 0){
        rst += n/5;
        n/=5;
    }
    return rst;
}

343 Integer Break 和固定的数字的最大乘积

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

对f(x)=x^(x/n) 求导f(x)’，得到x=e的时候最大
最接近的是3，然后取2….? 反正>4的用3..

1
2
3
4
5
6
7
8
9
10
public int integerBreak(int n) {
   int[] dp = new int[n + 1];
   dp[1] = 1;
   for(int i = 2; i <= n; i ++) {
       for(int j = 1; j < i; j ++) {
           dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
       }
   }
   return dp[n];
}

43 Multiply Strings 大数相乘

Input: num1 = “2”, num2 = “3”
Output: “6”

两个关键位置i+j,i+j+1。并且记住右边那个是取模，左边那个是累加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String multiply(String num1, String num2) {
    int n = num1.length();
    int m = num2.length();
    StringBuilder sb = new StringBuilder();
    int[] rst = new int[m+n];
    for(int i = n-1;i>=0;i--){
        for(int j = m-1;j>=0;j--){
            int mul = (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
            int p1 = i+j,p2 = i+j+1;
            mul += rst[p2];
            rst[p2] = mul%10;
            rst[p1] += mul/10;
        }
    }
    for(int num:rst){
        if(sb.length()==0 && num == 0)continue;
        sb.append(num);
    }
    return sb.length()==0?"0":sb.toString();
}

233 Number of Digit One [1,n]中数字带1的个数

Input: 13
Output: 6
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

不会
https://leetcode.com/problems/number-of-digit-one/discuss/64381/4%2B-lines-O(log-n)-C%2B%2BJavaPython

1
2
3
4
5
6
public int countDigitOne(int n) {
    int ones = 0;
    for (long m = 1; m <= n; m *= 10)
        ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
    return ones;
}

m个芒果n个人

https://www.geeksforgeeks.org/count-ways-to-distribute-m-items-among-n-people/
1）m个芒果，n个人，如果物品和人都是相同的
用n个人划分芒果，需要n-1个划分。 所有芒果的排列和划分的排列一共是(m+n-1)!种排列。
因为芒果是相同的，而且人也是相同的，所以把相同的分法去掉就是(m+n-1)!/((n-1)!*(m)!)

二项式系数(组合数）：C(N,K) = factorial(N)/factorial(K)*factorial(N-K)
m芒果n个人就是二项式系数C(N-1+M) = F()

19本书，编号1-19，取5本，任意两本不相邻的取法有：

14本书15个空，插空放5本书
C(15,5)

9宫格连线密码一共有389112方案数。

一根木棍截成三段，组成三角形的概率是多少？

棍长a，设边长x,y,a-x-y.得到可行域x+y<a.
用3个两边之和>第三边得到3个不等式，得到小三角形。是大三角形的1/4

两个人轮流掷（6面）骰子，先掷出6的人获胜，先手者获胜的概率是多少？

决出胜负：1-5/6*5/6
先手胜:1/6
p(先手|决出胜负) = 1/6 / 11/36 = 6/11

有6个洞 编号9个球，求球入洞的方案数

隔板法：

  1. 划分6个洞需要5个隔板，用1~9填充隔板的空间。变成5个隔板和9个球的全排列。
  2. 5个隔板是相同的，P（14,5,1,1,1,1,1,1,1,1,1,1) = 14!/5!

另一种方法：

  1. 1号球可以放6个位置
  2. 1号球等于把空间又划分成了1前和1后，2球有5+2种可能
  3. 同理 3号球有7-1+2 =8个可能…
  4. 6乘到14 = 14!/5!

12本书按 4:4:4平均分给3个人，有多少种分法

C(12,4)C(8,4)C(4,4)

12本书按 3:3:2:2:2分给 ABCDE 5个人

A(5,5)C(12,3)C(9,3)C(6,2)C(4,2)C(2,2)/(A(3,3)A(2,2))

10个小朋友做游戏，分成四组，每组人数分别为2，2，3，3，请问有几种分组方法

C(10,2)C(8,2)C(6,3)C(3,3)/A(2,2)*A(2,2)

52张牌分发给4个人，每人13张，问每人有一张A的概率有多少？
10.55%

52张牌分发给4个人，每人13张的方法数为52！/(13!)^4 。
每人发一张A的方法数为4！* 48！/(12!)^4 .

4个相同的桔子和6个不同的苹果放到5个不同的盒子中，问每个盒子里有2个水果的概率有多大？
7.4%

把4个相同桔子放入5个不同盒子的放法数为C(5,4),
把6个不同苹果放入5个不同盒子的放法数为5^6 .因此总的分配方法数为C(5,4)*5^6 .

每个盒子有2个水果，有如下三种情况：

1
2
3
4
5
6
1、（AA)(AA)(AA)(OO)(OO)
C(5,2)*6!/2!/2!/2!
2、AA)(AA)(OA)(OA)(OO)
C(5,1)\*C(4,2)\*6!/2!/2!
3.（AA)(OA)(OA)(OA)(OA)
C(5,4)*6!/2!

将n个不同的球放入编号为1,2,…,k的k个盒子中，试求：

  1. 第一个盒子是空盒的概率: 第一个盒子是空盒的方案数为(k－1) n 。
  2. 设k≥n,求n个球落入n个不同盒子的概率: n个球落入n个不同盒子的方案数为C(k,n)n!。
  3. 第一盒或第二盒两盒中至少一个是空盒的概率。该方案数为第一个盒子是空盒的方案数加上第二个
    盒子是空盒的方案数，再减去两个盒子都是空盒的方案
    数。

随机地将15名插班生分配到三个班级，每班各5名。设15名插班生中有3为女生。试求：
将15名插班生分配到三个班级，每班各5名的方案数为C(15,5)C(10,5)C(5,5)=15!/(5!5!5!)。

  1. 每一个班级分到一名女生的概率:3!*12!/(4!4!4!)
  2. 三名女生分到同一班的概率: 3*12!/(5!5!2!)

歌单：
3个红球3个白球，红球2分，白球3分，问总分5分的拿法有多少种？

有4副相同的牌,每副牌有4张不同的牌.先从这16张牌中,随机选4张出来.然后,在这4张牌中随机选择一张牌,然后把抽出的一张放回3张中,再随机选择一张牌.与上次选出的牌一样的概率是()
正确答案: C 你的答案: F (错误)
1/4
1/3
2/5
1/2
2/3
3/4

某体校选择校服,每套校服都包括短袖运动衫,长袖运动衫,厚外套,运动长裤和运动短裤组成.每种运动服有3个备选方案.老师请了部分学生来挑选自己喜欢的校服.结果发现任意3个学生都至少在一种运动服上选择互不相同,那么老师最多邀请了()名学生参加挑选.
正确答案: B 你的答案: E (错误)
7
8
9
10
11
12

任意3个学生都至少在一种运动服上选择互不相同翻译过来就是说对于每种不同的选择，最多有2个人选择。

有100个金币，分给10个人.第一个金币等概率地分给10个人之一.之后的每一个金币分配给第K个人的概率正比于这个人已经持有的金币数+1.在这样的分配机制下，关于每个人最终的金币个数的分布的说法错误的是()
正确答案: B 你的答案: B (正确)
A每个人得到的金币的个数的期望是相等的
B每个人的金币个数接近均匀分布
C第一个金币给哪个人,哪个人的最终金币个数的期望就会更大
D在中间的某个阶段金币个数越多的人，未来获得金币的可能性越大

21点

21点是一种扑克游戏。如果玩家拿到扑克牌的点数总和超过21点则称为爆点，被判失败。其中A牌可以被记为11点或者1点，J, Q, K 都记为10点。如果用一副牌玩游戏（52张牌），玩家手上拿到一个K和6。那他再抽两张牌会爆点的可能性约有多大？()

(1) 93.7% 或 93.8% 或 93.7 或 93.8

十字交叉法 平均数 总体平均数

三部门人员平均年龄分别为38岁、24岁、42岁。A和B 两部门人员平均年龄为30岁，B和C两部门人员平均年龄为34岁。这三个部门全体人员的平均年龄为多少岁？
38a+24b = 30(a+b)
24b+42c = 34(b+c)
a:b:c = 3:4:5
(38x3+24x4+42x5)/12 = 35

https://blog.csdn.net/MrChen11/article/details/47114877

最大似然估计、最大后验估计、贝叶斯估计 最小二乘

https://blog.csdn.net/yangliuy/article/details/8296481
进行20次投硬币的伯努利实验，出现正面12次，反面8次，请分别用最大似然估计、最大后验估计、贝叶斯估计估计三种方法来估计“正面出现”的概率p. [注：n次伯努利实验服从二项分布 B(n, p)]

最大似然估计MLP：似然函数：$p(X|\theta)$
用似然函数取最大值的参数作为估计值。
参数是p 每次正面的概率。 12/20。

最大后验估计MAP：后验概率：$p(\theta|X)$
贝叶斯公式中的先验概率根据经验0.5
用到了beta分布 要设置beta分布的超参数a,b，让先验分布在0.5取最大值。

贝叶斯估计：不是直接求参数，而是求参数的分布

LSE

硬币相关问题

p112 3.39 连续仍硬币，A正反胜，B反反胜，A赢的概率?

3/4
coinflip.jpg

A赢： 先正后反， B赢 连续两次反面：A胜的概率 3/4

B 赢概率是1/2*1/2 = 1/4

http://www.raychase.net/3144
正正反 甲赢 正反反 乙赢 Penney’s game

penneygame.jpg

使用长度为3字节的序列，玩家B相对玩家A有优势。这是因为这个游戏是一个非传递博弈，所以无论如何选定第一个序列，总会有一个序列有更大的获胜概率。

反反正:正反反 = 1：3
因为只要出现一次正，想得到反反正的人就必输了，他肯定得先看到两次反，我就得到正反反了。
两个硬币4种情况有3种有正

正正反：反正正 = 1：3
只要出现一次反，反正正就赢了。

正反反HTT：正正反HHT = 1:2
反正正thh:反反正tth = 1：2

https://en.wikipedia.org/wiki/Penney%27s_game
对于二号玩家：1-2-3 -> (not-2)-1-2
第一个字节与1号玩家的第二个字节相反，
第二个字节与1号玩家的第一个字节相同，
第三个字节与1号玩家的第二个字节相同。

http://www.matrix67.com/blog/archives/3638

所有 1 都不相邻的 k 位 01 串有 Fk+2 个 Fi 表示 Fibonacci 数列中的第 i 项

抛掷第 k 次才出现连续两个正面”的意思就是， k 位 01 串的末三位是 011，并且前面 k – 3 位中的数字 1 都不相邻。 k-3位的01不相邻的串有F(k-1)个

平均需要抛掷多少次硬币，才会首次出现连续的 n 个正面？

答案是 2^(n+1) – 2
神奇的模式概率与“鞅”//todo
http://www.math-engineering.uestc.edu.cn/
模式的平均等待时间：
模式 HHHHHH 的平均等待时间 126

扔硬币直到连续两次出现正面，求扔的期望次数 6

• 扔到的是反面，那么还期望抛 E 次，因为抛到反面完全没用，总数就期望抛 E+1，所以是0.5*(1 + E)
• 扔到的是正面，如果下一次是反面，那么相当于重头来过，总数就期望抛，则是0.25*(2 + E)
• 扔到两次，都是正面，总数是 2，则是0.25*2注意2
所以递归来看E = 0.5*(1 + E) + 0.25*(2 + E) + 0.25*2，解得E = 6

反复投掷一个均匀的硬币直到正面向上为止，则期望投掷次数为 2

当xxx长度为n时，期望为$2^{n+1} - 2$

快手发了10个月饼，已知月神一天至少吃一个月饼；请问，月神在3天内将10个月饼全部吃完的概率为：

10个月饼，分割，9个空。
总的可能性是2^9. 第一天是C(9,0),第二天C（9，1）第三天C（9,3)

期望（均值）

随机变量平均下来会取怎样的值

如果5局3胜，两人出100赌本，赢的人得200
甲已2胜，乙1胜，继续两局的可能是甲甲、甲乙、乙乙、乙甲
甲的期望获得的收益是：200 x 3/4 +0 x 1/4 =150
乙期望是200 x 1/4 +0 x3/4 = 50

离散型随机变量出现的概率就是取值的权重。
所以加权算术平均数
(p1 x a1 + p2 x a2) /(p1 + p2) = (p1 x a1 + p2 x a2)

绝对收敛 => 黎曼定理 => 交换律可以用
随机试验结果次序是任意的，所以按任意次序算期望应该是一样的。
所以无穷项 随机变量 的期望 级数是绝对收敛的。

连续型是 xp(x) 从-∞到+∞的广义积分 也是绝对收敛。

01分布 两点分布

二项分布 期望np

https://baike.baidu.com/item/%E4%BA%8C%E9%A1%B9%E5%88%86%E5%B8%83
在n重伯努利试验中，事件A恰好发生k次的概率为
在伯努利试验序列中，事件A在第 k 次试验中才首次发生的概率为
bip.jpg

泊松分布 期望λ

1
2
from scipy.stats import poisson
rv = poisson(mu=5)

https://baike.baidu.com/item/%E6%B3%8A%E6%9D%BE%E5%88%86%E5%B8%83
当二项分布的n很大而p很小时，泊松分布可作为二项分布的近似，其中λ为np。
posoe.jpg
每天中午12点 等待地铁的人数

均匀分布 期望(a+b)/2

指数分布

泊松过程中，第k次随机事件与第k+1次随机事件出现的时间间隔服从指数分布。
果T是某一元件的寿命，已知元件使用了t小时，它总共使用至少s+t小时的条件概率，与从开始使用时算起它使用至少s小时的概率相等。

正态分布

随机变量的函数的期望Y=g(x)

假设x的分布已知
Y的期望就是g(x)的期望

矩

https://baike.baidu.com/item/%E5%8E%9F%E7%82%B9%E7%9F%A9
一阶原点距是期望
二阶中心距是方差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from scipy.stats import binom
rv = binom(10,0.2) # n = 10 p = .2
## 期望 10 x 0.2 
print(rv.mean())
## 方差 10 x 0.2 x 0.8
print(rv.var())
## 一阶原点矩 就是期望
print(rv.moment(1))
## 二阶矩
print(rv.moment(2))
## 方差= (2阶距- 1阶矩^2 )
print(rv.moment(2) - rv.moment(1)**2)
## 期望 方差 偏度 峰度
print(rv.stats(moments='mvsk'))

方差公式：
fangcha.jpg

参数估计

矩估计 中心矩 x和中心ex的差的k次方的期望 样本矩
点估计

有分配对象的排列组合问题
https://zhuanlan.zhihu.com/p/27017390
分组分配问题
http://blog.sina.com.cn/s/blog_50a269f00100haxo.html

概率生成函数 概率母函数

1.x的系数是a1,a2,…an 的单个组合的全体。
2.x^2的系数是a1,a2,…a2的两个组合的全体。
………
n. x^n的系数是a1,a2,….an的n个组合的全体（只有1个）。

有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？

设x表示砝码，x的指数表示砝码的重量
1个1克的砝码可以用函数1+1*x^1表示，
1个2克的砝码可以用函数1+1*x^2表示，
1个3克的砝码可以用函数1+1*x^3表示，
1个4克的砝码可以用函数1+1*x^4表示，

1表示数量0个
例如1个2克的砝码：1+x^2
1其实应该写为：1*x^0,即1代表重量为2的砝码数量为0个。

  • 系数表示状态数（方案数）
    1+x^2，也就是1x^0 + 1x^2，不取2克砝码，有1种状态；或者取2克砝码，也有1种
    状态。
1
2
3
(1+x)(1+x^2)(1+x^3)(1+x^4)
=(1+x+x^2+x^4)(1+x^3+^4+x^7)
=1 + x + x^2 + 2*x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 + x^8 + x^9 + x^10

从上面的函数知道：可称出从1克到10克，系数便是方案数。
有2*x^5 项，即称出5克的方案有2种：5=3+2=4+1；

求用1分、2分、3分的邮票贴出不同数值的方案数：每种是无限的。

分配问题及应用

fenpei.jpg

排列

村长带着 4 对父子参加爸爸去哪儿第三季第二站某村庄的拍摄。村里为了保护小孩不被拐走有个前年的规矩，那就是吃饭的时候小孩左右只能是其他小孩或者自己的父母。那么 4 对父子在圆桌上共有___种坐法。 （旋转一下，每个人面对的方向变更后算是一种新的坐法）

Little定律

系统中物体的平均数量等于物体到达系统的平均速率和物体在系统中停留的平均时间的乘积

如果一个博物馆参观者到达的速率是每分钟 20 人，平均每个人在馆内停留20分钟，那么该博物馆至少需要容纳__人才行？
400

鸽策略鹰策略

多重排列：pingpang中有重复2个p 2个n 2个g

1
2
3
4
1. 标记为p1p2n1n2g1g2ia 全排列个数是8!
2. p的重复度 为p1p2的全排列 2!
3. P(N,r1,r2...rt)  标记为P(8;2,2,2,1,1)
4. P(8;2,2,2,1,1)\*2!\*2!\*2! = 8!

理解二项式定理(a+b)^n
abbinary.jpg
通项是a^k b^(n-k) 前面的系数表示 n个数的可重排列，a有k个，b有n-k个

不仅是二项式
通项是a1^(r1) a2^(r2) at^(rt)
nbinary.jpg
(x1+x2+…+xm)^n 展开式的项数等于C(n+m-1,n).