โจทย์
เพื่อน 5 คนกองหมวกของตัวเองรวมกันไว้ แล้วต่างคนต่างสุ่มหยิบกลับมาคนละใบ จะมีกี่วิธีที่ไม่มีใครได้หมวกของตัวเองคืนเลย การจัดเรียงของ n ชิ้นที่ไม่มีชิ้นใดอยู่ในตำแหน่งเดิมเรียกว่า derangement จำนวนวิธีเริ่มต้นด้วย 1, 0, 1, 2, 9, 44 และเป็นไปตามสูตร D(n) = (n − 1) × (D(n − 1) + D(n − 2))
จงเขียนฟังก์ชัน derangements(n)
อินพุต
n: จำนวนสิ่งของ
เอาต์พุต
คืนค่าจำนวน derangement ของสิ่งของ n ชิ้น โดย D(0) เท่ากับ 1 (การจัดเรียงที่ว่างเปล่าไม่มีชิ้นใดค้างอยู่ที่เดิม) และ D(1) เท่ากับ 0
เงื่อนไข
0 ≤ n ≤ 20
ตัวอย่าง
อินพุต:
n = 3
ผลลัพธ์ที่คาดหวัง:
expected = 2
อินพุต:
long long n = 3;
ผลลัพธ์ที่คาดหวัง:
long long expected = 2;
อินพุต:
long n = 3;
ผลลัพธ์ที่คาดหวัง:
long expected = 2;
คำอธิบาย
สำหรับของ A, B, C มีเพียง BCA และ CAB ที่ทุกชิ้นย้ายที่ คำตอบจึงเป็น 2
อินพุต:
n = 4
ผลลัพธ์ที่คาดหวัง:
expected = 9
อินพุต:
long long n = 4;
ผลลัพธ์ที่คาดหวัง:
long long expected = 9;
อินพุต:
long n = 4;
ผลลัพธ์ที่คาดหวัง:
long expected = 9;
คำอธิบาย
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
เริ่มจาก D(0) = 1 และ D(1) = 0
คำใบ้ 2
ค่าถัดไปแต่ละค่าใช้สองค่าก่อนหน้าและค่า n ปัจจุบัน
คำใบ้ 3
ในแต่ละขณะต้องใช้เพียงสองค่าล่าสุด
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน