K개의 역순 쌍으로 순열의 수를 찾기 위해 C++를 사용하여 코드를 작성하세요.

배열에서 a[i] > a[j]이고 i

Input: N = 4, K = 1
Output: 3
Explanation: Permutation of the first N numbers in total : 1234, 1243, 1324 and 2134. With 1 inversion we have 1243, 1324 and 2134.

Input : N = 3, K = 2
Output : 3
Explanation: Permutation of the first N numbers in total : 123, 132, 213, 231, 312, and 321 with 2 inversions we have 231, 312 and 321.

해결 방법

우리는 무차별 대입 방법을 사용할 수 있습니다. 먼저 첫 번째 N 숫자의 모든 순열을 찾은 다음 모든 반전이 K인지 확인합니다. 그렇다면 결과 카운터를 늘리십시오.

효율적인 방법

이 방법에는 처음 N개의 자연수 중 N자리가 있습니다. 이 숫자의 모든 순열은 다른 곳에서 계산되며, 여기에서 K 순열을 찾습니다. 이를 찾기 위해 모든 순열에 다음 숫자 N번째(최대)를 삽입하고 해당 숫자를 추가한 후 반전 횟수가 K와 같은 숫자를 결과에서 계산해야 합니다. (K – 3) 반전 없이 (N – 1) 숫자의 순열을 취하면 마지막 색인에서 세 번째 색인에 있는 새 숫자를 이동합니다. K개의 반전 횟수를 사용하면 find_permutations(N-1, K-3)이 답이 됩니다. 다른 반전에도 동일한 논리를 사용할 수 있으며 위의 재귀를 최종 답으로 얻습니다.

Input

#include <bits/stdc++.h>
using namespace std;
const int X = 100;
int a = 0;
int arr[X][X];
// recursive function
int find_permutations (int N_numbers, int K_inversion){
    if (N_numbers == 0){
      return 0;            // return 0 when N becomes 0
    }
    if (K_inversion == 0)
        return 1;            // return 1 when K becomes 1
    if (arr[N_numbers][K_inversion] != 0)
        return arr[N_numbers][K_inversion];
    int result = 0;
    for (int i = 0; i <= K_inversion; i++){

        if (i <= N_numbers - 1)
          result += find_permutations (N_numbers - 1, K_inversion - i);
    }
    arr[N_numbers][K_inversion] = result;
    return result;
}
// main function
int main (){
    int N, K;
    cin >> N;    // taking input from user
    cin >> K;
    cout << find_permutations (N, K);
    return 0;
}

Output

0

Input− N = 4, K = 3

Output− 6

Conclusion

이 논문에서는 O(n * k)의 문제를 찾기 위해 문제를 해결했습니다. 시간 복잡도의 K 역전의 순열. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 K개의 역순 쌍으로 순열의 수를 찾기 위해 C++를 사용하여 코드를 작성하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!