โจทย์
สัมประสิทธิ์ทวินาม C(n, k) อ่านว่า "n เลือก k" คือจำนวนวิธีเลือกของ k ชิ้นจากของที่แตกต่างกัน n ชิ้น โดยไม่สนใจลำดับ สูตร n! / (k! (n − k)!) จะล้นอย่างรวดเร็วถ้าคำนวณแฟกทอเรียลก่อน ดังนั้นให้สร้างคำตอบทีละขั้น หรือใช้กฎของปาสคาล C(n, k) = C(n − 1, k − 1) + C(n − 1, k)
จงเขียนฟังก์ชัน binomial_coefficient(n, k)
อินพุต
n: จำนวนของทั้งหมด
k: จำนวนที่ต้องเลือก
เอาต์พุต
คืนค่า C(n, k) ถ้า k > n จะไม่มีวิธีเลือกเลย ให้คืนค่า 0
เงื่อนไข
0 ≤ n ≤ 66
0 ≤ k ≤ 100
ตัวอย่าง
อินพุต:
n = 5
k = 2
ผลลัพธ์ที่คาดหวัง:
expected = 10
อินพุต:
long long n = 5;
long long k = 2;
ผลลัพธ์ที่คาดหวัง:
long long expected = 10;
อินพุต:
long n = 5;
long k = 2;
ผลลัพธ์ที่คาดหวัง:
long expected = 10;
คำอธิบาย
จำนวนวิธีเลือกของ 2 ชิ้นจาก 5 ชิ้นคือ 5 × 4 / 2 = 10
อินพุต:
n = 6
k = 0
ผลลัพธ์ที่คาดหวัง:
expected = 1
อินพุต:
long long n = 6;
long long k = 0;
ผลลัพธ์ที่คาดหวัง:
long long expected = 1;
อินพุต:
long n = 6;
long k = 0;
ผลลัพธ์ที่คาดหวัง:
long expected = 1;
คำอธิบาย
การไม่เลือกอะไรเลยทำได้เพียงวิธีเดียว คำตอบจึงเป็น 1
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
แฟกทอเรียลของจำนวนที่มากกว่า 20 เก็บใน 64 บิตไม่ได้ จึงควรหลีกเลี่ยง
คำใบ้ 2
แถวหนึ่งของสามเหลี่ยมปาสคาลอัปเดตในที่เดิมได้โดยไล่จากขวาไปซ้าย
คำใบ้ 3
C(n, k) เท่ากับ C(n, n − k) และเท่ากับ 0 เมื่อ k > n
ความซับซ้อนที่คาดหวัง
เวลา O(n · k), หน่วยความจำเพิ่ม O(k)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน