ในอาร์เรย์ คู่ a[i], a[j] เรียกว่าการผกผันถ้า a[i]> a[j] และ i
เราสามารถประยุกต์ใช้แนวทางกำลังดุร้าย ซึ่งเป็นครั้งแรกที่ค้นหาการเรียงสับเปลี่ยนของตัวเลข N ตัวแรก จากนั้นตรวจสอบการผกผันทั้งหมดว่ามีค่าเท่ากับ K หรือไม่ ถ้าใช่ ให้เพิ่มตัวนับผลลัพธ์
ในแนวทางนี้ เรามี N หลักของ N ตัวเลขธรรมชาติตัวแรก พีชคณิตทั้งหมดของตัวเลขนั้นคำนวณจากที่อื่นที่เรากำลังมองหาการเรียงสับเปลี่ยน K ในการค้นหา เราจะใส่ตัวเลขถัดไปที่ N (ใหญ่ที่สุด) ในการเรียงสับเปลี่ยนทั้งหมด และมองหาตัวเลขที่มีการนับผกผันเท่ากับ K หลังจากเพิ่มตัวเลขนี้แล้ว ควรนับในผลลัพธ์ของเรา การเรียงสับเปลี่ยนของตัวเลข (N – 1) ที่ไม่มี (K – 3) ผกผัน เราจะเปลี่ยนตัวเลขใหม่ที่ดัชนีที่ 3 จากล่าสุด จำนวนการผกผันจะเป็น K และ find_permutations(N-1, K-3) จะเป็นคำตอบของเรา ตรรกะเดียวกันนี้สามารถใช้ได้กับการผกผันอื่นๆ และเราจะมาถึงการเรียกซ้ำข้างต้นเป็นคำตอบสุดท้าย
อินพุต - N =4, K =3
เอาต์พุต - 6
ในบทความนี้ เราแก้ปัญหาเพื่อค้นหาจำนวนพีชคณิตที่มีการผกผัน K จาก O(n * k) ความซับซ้อนของเวลา นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์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.
แนวทางในการหาแนวทางแก้ไข
แนวทางที่มีประสิทธิภาพ
อินพุต
#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;
} ผลลัพธ์
0
บทสรุป
