一个随机禁言引起的算法问题

起因

小小功能里面最火爆的竟然是禁言套餐，群友疯狂索要禁言套餐，玩起了赌博

问题来了，现在的时间是9点，如果老罗每当禁言解禁就去申请，问老罗在十二点之前学习的概率。

题目总结一下：

给定三个正整数a,b,c, 当禁言时间大于a时，老罗立刻去学习。b为随即禁言的范围，每次申请禁言，随机范围为[1,b]，取值为整数c为距离十二点的时间。现求老罗在十二点之前能去学习的概率。

个人思路

目测是动态规划，因为时间取值是正整数，这就自然的构成了不同的状态(不过如果取值不是整数的话，那就太难算了)。还有一个假设，每一次请求的随机数完全随机，每次请求独立，构成n重伯努利实验。根据这两个假设，写了一个递推式。

这里写错了，应该是从i+10开始到i+100，不过思路一样，debug时候改过去了。懒得改了。

study_time,top_time,rest_time = 10,100,180
# 小于等于10分钟则学习，禁言封顶100，还剩180分钟到12点。
dp = [0 for i in range(rest_time)]
dp[-10:] = [1-study_time/top_time]*10
for i in range(rest_time-10-1,-1,-1):
	if(180<i+100):
		dp[i] += (i+100-180-1)/100#超界，不学习的概率是1，加权加上去
	for j in range(i+10,min(i+101,180),1):
		dp[i] += 0.01*dp[j]
print(dp)
print("学习概率",1-dp[0])

python代码写了些，算出来结果是33.1%

智慧的群友1

宗濂61某个万能的医生用了个牛逼方法，random来模拟，并且模拟了很多次，一看就是老统计学派概率论了

import random

for raw_tl in range(180, 10, -1):
    sp = 0
    for i in range(1000000):
        tl = raw_tl
        while tl >= 0:
            ct = random.randint(1, 100)
            tl = tl-ct
            if ct<10 and tl>0:
                sp += 1
                break
    print('%s    %s:%s  %s' % (raw_tl, sp, 1000000-sp, sp/10000))

智慧的群友2

能动A某大佬直接就上数学了，概率估算，扔掉后面的余项。

算出也是29%左右

总结

群友的方法算出来都是29%左右，我那个递推算出来是33%，差距挺大，不过我找不出问题，希望朱军可以指导我一下，实在是debug不来了。

Donate