程序员的数学一（5-8章）
排列组合——解决计数问题的方法
认清计数对象的性质，不遗漏，不重复地去数
1.植树问题——不要忘记0
2.容斥原理——principle of inclusion and exclusion
集合A.B的元素总数=A的元素数+B的元素数-A和B共同的元素数
置换（substitution）——将n个事物按顺序进行排列
排列（permutation）——从n个事物中取出一部分进行排列
可使用鸽巢原理——鸽巢定理
组合（combination）——不考虑顺序的方法
计算组合的常用方法：先考虑顺序进行计数，然后除以重复度
常用方法：隔板法，反逻辑解法
1.思考题——药品调剂
现假设要将颗粒状的药品调剂成一种新药，药品有A,B,C三种，新药调剂规则如下：
从A.B.C这3种药品中，共取出100粒进行调剂
调剂时，A,B,C这3种药品每种至少有1粒
不考虑药品调剂的顺序
同种药品每粒都相同
解题关键：3种药品不需要排序，以固定顺序进行解答，使用隔板法
C（2.99），100粒药种一共有99个空位置，使用两个隔板
2.思考题——至少有一端是王牌
现在有5张扑克牌，其中王牌有2张2，J,Q,K各有1张，将这5张牌排成一排，左端或者右端至少有一端是王牌
解题思路一：（容斥原理）
关键：“至少有一端是王牌”，和“不区分大小王牌”，
（1）左端是王牌，2*p（4，4）=2*4！=48
（2）右端是王牌，2*p（4，4）=2*4！=48
（3）两端都是王牌，现将王牌都置于两端，王牌有两种排法，剩余牌有三种排法，2！*3！=12
（4）得出答案：(48+48-12)/2=42
解题思路二：（逻辑解法）
“至少有一段是王牌”也就是“两端都不是王牌”的否定，从“所有的排法”减去“两端都不是王牌的排法”得出答案
所有排法：5*4*3*2*1/2
两端都不是王牌：（A（2，3）*3*2*1）/2
递归——自己定义自己
GNU的缩写：GNU is Not UNIX的缩写
1.汉诺塔问题
比如：3层汉诺塔的解法
从中可以悟出点规律：
（x为起始棒，y为中转棒，z为目标棒）
当n=1时，直接起始棒移动到目标棒
当n>0时，首先，将n-1个圆盘从x柱，经由z柱中转，移到y柱（解出n-1层汉诺塔）。
然后，将1个圆盘从x柱移到z柱。
最后，将n-1个圆盘从y柱，经过x柱中转，一道z柱（解出n-1层汉诺塔）。
#include<bits/stdc++.h>
using namespace std;
void solve(int n,char x,char y,char z)
{
if(n==1){
cout<<x<<"->"<<z<<endl;
}else{
solve(n-1,x,z,y);
cout<<x<<"->"<<z<<endl;
solve(n-1,y,x,z);
}
}
int main()
{
//x为起始棒，y为中转棒，z为目标棒
solve(3,'x','y','z');
return 0;
} 2.阶乘与斐波那契数列
斐波那契问题有：兔子繁殖
经典的递推问题：摆砖头，创作旋律
3.帕斯卡三角形（杨辉三角）
主要掌握下杨辉三角的一维打法：
#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int shu[maxn];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
for(int j=i;j>=0;j--){//此处使用滚动数组，和01背包很像，必须从后往前打
if(j==0||j==i){
shu[j]=1;
}else{
shu[j]+=shu[j-1];
}
cout<<shu[j]<<" ";
}
cout<<endl;
}
return 0;
} 从帕斯卡三角形我们还可以得出一个C(k,n)=C(k-1,n-1)+C(k,n-1);
谢尔平斯基三角形——用颜色区分帕斯卡三角形中的奇数和偶数
指数爆炸——如何解决复杂问题
1.思考：一张1mm的纸，通过对折39次可以超过地月距离，可以看出指数爆炸的威力
2.利用这个特性，我们便可以将指数爆炸用在正途上，那就是使用个二分查找法
3.可以使用对数来求一个数的位数
log10(i)+1
不可解问题——不可解的数，无法编写的程序
1.反证法（因为最后可以推出荒谬的答案，所以有时候也叫归谬法）
2.可数：元素可按一定规律既无“遗漏”也无“重复”地数出来
3.不可解问题.