数学理论
- 一、编程计算
- 1. 编程计算规则
- 2. 编程计算符号
- 3. 特殊计算符号
- 二、数学原理
- 1. 加法原理
- 2. 乘法原理
- 3. 容斥原理
- 4. 排列组合
一、编程计算
1. 编程计算规则
编程计算优先级:算数运算符(数学运算) > > > 比较运算符(大于、小于等) > > > 逻辑运算符(非、与、条件等) > > > 赋值运算符(+=
、-=
等) > > > ,
运算符
2. 编程计算符号
运算符 | 表示方法 |
---|---|
非 | ¬ ¬ ¬ |
与 | ∧ ∧ ∧ |
或 | ∨ ∨ ∨ |
异或 | ⊕ ⊕ ⊕ |
3. 特殊计算符号
与运算:从左到右遍历所有的条件,一旦返现一个 0
,整个表达式就是 0
。
或运算:从左到右遍历所有的条件,一旦发现一个 1
,整个表达式就是 1
。
所以上述的两种运算都有短路。
二、数学原理
1. 加法原理
加法原理的核心思想:如果一个问题可以分解成互不相交的多个子问题,那么问题的总数目等于各个子问题的数目之和。
2. 乘法原理
乘法原理的核心思想:如果一个过程可以分为 n n n 个独立的步骤,其中第 i i i 个步骤有 m i m_i mi 种选择方式,那么整个过程的选择方式数目为 m 1 × m 2 × ⋯ × m n m_1 × m_2 × \cdots × m_n m1×m2×⋯×mn。
3. 容斥原理
容斥原理的核心思想:用于计算两个集合的并集的大小,通过减去两个集合的交集的大小来避免重复计算。
4. 排列组合
n n n 个不同的元素的全排列有 n ! n! n! 种方式。
n n n 个不用的元素中要选择 m m m 个元素进行全排列有 A n m = n ! ( n − m ) ! \text{A} ^m _n = \frac{n!}{(n-m)!} Anm=(n−m)!n! 种方式,也利用了容斥原理。
n n n 个不同的元素种要选择 m m m 个元素不考虑排序有 C n − 1 m − 1 = n ! m ! ( n − m ) ! = A n m m ! \text{C} ^{m-1} _{n-1} = \frac{n!}{m!(n-m)!}=\frac{\text{A}_n^m}{m!} Cn−1m−1=m!(n−m)!n!=m!Anm
方法:
- 捆绑法
当要求两个物品需要相邻的时候,就可以将两个物品看作一个物品,那么总共的种数有( s s s:表示捆绑的物品数): 1 × s ! 1 \times s! 1×s!。 - 插空法
当要求两个物品不能相邻的时候,就可以,那么总共的种数有( n n n:表示总数): ( n − s ) ! × A n − 1 s (n-s)! \times \text{A}_{n-1} ^{s} (n−s)!×An−1s。 - 砍刀法
n n n 个物品分成 m m m 组( n > m n>m n>m),每个组至少有 1 1 1 个物品,那么总共的分法有: C n m − 1 C_n ^{m-1} Cnm−1 种。 - 围圈法
n n n 个物品围成一个圈,共有 ( n − 1 ) ! (n-1)! (n−1)! 种围法。 - 分组法
n n n 个物品分成 x ( 个 / 组 ) x(^个/_组) x(个/组),不同的组队情况有 C n x × C n − x x × 1 \text{C}_n ^x \times \text{C}_{n-x}^x\times 1 Cnx×Cn−xx×1 - 最不利原则
n n n 个物品有 x 1 x_1 x1 个 a a a 类型、 x 2 x_2 x2 个 b b b 类型、…,那么摸到 z z z 类型至少需要 x 1 + x 2 + ⋯ ( 其他的数量 ) x_1+x_2+\cdots(其他的数量) x1+x2+⋯(其他的数量) 次摸到。 - 抽屉原理
数量最多的抽屉就是 n n n(总数) ÷ x \div x ÷x(份数)向上取整。