[已解决]大佬帮忙优化代码，我的代码运算量太大了

爱意随风起9306

题目
某电影院的电影票出售方式很特别，它们只准备了两种电影票。
A 类票——免费球票
B 类票——双倍价钱球票。
购买时由工作人员通过掷硬币决定，投到正面的买 A 类票， 反面的买 B 类票。由于是市场经济，主办方不可能倒贴钱，所以他们总是准备了同样多的 A 类票和 B 类票。

你和你的朋友十分幸运的排到了某场精彩电影的最后两个位置。

这时工作人员开始通过硬币售票。不过更为幸运的是当工作人员到你们面前时他发现已无需再掷硬币了，因为剩下的这两张票全是免费票。

你和你的朋友在欣喜之余，想计算一下排在队尾的两个人同时拿到一种票的概率是多少(包括同时拿 A 类票或 B 类票)

假设工作人员准备了 2N张电影票，其中 N 张 A 类票，N 张 B 类票，并且排在队伍中的人每人必须且只能买一张电影票(不管掷到的是该买 A 还是该买 B)。


输入
输入文件仅一行，包含整数 2N，代表 A、B 类票各 N 张。其中(0≤N≤1250) ，N 为整数。

输出
输出只包含一个数，为拿到同一种票的概率，精确到小数点后 4 位。

样例
输入：256
输出：0.9500






代码如下：

1. import random
   
2. shuffle_times =1000000
   
3. total_piao =int(input())
   
4. balls = [1]*(total_piao//2) + [2] *(total_piao//2)
   
5. for _ in range(shuffle_times):
   
6.     random.shuffle(balls)
   
7. 
   
8. same_balls = sum([1 for i in range(len(balls)-1) if balls[i] ==balls[i+1]])
   
9. probability = same_balls / (total_piao-1)
   
10. if total_piao==0:
    
11.     print("0.0000")
    
12. else:
    
13.     print("%.4f" % probability)

复制代码

最佳答案

月排行榜 / 总排行榜

wp231957

2023-3-2 15:08:40

网上的动态规划的解法，我给你转成PY代码，原理我是看不懂 啊

1. dp=[]
   
2. n=256
   
3. for i in range(n+1):
   
4.     dp.append([0])
   
5.     for j in range(n+1):
   
6.         dp[i].append(0)
   
7. dp[0][0]=1
   
8. for i in range(1,n+1):
   
9.     dp[i][0]=dp[i-1][0]*0.5
   
10.     for j in range(1,n//2+1):
    
11.         if j==n//2:
    
12.             dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j]   
    
13.         else:
    
14.             dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j]*0.5
    
15. print((dp[n-2][n//2])*2)               

复制代码

跳转到最佳答案楼层

wp231957

这个问题的答案不是128/256*（127/255） 约等于四分之一吗

wp231957

网上的动态规划的解法，我给你转成PY代码，原理我是看不懂 啊

1. dp=[]
   
2. n=256
   
3. for i in range(n+1):
   
4.     dp.append([0])
   
5.     for j in range(n+1):
   
6.         dp[i].append(0)
   
7. dp[0][0]=1
   
8. for i in range(1,n+1):
   
9.     dp[i][0]=dp[i-1][0]*0.5
   
10.     for j in range(1,n//2+1):
    
11.         if j==n//2:
    
12.             dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j]   
    
13.         else:
    
14.             dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j]*0.5
    
15. print((dp[n-2][n//2])*2)               

复制代码

wp231957

0.949985521005287