資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告