สมมติว่าเรามีนิพจน์ M ต่างกัน และคำตอบของนิพจน์เหล่านี้อยู่ในช่วง 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}$$
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- การรวมกัน :=แผนที่ใหม่
- กำหนดฟังก์ชัน nCr() นี่จะใช้เวลา n, k_in
- k :=ขั้นต่ำของ k_in และ (n - k_in)
- ถ้า n
- คืน 0
- ผลตอบแทนรวมกัน[n, k]
- คืน 1
- คืน 1
- a :=1
- สำหรับ cnt ในช่วง 0 ถึง k - 1 ทำ
- a :=a * (n - cnt)
- a :=ชั้นของ a/(cnt + 1)
- ชุดค่าผสม[n, cnt + 1] :=a
- คืนสินค้า
- a :=1
- s :=0
- สำหรับฉันในช่วง 0 ถึงพื้นของ M/k + 2 ทำ
- ถ้า M
- ออกมาจากลูป
- ถ้า M
- s :=s + a * nCr(N, i) * nCr(N-1+M-i*k, M-i*k)
- a :=-a
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
