Cho số nguyên N. Nhiệm vụ: tìm hoán vị tốt (good permutation) của N số tự nhiên đầu tiên.
Định nghĩa hoán vị tốt
Hoán vị P thỏa mãn: P[i] ≠ i và P[P[i]] = i với mọi 1 ≤ i ≤ N.
Ví dụ minh họa
Input: N = 1 Output: -1
N = 4: Hoán vị tốt là 2 1 4 3
Phương pháp giải
Nếu N lẻ → không có nghiệm. N chẵn → hoán đổi cặp (2i, 2i-1) cho i = 1 đến N/2.
Ví dụ chương trình
#include <iostream>
using namespace std;
void printGoodPermutation(int n) {
if (n % 2 != 0) cout << -1;
else for (int i = 1; i <= n / 2; i++)
cout << (2*i) << "\t" << (2*i - 1) << "\t";
}
int main() {
int n = 4;
cout << "Hoán vị tốt của " << n << " số tự nhiên đầu tiên:\n";
printGoodPermutation(n);
return 0;
}
Kết quả
Hoán vị tốt của 4 số tự nhiên đầu tiên: 2 1 4 3