Derangement เป็นการเรียงสับเปลี่ยนของตัวเลข N โดยที่ตัวเลขไม่ปรากฏที่ตำแหน่งเดิม ตัวอย่าง ตัวอย่างหนึ่งที่เป็นไปได้ของความผิดปกติ { 1,2,3 } คือ { 2,1,3 } ไม่มีองค์ประกอบใดในเรื่องนี้ที่เดิมตำแหน่ง เป้าหมายที่นี่คือการนับความแปรปรวนที่เป็นไปได้สำหรับตัวเลข N
เราจะทำสิ่งนี้โดยใช้โซลูชันแบบเรียกซ้ำ สำหรับหมายเลขต่อไปนี้ ขององค์ประกอบ −
- N=0, ไม่มีความผิดปกติ, ส่งคืน 1
- N=1 มีเพียงตัวเลขเดียวเท่านั้น ส่งกลับ 0
- N=2 สามารถสลับตำแหน่งได้เพียงครั้งเดียว { 1,2 } → { 2,1 } คืนค่า 1
- N=3, 2 การเปลี่ยนแปลงที่เป็นไปได้ เช่น { 1,2,3 } → { 2,3,1 }, { 3,1,2 } นับ 2
- N=4, 9 การเปลี่ยนแปลงที่เป็นไปได้
- ................................
- N, (N-1)*( การเปลี่ยนแปลง (N-1) + การเปลี่ยนแปลง (N-2) )
สำหรับองค์ประกอบทั้งหมดในอาร์เรย์
-
องค์ประกอบที่ดัชนี 0 มีตำแหน่ง n-1 ที่สามารถรับได้
-
หากองค์ประกอบใด ๆ ที่ดัชนี i ถูกวางไว้ที่ดัชนี 0 ดังนั้น arr[i] และ arr[0] จะถูกสลับ ตอนนี้มี n-2elements สำหรับการคำนวณ
-
หากองค์ประกอบที่ดัชนี i ไม่ได้วางไว้ที่ดัชนี 0 ดังนั้นสำหรับองค์ประกอบ n-1 จะมีตัวเลือก n-2 อยู่
แผนภาพ
อินพุต
Arr[] = { 1, 2 } ผลลัพธ์
No. of derangements : 1
คำอธิบาย − ตำแหน่ง 1 และ 2 คือดัชนี 0 และ 1 เฉพาะตำแหน่งที่พวกเขาจะได้รับเท่านั้นคือการแลกเปลี่ยนตำแหน่งเดิม { 2,1 }
อินพุต
Arr[] = { 1, 2, 3 } ผลลัพธ์
No. of derangements : 2
คำอธิบาย − ตำแหน่งของ 1,2 และ 3 เป็นดัชนี 0,1,2
1 สามารถวางที่ดัชนี 1 และ 2, 2 สามารถวางที่ดัชนี 0 และ 3 และ 3 สามารถวางที่ดัชนี0 และ 1
{ 2,3,1 } และ { 3,1,2 } เป็นความผิดปกติ 2 อย่าง
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
จำนวนเต็มเก็บจำนวนตัวเลขที่มีอยู่
-
derangements ของฟังก์ชันแบบเรียกซ้ำ (int N) ใช้การนับจำนวนเป็นอินพุตและส่งคืนหมายเลข ของความผิดปกติ
-
คำสั่งส่งคืนสำหรับ N=0,1,2 กำลังจัดการกรณีพื้นฐานที่พีชคณิตคำนวณแล้วเป็น 1,0 และ 1
-
เมื่อ N>2 เรียกซ้ำไปยัง derangements() เสร็จสิ้นโดยใช้สูตร
(N-1)* ( ความผิดปกติ ( N-1) + ความผิดปกติ ( N-2) )
เมื่อการย้อนรอยเริ่มต้น การนับจะถูกคำนวณและส่งคืน
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int derangements(int N){
if (N == 0)
return 1;
if (N == 1)
return 0;
if (N == 2)
return 1;
return (N - 1) * (derangements(N - 1) + derangements(N - 2));
}
int main(){
int Numbers=5;
cout<<"Number of Derangements :"<<derangements(Numbers);
} ผลลัพธ์
Number of Derangements :44
