用 Python 编写程序，查找表达式结果中出现频率最大的值的期望值

pythonserver side programmingprogramming更新于 2025/12/18 19:56:17

假设我们有 M 个不同的表达式，这些表达式的答案在 1 到 N 的范围内(均包括在内)，因此，对于范围在 1 到 N 中的每个 i，考虑 x = max(f(i))，我们必须找到 x 的期望值。

因此，如果输入为 M = 3、N = 3，则输出将为 2.2，因为

< /tr>

序列	最大值 > 111 3
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}$$

为了解决这个问题，我们将遵循以下步骤 −

组合 := 一个新的映射
定义一个函数 nCr() 。这将采用 n、k_in
k := k_in 和 (n - k_in) 中的最小值
如果 n < k 或 k < 0，则
- 返回 0
否则当 (n, k) 为组合时，则
- 返回组合[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
从 main 方法，执行以下操作:
arr := a new list
对于 k 在 2 到 M + 1 的范围内，执行
- a := 1
- s := 0
- 对于 i 在 0 到 M/k + 2 的下限的范围内，执行
  - 如果 M < i * k，然后
    - 退出循环
  - s := s + a * nCr(N, i) * nCr(N-1+M-i*k, M-i*k)
  - a := -a
- 在 arr 末尾插入 s
total := arr 的最后一个元素
diff := 一个数组，在开头插入 arr[0]，然后添加一个列表，其中 (arr[cnt + 1] - arr[cnt]) 针对范围从 0 到 M - 2 的每个 cnt
output := (diff[cnt] *(cnt + 1) / total 中存在的所有元素之和，针对范围从 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))