算法入门实战：从奶茶杯套问题，彻底搞懂经典赠券收集问题与动态规划实现

从奶茶店集杯套搞懂经典概率题算法实现 | 小白也能看懂的赠券收集问题全解导语你有没有过这样的经历网红奶茶店出了季节限定杯套集齐4款就能换一杯免费奶茶你兴冲冲地连续买了一周结果要么重复款堆了一堆要么永远差最后一款死活集不到最后算下来花的钱早就够买好几杯奶茶了。你有没有想过到底买多少杯奶茶才能稳稳妥妥集齐一套杯套有没有办法精准算出集齐的概率商家的集卡活动到底藏着什么套路读完这篇文章你将收获搞懂经典的「赠券收集问题」再也不会被集卡/盲盒/杯套活动套路用最基础的概率知识算出集齐杯套需要的平均购买量掌握用动态规划解决复杂概率问题的思路附完整可运行的Python代码看透商家集卡活动的底层逻辑理性消费不踩坑一、先把规则说清楚我们到底在算什么先把奶茶店的活动规则还原成严谨的数学场景避免后面算糊涂本次活动一共有n款不同的杯套编号1~n每买一杯奶茶随机赠送1款杯套每款杯套的获取概率完全相等每次赠送相互独立不受之前结果的影响每集齐1套完整的n款杯套每款各1个就能兑换1杯免费奶茶兑换时回收用来兑换的n个杯套多余的杯套可以保留继续用。接下来我们就从大家最关心的3个问题入手一步步拆解。二、灵魂拷问1集齐第一套n款杯套平均要买多少杯奶茶2.1 先打破你的直觉误区很多人第一反应n款杯套那平均买n杯不就集齐了大错特错我们拿最常见的n4款杯套举例子买4杯奶茶刚好集齐4款不同杯套的概率只有4!/4^4 24/256 ≈ 9.375%——也就是说你买4杯只有不到10%的概率能直接集齐一套剩下90%的情况都会出现重复款。那到底平均要喝多少杯这里就要用到经典的赠券收集问题Coupon Collector Problem我们用大白话给你讲得明明白白。2.2 把集齐的过程拆成一步一步算我们把「从0到集齐n款杯套」的过程拆成n个阶段每个阶段的目标只有一个收集到1款新的杯套。我们还是用n4春、夏、秋、冬4款杯套来举例一步步算阶段1手里0款杯套→收集到第1款你买第一杯奶茶不管拿到哪一款都是新的所以这个阶段只需要买1杯毫无悬念。阶段2手里1款杯套→收集到第2款现在你已经有1款了再买一杯奶茶拿到「新款杯套」的概率是多少4款里有3款你没拿到所以概率是3/4。这里要给大家补一个超简单的概率常识如果一件事每次成功的概率是p那么平均需要1/p次才能成功这就是几何分布的核心结论小白不用记名字记住结论就行。举个例子抛硬币正面朝上的概率是1/2那平均抛2次就能出一次正面完美符合这个结论。所以这个阶段你平均需要买4/3 ≈ 1.33杯才能拿到第2款新杯套。阶段3手里2款杯套→收集到第3款现在你已经有2款了再买一杯出新款的概率是2/4 1/2所以平均需要买4/2 2杯才能拿到第3款。阶段4手里3款杯套→收集到第4款最后一款最坑的阶段来了你已经有3款就差最后1款再买一杯出新款的概率只有1/4所以平均需要买4/1 4杯才能拿到最后一款现在把4个阶段的杯数加起来1 4/3 2 4 25/3 ≈ 8.33杯哦原来4款杯套理论上平均要买8-9杯才能集齐一套是不是和你平时的经历一模一样永远差最后一款死活集不到因为最后一步的平均成本是前面所有阶段加起来的一半2.3 推广到n款杯套的通用公式刚才的例子我们可以直接推广到任意n款杯套的情况从0到1款平均需要n/n 1杯从1到2款平均需要n/(n-1)杯从2到3款平均需要n/(n-2)杯…从n-1到n款平均需要n/1杯把所有阶段加起来集齐n款杯套的平均购买杯数就是E(n)n⋅(11213⋯1n) E(n) n \cdot \left(1 \frac{1}{2} \frac{1}{3} \dots \frac{1}{n}\right)E(n)n⋅(121​31​⋯n1​)这个公式里的1 1/2 1/3 ... 1/n在数学里叫做第n个调和数记作HnH_nHn​所以公式可以简化成E(n)n⋅Hn E(n) n \cdot H_nE(n)n⋅Hn​2.4 给你几个直观的数字感受商家的套路n5款杯套平均需要5*(11/21/31/41/5) ≈ 11.42杯n10款杯套平均需要10*H_10 ≈ 29.29杯n100款杯套平均需要100*H_100 ≈ 518.74杯看到了吗杯套款数越多你需要买的奶茶数量呈指数级上涨商家就是利用了大家的收集欲和对概率的不敏感让你不知不觉为了一杯免费奶茶花了十几倍的钱。三、灵魂拷问2已经有k款了还要买多少杯才能集齐很多人看到这里会问我已经集到了k款就差(n-k)款了能不能帮我算算平均还要买多少杯其实这个问题我们刚才的拆解已经给出答案了你已经有了k款杯套接下来的目标就是从k款到k1款、k1款到k2款……一直到n款把这些阶段的平均杯数加起来就行。3.1 通用公式已经收集到k款杯套后集齐完整一套的平均额外购买杯数为E(k,n)n⋅(1n−k1n−k−1⋯11) E(k,n) n \cdot \left( \frac{1}{n-k} \frac{1}{n-k-1} \dots \frac{1}{1} \right)E(k,n)n⋅(n−k1​n−k−11​⋯11​)还是用n4的例子给大家验证已经有2款了还差2款平均需要4*(1/2 1/1) 6杯已经有3款了只差最后1款平均需要4*(1/1) 4杯是不是很真实很多人差最后一款的时候买了四五杯都抽不到这不是你运气差是数学上平均就要买4杯互动小提问你现在集杯套/集卡已经有了几款还差几款评论区打出来我帮你算平均还要买多少四、灵魂拷问3n4买了6杯奶茶刚好能换1杯免费奶茶的概率是多少这个问题是很多人最关心的我已经买了固定数量的奶茶到底有多大概率能凑齐一套4.1 先明确什么叫「刚好可以兑换一杯免费奶茶」首先兑换1套杯套需要4个每款1个买了6杯总共有6个杯套。「刚好能兑换1杯」的核心条件是6个杯套里4款杯套每款至少有1个。因为6个杯套最多只能凑1套凑2套需要8个所以不用额外限制4.2 一步步算概率概率的核心公式是符合条件的情况数 ÷ 总可能情况数第一步算总可能情况数每买一杯奶茶有4种杯套可能买6杯总可能数就是4^6 4096种。第二步算符合条件的情况数我们要算的是6个杯套4款每款至少1个有多少种可能这里用一个超简单的思路先给每款杯套分1个用掉4个杯套还剩2个杯套这2个可以随便分给4款杯套。这时候剩下的2个杯套只有两种分法情况12个杯套都分给同一款也就是有1款杯套有3个剩下3款各1个。选哪一款多2个有C(4,1)4种选择这种情况的排列数6个杯套里有3个是同一款剩下3个各不同排列数是6!/3! 120总贡献4 * 120 480种情况22个杯套分给不同的2款每款1个也就是有2款杯套各有2个剩下2款各1个。选哪两款各多1个有C(4,2)6种选择这种情况的排列数6个杯套里有2款各2个剩下2款各1个排列数是6!/(2!*2!) 180总贡献6 * 180 1080种把两种情况加起来符合条件的总情况数是480 1080 1560种。第三步算最终概率P符合条件的情况数总可能情况数15604096195512≈38.09% P \frac{符合条件的情况数}{总可能情况数} \frac{1560}{4096} \frac{195}{512} ≈ 38.09\%P总可能情况数符合条件的情况数​40961560​512195​≈38.09%也就是说你买了6杯奶茶只有不到4成的概率能凑齐一套换免费奶茶剩下6成的概率要么缺款要么重复太多根本换不了五、进阶挑战规则变复杂了用代码搞定所有情况刚才我们算的都是「每款杯套概率均等」的理想情况但现实里商家的套路可不止这么简单隐藏款杯套的概率特别低普通款概率高除了换免费奶茶单款杯套攒够s个还能换小礼品甚至还有「稀有款只能通过活动获取买奶茶拿不到」的骚操作这时候纯数学公式就很难快速算出结果了我们可以用动态规划DP用代码来搞定所有复杂规则5.1 升级版题目算法题我们把原题升级成更贴合现实的场景也是一道标准的算法题某网红奶茶店推出升级版杯套收集活动规则如下共有n款杯套编号1~n。每买一杯奶茶随机获得一款杯套第i款的获取概率为p_i保证所有p_i加起来等于1每次获取相互独立。每集齐一套每款各1个可兑换1杯免费奶茶兑换时回收n个杯套多余杯套可保留。额外规则若某款杯套的持有量达到s个可兑换1个小礼品兑换后杯套数量不变小礼品可重复兑换。要求计算买m杯奶茶后期望能兑换的免费奶茶数量。计算买m杯奶茶后恰好兑换t杯免费奶茶、g个小礼品的概率。5.2 动态规划思路大白话版动态规划的核心就是一步一步记录每一个状态的概率最后汇总得到我们想要的结果。我们不用复杂的多维数组用最直观的「字典」来存状态小白也能看懂状态定义我们用一个字典dp其中key是一个元组(a1, a2, ..., an)表示当前每款杯套的持有数量value是达到这个状态的概率。初始状态买0杯奶茶的时候所有杯套数量都是0概率是100%也就是dp {(0,)*n: 1.0}。状态转移每买一杯奶茶我们就更新一次状态遍历上一轮的所有状态遍历每一款杯套给这款杯套的数量1生成新的状态把新状态的概率加上「上一轮状态的概率 × 这款杯套的获取概率」结果统计买完m杯奶茶后遍历所有状态根据杯套数量算出每个状态能兑换的免费奶茶数和小礼品数汇总概率和期望。5.3 完整可运行Python代码我给大家写了完整的代码加了超详细的注释小白复制粘贴就能直接运行还能自己修改参数算任何你想要的场景defcalculate_cup_set_probability(n,m,s,p,target_tNone,target_gNone): 计算奶茶杯套收集问题的概率和期望 :param n: 杯套总款数 :param m: 购买奶茶的总杯数 :param s: 单款杯套兑换小礼品的阈值 :param p: 每款杯套的获取概率列表类型长度为n :param target_t: 目标免费奶茶兑换数可选 :param target_g: 目标小礼品兑换数可选 :return: 免费奶茶的期望数量目标(t,g)的概率 # 初始化DPkey是杯套数量元组value是对应概率dp{(0,)*n:1.0}# 模拟买m杯奶茶的过程每一杯更新一次状态for_inrange(m):new_dp{}# 遍历上一轮的所有状态forstate,probindp.items():# 遍历每一款杯套模拟买一杯拿到该款的情况foriinrange(n):# 给第i款杯套的数量1生成新状态new_statelist(state)new_state[i]1new_statetuple(new_state)# 累加概率new_dp[new_state]new_dp.get(new_state,0.0)prob*p[i]# 更新dp为当前轮的状态dpnew_dp# 统计结果expect_free0.0# 免费奶茶的期望数量target_prob0.0# 目标(t,g)的概率forstate,probindp.items():# 计算当前状态能兑换的免费奶茶数每款至少1个才能换1套最多换min(state)套free_nummin(state)# 累加期望expect_freefree_num*prob# 如果指定了目标计算对应概率iftarget_tisnotNoneandtarget_gisnotNone:# 计算当前状态能兑换的小礼品数每s个换1个可重复兑换gift_numsum(x//sforxinstate)# 如果符合目标累加概率iffree_numtarget_tandgift_numtarget_g:target_probprobreturnexpect_free,target_prob# ------------------- 测试用例原题第三问 -------------------# 原题参数n4款杯套买m6杯s随便填不影响免费奶茶计算每款概率0.25if__name____main__:# 基础参数设置n4m6s2p[0.25,0.25,0.25,0.25]target_t1# 目标兑换1杯免费奶茶target_g0# 目标兑换0个小礼品随便填不影响免费奶茶概率# 计算结果expect_free,target_probcalculate_cup_set_probability(n,m,s,p,target_t,target_g)# 输出结果print(f买{m}杯奶茶免费奶茶的期望兑换数{expect_free:.4f})print(f恰好兑换{target_t}杯免费奶茶的概率{target_prob:.4f})5.4 代码运行结果运行上面的代码你会得到买6杯奶茶免费奶茶的期望兑换数0.3809 恰好兑换1杯免费奶茶的概率0.3809和我们之前手动算的结果完全一致你还可以自己修改参数比如把某款杯套的概率改成0.1其他改成0.3模拟隐藏款的情况把n改成10m改成30看看买30杯能集齐一套的概率有多少把s改成3看看能兑换多少小礼品六、写在最后数学是你的反套路神器其实今天讲的「赠券收集问题」不止适用于奶茶杯套生活里到处都是它的影子盲盒抽隐藏款游戏里抽卡集角色方便面里集水浒卡电商平台集卡分红包所有的集卡活动底层逻辑都是一样的利用你的收集欲和损失厌恶心理让你为了一个“免费”的奖励付出远超奖励本身的成本。而数学就是帮你看透这些套路的最好工具。当你能精准算出集齐一套需要的平均成本能算出你买了这些东西之后的中奖概率你就不会再为了虚无缥缈的“集齐”上头就能理性消费把钱花在真正值得的地方。互动时间你有没有过为了集卡/集杯套/抽盲盒上头的经历最后花了多少钱你想算什么集卡场景的概率比如n10款隐藏款概率0.05买50杯能集齐的概率有没有其他想了解的概率问题欢迎在评论区留言我会一一回复帮你算得明明白白