想了一道程序题

2018/4/20镜像同步8 回复

假定桌子上从左到右排列着n个盒子，第i个盒子里装着i颗糖。小明每次等概随机选择桌上的一个盒子并从里取一块糖，如果盒子空了就扔掉该盒子。重复拿糖的过程，直到桌上没有盒子为止。求第n号盒子最后被扔掉的概率。比如， P(n=1) = 1.0 P(n=2) = 0.75 ... 用了递归的方法并维护了各种的情况下的概率分布以简化运算，发现效率仍然堪忧。各位怎么看？

订阅后，新回复会通过你的通知中心匿名送达。

8 条回复

yibanxianshi机器人#1 · 2018/4/20

冏，递归算错了

lu1017222931机器人#2 · 2018/4/20

这还能用编程模拟呀？模拟不是得不到精确的值嘛。。这应该用数学去算吧

Nroskill机器人#3 · 2018/4/20

明显是O(1)数学题…

allvphx机器人#4 · 2018/4/21

复杂度 O(n^2 C{n-1})， Cn 表示卡特兰数列第 n 项 n = 16的时候大概 6s， n = 15 的时候不到1s。这样的行不行。

allvphx机器人#5 · 2018/4/21

考虑用n元组表示1~n-1号桶中当前剩余球状态S，然后动态规划 f(S,j) 表示前n-1个桶状态为S，第n个桶中有j个球的概率，可以发现前n-1个桶本质相同，所以考虑用集合代替序列，每次转移考虑从非空桶中取出一个，单次转移O(n)。总复杂度 O(C_{n-1} n^2)

yibanxianshi机器人#6 · 2018/4/22

好专业的感觉。我非模拟的做法是考虑计算出每个状态的到转移目标的概率，然后累加起来；其中概率用递归算出，但是因为有n!个状态，所以最后会计算很庞大。恕我愚钝，感觉思路很像。【在 allvphx 的大作中提到: 】 : 考虑用n元组表示1~n-1号桶中当前剩余球状态S，然后动态规划 f(S,j) 表示前n-1个桶状态为S，第n个桶中有j个球的概率， : 可以发现前n-1个桶本质相同，所以考虑用集合代替序列，每次转移考虑从非空桶中取出一个，单次转移O(n)。 : 总复杂度 O(C_{n-1} n^2)

yibanxianshi机器人#7 · 2018/4/22

因为难算就以为可以作为算法题，抱歉抱歉…… 【在 Nroskill 的大作中提到: 】 : 明显是O(1)数学题…

allvphx机器人#8 · 2018/4/25

【在 yibanxianshi 的大作中提到: 】 : 好专业的感觉。 : 我非模拟的做法是考虑计算出每个状态的到转移目标的概率，然后累加起来；其中概率用递归算出，但是因为有n!个状态，所以最后会计算很庞大。 : 恕我愚钝，感觉思路很像。也就是 nC(n-1) < n! 缩减状态优化暴力，依然是非多项式，没什么专业要素的。 > . <