Tulis kod menggunakan C++ untuk mencari bilangan pilih atur dengan pasangan K dalam susunan terbalik

Dalam tatasusunan, jika a[i] > a[j] dan 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.

Kaedah penyelesaian

Kita boleh menggunakan kaedah brute force, mula-mula cari semua pilih atur nombor N pertama, dan kemudian semak sama ada semua pembalikan adalah sama atau K. Jika ya, tambahkan pembilang hasil.

Kaedah yang cekap

Dalam kaedah ini kita mempunyai N digit bagi N nombor asli pertama. Semua pilih atur nombor ini dikira di tempat lain, dari mana kita dapati pilih pilih K. Untuk mencarinya, kami akan memasukkan nombor Nth (maksimum) seterusnya dalam semua pilih atur dan selepas menambah nombor itu cari nombor yang kiraan penyongsangannya bersamaan dengan K harus dikira dalam keputusan kami. Mengambil pilih atur nombor (N – 1) tanpa penyongsangan (K – 3), kami akan mengalihkan nombor baharu pada indeks ketiga daripada indeks terakhir. Dengan bilangan K pembalikan, find_permutations(N-1, K-3) akan menjadi jawapan kami. Logik yang sama boleh digunakan untuk penyongsangan lain dan kami akan mendapat rekursi di atas sebagai jawapan akhir.

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

Kesimpulan

Dalam kertas kerja ini, kami menyelesaikan masalah dengan (n)O masa Permutasi K penyongsangan kerumitan. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Tulis kod menggunakan C++ untuk mencari bilangan pilih atur dengan pasangan K dalam susunan terbalik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!