编程思维任务之(30) AMC一道概率题的编程解析

16个车位排成一行，先到的12辆车随机选空位停车入位。你和朋友后到，想找连在一块的空车位，你和朋友的车想紧挨着停。你和朋友找到两个紧挨着的空车位概率是？

640.png

示意图解释

为图片宽幅尺寸所限，不妨考虑12辆车之间没有空位，或最多留出一个空位，总共会有多少种排列？

先假设每辆车之间都有一个空位。12辆车如上图排开，每个车之间空出一个车位。这样算共有12+13=25个空位。那么13个空车位保证没有两个相连的。13个空位留给后面来的人，你和你的朋友就一定不能挨在一起停。

约束条件来了——总共只有16个车位。13个空车位只保留4个空车位，问题就简化为13个位置中任意选4个，共有多少种不同的结果。

到这里就是标准的combination问题 P(lot) = C(4,13),剩下只有一个问题，P(lot)是保证不会有两个空车位相连的停放方式的总数，那么P(total) = C(4,16)则是所有可能停放方式的总数(包括挨在一起，和不挨在一起两种情景）

挨在一起，和不挨在一起两种情景是互斥的，两种情况构成了全部停放方式，容易得到存在至少有两个空车位是紧挨的概率是：

**1 - P(lot) / P(total) **

结果是** C(4,13) / C(4,16) **** = 17/28**

math solve 告一段落 >>> 👇

如何用枚举法编码解决该问题的？

from fractions import Fraction
start = '0b1'+'0'*4 + '1'*12
end = '0b1'+'1'*12 + '0'*4

s,t = int(start,2),int(end,2)
num,total = 0,0
for n in range(s,t+1):
    if bin(n)[3:].count('0') == 4:
        total += 1
        num += (bin(n)[3:].count('00') != 0)
        
print(num,total,Fraction(num,total))
1105 1820 17/28

参考AMC问题