6.1 计数的基础.md

6.1 计数的基础

乘法法则

假定一个过程可以被分解成前后两个任务，如果完成第一个任务有k种方法，在第一个任务之后的第二个任务有r种方法，那么完成这个任务的过程有k*r种方法。

$amount=[];
for ($k=1;$k<=100;$k++){
    for ($r=1;$r<=100;$r++){
        // 乘法法则
        $amount[]=$k*$r;
    }
}
print_r($amount);

求和法则

假定一个过程可以被分解成两个独立的任务，如果完成第一个任务有k种方法，第二个任务有r种方法，那么完成这个任务的过程有k+r种方法。

// 加法法则
$amount=[];
for ($k=1;$k<=100;$k++){
    $amount[]=$k;
}
for ($r=1;$r<=100;$r++){
    $amount[]=$r;
}
print_r($amount);

减法法则（两个集合的容斥原理）

如果一个任务或者可以通过k种方法执行，或者可以通过r种另一类方法执行，则这个任务的方法数就是k+r后再减去两者的共同方法。

// 减法法则
$amount=[];
for ($k=1;$k<=100;$k++){
    $amount[$k]=1;
}
for ($r=50;$r<=150;$r++){
    $amount[$r]=1;
}
print_r($amount);

除法法则

如果一个任务能由一个可以用n种方式完成的过程实现，而对于每种完成任务的方式w，在n种方法中恰好有d种与之对应，则完成这个任务的方法数为 n/d。

// 除法法则
$amount=[];
$d=10;
$result=0;
for ($n=1;$n<=100;$n++){
    if ($n % $d==0){
        $amount[$n]=$result;
        $result++;
        continue;
    }
    $amount[$n]=$result;
}

print_r($amount);

树图

其实这个很简单，就是以前说的把所有情况列出来。

比如，3位数的byte数能有多少种组合？

根据上面的图，从左到右可以得到值有：

• 000
• 001
• 010
• 011
• 100
• 101
• 110
• 111

共计8种组合方式。