这一题是10月份新加的题,网上也没啥答案,标签为dp动态规划,实际上我觉得不用动态规划也能做,毕竟python是自带了求组合数的函数,下面来看一下吧。

试题 算法训练 印章

资源限制

        时间限制:1.0s   内存限制:256.0MB

问题描述

  共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。

输入格式

  一行两个正整数n和m

输出格式

  一个实数P表示答案,保留4位小数。

样例输入

2 3

样例输出

0.7500

数据规模和约定

1≤n,m≤20

解题思路:

       
其实是很基础的概率问题,有n种印章,买了m个;其实可以转化为m个小球放入n个盒子中,每个盒子不限数量,求每个盒子至少一个球的概率,还不好求,再转化成(1-至少一个盒子为空的概率)。

        设某一盒子为空的事件为Ai,可以得出:

……

        由相容的n个事件的和的概率公式可得,至少有一个盒子为空的概率为:

         那么所有盒子都装有球的概率(集齐印章的概率)为:

python实现,代码如下:
n, m = map(int, input().split()) def quick_multi(n, m): #
快速幂,n的m次方,其实直接调用python的求幂的函数也可以,我为了是练习一下 res = 1 while m > 0: if m & 1: res *=
n n *= n m = m >> 1 return res def compose_dp(num): # 动态规划求组合数,利用C(n,m) =
C(n-1, m) + C(n-1, m-1)可以逐个求出 #
初始化的数组全为1,且会多出一行一列,作为m=1或n=1时计算使用,操作时C(n,m)就对应数组的dp_comb[n][m] dp_comb = [[1
for i in range(num + 1)] for j in range(num + 1)] #
行序号定为n,列序号定为m,从n个元素中选m个出来组合,m==n时为1 for n in range(2, num + 1): for m in
range(1, n): dp_comb[n][m] = dp_comb[n-1][m] + dp_comb[n-1][m-1] #
虽然我们建立了从C(0,0)到C(num,num)的所有组合数可能,但本题只会用到C(num,1)到C(num,num-1) return dp_comb
def probability(n, m): if n > m: # 如果买的还没种类多肯定不可能集齐 prob = 0.0 else: # 如果买的比种类多
# 计算出至少有一种印章没有集齐的概率p,用1-p即为所有印章都集齐的概率 if n == 1: prob = 1.0 else: #
先获取的动态规划的组合数数组(只需要取最后一行即可) dp_comb = compose_dp(n)[n] #print(dp_comb) p = 0 for
i in range(1, n): p += dp_comb[i] * quick_multi((1 - i / n), m) *
quick_multi(-1, i - 1) prob = 1 - p return prob res = probability(n, m)
print('%.4f' % res)
ps:应该还有直接计算每个盒子至少有一个概率的方法,但是可能我脑子不太好使觉得太麻烦,欢迎大家讨论、改进!

技术
友情链接
码工具
Toolsou
API参考文档
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信