교란은 원래 위치에 숫자가 나타나지 않도록 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-2개의 요소가 계산을 위해 존재합니다.
-
인덱스 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개의 교란입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 Num은 존재하는 숫자의 개수를 저장합니다.
-
재귀 함수 derangements(int N)는 숫자의 개수를 입력으로 받아 숫자를 반환합니다. .
-
N=0,1,2에 대한 return 문은 순열이 이미 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