สมมติว่าเรามีค่า k และ n พิจารณาการเรียงสับเปลี่ยนสุ่ม p1, p2, ..., pn ของจำนวน tự nhiên 1 ถึง n คำนวณค่า F = (X2+...+Xn-1)^k โดย Xi เป็นตัวแปรสุ่มตัวชี้วัด (Indicator Random Variable) เป็น 1 เมื่อ pi-1 < pi > pi+1 หรือ pi-1 > pi < pi+1 มิฉะนั้นเป็น 0 ต้องหาค่าคาดหวังของ F
ตัวอย่าง k = 1, n = 1000 ผลลัพธ์ = 1996/3
ขั้นตอนการแก้ปัญหา
- กำหนดฟังก์ชัน exp_factor(n, k) คืนค่า (ตัวเศษ, ตัวส่วน) ตามสูตรสำหรับ k = 1..5
- จากฟังก์ชันหลัก: M = n-2, p = 2/3, q = 1-p
- (num, den) := exp_factor(n, k)
- g := gcd(num, den)
- คืนค่าเศษส่วน (num/g)/(den/g)
ตัวอย่างโค้ด
from math import gcd
def exp_factor(n, k):
if k == 1:
return (2*(n-2), 3)
elif k == 2:
return (40*n**2 - 144*n + 131, 90)
elif k == 3:
return (280*n**3 - 1344*n**2 + 2063*n - 1038, 945)
elif k == 4:
return (2800*n**4 - 15680*n**3 + 28844*n**2 - 19288*n + 4263, 14175)
elif k == 5:
return (12320*n**5 - 73920*n**4 + 130328*n**3 - 29568*n**2 - 64150*n - 5124, 93555)
return 1.0
def solve(k, n):
M = n-2
p = 2.0/3
q = 1 - p
num, den = exp_factor(n, k)
g = gcd(num, den)
return str(int(num/g)) + '/' + str(int(den/g))
k = 1
n = 1000
print(solve(k, n))
อินพุต
1, 1000
เอาต์พุต
1996/3
