수학에서 오일러 수 특수 유형의 조합 번호입니다. 다음 요소가 이전 요소보다 큰 특정 숫자인 순열의 수를 정의합니다.
다음으로 표시됨,
A(n, m) 두 숫자가 m에 따라 달라지는 1에서 n으로의 순열입니다.
문제 설명: 이 문제에서는 두 개의 숫자 m과 n이 주어집니다. 그리고 오일러 수인 순열의 수를 찾아야 합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력: n =4, m =2
출력: 11
설명:
1에서 4까지의 모든 순열은 -
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2
2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1
3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1
4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
11개의 모든 순열 중에서 두 숫자 m의 차이가 있습니다.
솔루션 접근 -
순열의 수를 찾기 위해 오일러 수 공식을 사용할 것입니다.
A(n, m) =0, m> n 또는 n =0인 경우
A(n, m) =1, m =0인 경우
A(n, m) =(n-m)A(n-1, m-1) + (m+1)A(n-1, m)
우리 솔루션의 작동을 설명하는 프로그램,
예시
#include <iostream>
using namespace std;
int countEulerianNumber(int n, int m)
{
if (m >= n || n == 0)
return 0;
if (m == 0)
return 1;
return ( ( (n - m) * countEulerianNumber(n - 1, m - 1) ) + ( (m + 1) * countEulerianNumber(n - 1, m) ) );
}
int main() {
int n = 5, m = 3;
cout<<"The number of Eulerian permutations is "<<countEulerianNumber(n, m);
return 0;
} 출력 -
The number of Eulerian permutations is 26