数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：求表达式结果中出现频率最高值的期望值
假设我们有M个不同的表达式，这些表达式的结果在1到N（包含1和N）的范围内。考虑x = max(f(i))，其中i从1到N，我们需要找到x的期望值。
例如，如果输入为M = 3，N = 3，则输出为2.2，因为
| 序列 | 最大频率 |
|---|---|
| 111 | 3 |
| 112 | 2 |
| 113 | 2 |
| 122 | 2 |
| 123 | 1 |
| 133 | 1 |
| 222 | 3 |
| 223 | 2 |
| 233 | 2 |
| 333 | 3 |
$$E(x) = \sum P(x) * x = P(1) + 2P(2) + 3P(3) = \frac{1}{10} + 2 * \frac{6}{10} + 3 * \frac{3}{10} = \frac{22}{10}$$
为了解决这个问题，我们将遵循以下步骤：
- combination := 一个新的映射
- 定义一个函数nCr()。它将接收n和k_in作为参数。
- k := k_in和(n - k_in)中的最小值
- 如果n < k或k < 0，则
- 返回0
- 否则，如果(n, k)存在于combination中，则
- 返回combination[n, k]
- 否则，如果k等于0，则
- 返回1
- 否则，如果n等于k，则
- 返回1
- 否则，
- a := 1
- 对于cnt从0到k - 1，执行以下操作：
- a := a * (n - cnt)
- a := floor of a/(cnt + 1)
- combination[n, cnt + 1] := a
- 返回a
- 在主方法中，执行以下操作：
- arr := 一个新的列表
- 对于k从2到M + 1，执行以下操作：
- a := 1
- s := 0
- 对于i从0到floor of M/k + 2，执行以下操作：
- 如果M < i * k，则
- 退出循环
- s := s + a * nCr(N, i) * nCr(N-1+M-i*k, M-i*k)
- a := -a
- 如果M < i * k，则
- 将s插入到arr的末尾
- total := arr的最后一个元素
- diff := 一个数组，在开头插入arr[0]，然后添加一个列表，其中包含(arr[cnt + 1] - arr[cnt])，其中cnt从0到M - 2
- output := (diff[cnt] *(cnt + 1) / total，其中cnt从0到M-1)中所有元素的总和
- 返回output
示例
让我们看看以下实现，以便更好地理解：
combination = {}
def nCr(n, k_in):
k = min(k_in, n - k_in)
if n < k or k < 0:
return 0
elif (n, k) in combination:
return combination[(n, k)]
elif k == 0:
return 1
elif n == k:
return 1
else:
a = 1
for cnt in range(k):
a *= (n - cnt)
a //= (cnt + 1)
combination[(n, cnt + 1)] = a
return a
def solve(M, N):
arr = []
for k in range(2, M + 2):
a = 1
s = 0
for i in range(M // k + 2):
if (M < i * k):
break
s += a * nCr(N, i) * nCr(N - 1 + M - i * k, M - i * k)
a *= -1
arr.append(s)
total = arr[-1]
diff = [arr[0]] + [arr[cnt + 1] - arr[cnt] for cnt in range(M - 1)]
output = sum(diff[cnt] * (cnt + 1) / total for cnt in range(M))
return output
M = 3
N = 3
print(solve(M, N))输入
3, 3
输出
1
更新于: 2021年10月11日
105 次浏览
广告