[已解决]Python：每日一题 317

zltzlt

今天的题目：

一个袋子里有 w 个白豆子，r 个红豆子。

第一步：随机摸一个豆子，摸到白豆子直接吃，摸到红豆子，放回去。
第二步：随机再摸一豆子，不管是红是白，都吃。

然后重复第一步和第二步，求最后一个豆子是白豆子的概率。

示例 1：

输入：w = 1，r = 1
输出：0.25
解释：第一步结束后，剩下 1 个白豆子，1 个红豆子的概率为 0.5，剩下 0 个白豆子，1 个红豆子的概率为 0.5，第二步结束后剩下 1 个白豆子，0 个红豆子的概率为 0.25，剩下 0 个白豆子，1 个红豆子的概率为 0.75。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

塔利班

2020-1-28 15:43:14

1. def f317(w,r):
   
2.     back=dict()
   
3.     def dp(w,r):
   
4.         if (w,r) in back:
   
5.             return back[(w,r)]
   
6.         if w<=0:
   
7.             return 0
   
8.         elif not r:
   
9.             return 1
   
10.         else:
    
11.             s=w+r
    
12.             p=w/s
    
13.             back[(w,r)]=(1-p)*(dp(w,r-1)*(1-p)+dp(w-1,r)*p)+p*(dp(w-1,r-1)*r/(s-1)+dp(w-2,r)*(w-1)/(s-1))
    
14.             return back[(w,r)]      
    
15.     return dp(w,r)

复制代码

概率头大怕写错了，先试试

跳转到最佳答案楼层

塔利班

1. def f317(w,r):
   
2.     back=dict()
   
3.     def dp(w,r):
   
4.         if (w,r) in back:
   
5.             return back[(w,r)]
   
6.         if w<=0:
   
7.             return 0
   
8.         elif not r:
   
9.             return 1
   
10.         else:
    
11.             s=w+r
    
12.             p=w/s
    
13.             back[(w,r)]=(1-p)*(dp(w,r-1)*(1-p)+dp(w-1,r)*p)+p*(dp(w-1,r-1)*r/(s-1)+dp(w-2,r)*(w-1)/(s-1))
    
14.             return back[(w,r)]      
    
15.     return dp(w,r)

复制代码

概率头大怕写错了，先试试

阴阳神万物主

我寻思着，用模拟的办法，十有八九要超时。

546623863

刚开始看的时候有点懵

ouyunfu

def P(w,r):
    def D(w,r):
        if w<=0:
            return 0
        elif r<=0:
            return 1
        else:
            return D(w-2,r)*(w/(w+r))*((w-1)/(w-1+r))+\
                   D(w-1,r-1)*(w/(w+r))*(r/(w-1+r))+\
                   D(w-1,r)*(r/(w+r))*(w/(w+r))+\
                   D(w,r-1)*(r/(w+r))*(r/(w+r))
                  #Case 1  first white second white
                  #Case 2  first white second red
                  #Case 3  first red second white
                  #Case 4  first red second red     
    return D(w,r)
print(P(1,1))

TJBEST

版主：这个题计算是浮点数，不同的算法结果可能有一点点差别，希望您能用软判决 比如 0.199999992和  0.199999993之类的是有可能出现的

1. def fun317(w,r):
   
2.     def inner(w,r):
   
3.         if (w,r) in dictionary:
   
4.             return dictionary[(w,r)]
   
5.         else:
   
6.             if w > 1 and r > 0:
   
7.                 res = 0
   
8.                 res += (w/(w+r))*((w-1)/(w+r-1))*inner(w-2,r)
   
9.                 res += (w/(w+r))*(r/(w+r-1))*inner(w-1,r-1)
   
10.                 res += (r/(w+r))*(w/(w+r))*inner(w-1,r)
    
11.                 res += (r/(w+r))*(r/(w+r))*inner(w,r-1)
    
12.                 dictionary[(w,r)] = res
    
13.             elif w==0 and r > 0:
    
14.                 dictionary[(w,r)] = 0
    
15.             elif w==1 and r > 0:
    
16.                 dictionary[(w,r)] = (1/(1+r))**2
    
17.             else:
    
18.                 dictionary[(w,r)] = 1
    
19.             return dictionary[(w,r)]
    
20.     dictionary = dict()
    
21.     return inner(w,r)

复制代码

zltzlt

TJBEST 发表于 2020-1-28 21:38
版主：这个题计算是浮点数，不同的算法结果可能有一点点差别，希望您能用软判决 比如 0.199999992和  0.199 ...

收到

TJBEST

我又精简了一下，您看看 变慢了还是变快了

1. def fun317(w,r):
   
2.     def inner(w,r):
   
3.         if (w,r) in dictionary:
   
4.             return dictionary[(w,r)]
   
5.         else:
   
6.             if w > 1 and r > 0:
   
7.                 p = w/(w+r)
   
8.                 q = (w-1)/(w+r-1)
   
9.                 p_b = 1 - p
   
10.                 q_b = 1 - q
    
11.                 res = p*q*inner(w-2,r) + p*q_b*inner(w-1,r-1) + \
    
12.                       p_b*p*inner(w-1,r)+p_b*p_b*inner(w,r-1)
    
13.                 dictionary[(w,r)] = res
    
14.             elif r > 0:
    
15.                 dictionary[(w,r)] = (w/(1+r))**2
    
16.             else:
    
17.                 dictionary[(w,r)] = 1
    
18.             return dictionary[(w,r)]
    
19.     dictionary = dict()
    
20.     return inner(w,r)

复制代码

fan1993423

你们真的是自己做的吗？好厉害的感觉

TJBEST

fan1993423 发表于 2020-1-28 22:21
你们真的是自己做的吗？好厉害的感觉

不难啊，就是简单的全概率公式

Vmtayvj

数学总被当的我，看了就头疼!

阴阳神万物主

我感觉我的数学退步了，示例的输出为什么不是1/3呢？
(格式为：w,r)
第一步结束：0,1;1,1
第二步结束：0,1;1,0
只剩最后一颗豆子的事件总数为3，分别是：0,1;0,1;1,0

zltzlt

阴阳神万物主 发表于 2020-1-29 07:17
我感觉我的数学退步了，示例的输出为什么不是1/3呢？
(格式为：w,r)
第一步结束：0,1;1,1

（白 红）

第一步结束：    1 1               0 1
第二步结束：1 0 或 0 1         0 1

Croper

1. def func317(w,r):
   
2.     map={}
   
3.     def dp(w,r):
   
4.         if r==0:
   
5.             return 1
   
6.         if not (w,r) in map:
   
7.             t=w+r
   
8.             ret=dp(w,r-1)*r*r/(t**2) #红红
   
9.             if w>1:
   
10.                 ret+=dp(w-1,r)*r*w/(t**2) #红白
    
11.                 ret+=dp(w-1,r-1)*w*r/(t*(t-1)) #白红
    
12.                 if w>2:
    
13.                     ret+=dp(w-2,r)*w*w/(t*(t-1)) #白白
    
14.             map[(w,r)]=ret
    
15.         return map[(w,r)]
    
16.     return dp(w,r)

复制代码

TJBEST

我这个是不是不是 100ms 因为 110ms的朋友最佳答案

zltzlt

TJBEST 发表于 2020-1-29 17:41
我这个是不是不是 100ms 因为 110ms的朋友最佳答案

由于塔利班先回答，而且效率不错，所以最佳答案给他了