Giả sử chúng ta có M biểu thức khác nhau và câu trả lời của các biểu thức này nằm trong phạm vi từ 1 đến N (bao gồm cả hai) Vì vậy, xét x =max (f (i)) với mỗi i trong phạm vi 1 đến N, chúng ta phải tìm giá trị mong đợi trong tổng số x.
Vì vậy, nếu đầu vào là M =3, N =3, thì đầu ra sẽ là 2,2, bởi vì
| Sequence | Tần suất tối đa |
|---|---|
| 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} $$
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- kết hợp:=một bản đồ mới
- Định nghĩa một hàm nCr (). Điều này sẽ mất n, k_in
- k:=tối thiểu của k_in và (n - k_in)
- nếu n
- trả về 0
- kết hợp trả về [n, k]
- trả lại 1
- trả lại 1
- a:=1
- đối với cnt trong phạm vi từ 0 đến k - 1, thực hiện
- a:=a * (n - cnt)
- a:=tầng của a / (cnt + 1)
- kết hợp [n, cnt + 1]:=a
- trả về một
- a:=1
- s:=0
- đối với tôi trong phạm vi từ 0 đến tầng M / k + 2, hãy thực hiện
- nếu M
- ra khỏi vòng lặp
- nếu M
- s:=s + a * nCr (N, i) * nCr (N-1 + M-i * k, M-i * k)
- a:=-a
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)) Đầu vào
3, 3
Đầu ra
1