Ta có N số tự nhiên đầu tiên. Nhiệm vụ của chúng ta là lấy một hoán vị của chúng trong đó hiệu số tuyệt đối giữa hai phần tử liên tiếp là> 1. Nếu không có hoán vị nào như vậy, hãy trả về -1.
Cách tiếp cận rất đơn giản. Chúng tôi sẽ sử dụng cách tiếp cận tham lam. Chúng ta sẽ sắp xếp tất cả các số lẻ theo thứ tự tăng hoặc giảm, sau đó sắp xếp tất cả các số chẵn theo thứ tự giảm dần hoặc tăng dần
Thuật toán
sắp xếpN (n)
Begin if N is 1, then return 1 if N is 2 or 3, then return -1 as no such permutation is not present even_max and odd_max is set as max even and odd number less or equal to n arrange all odd numbers in descending order arrange all even numbers in descending order End
Ví dụ
#include <iostream>
using namespace std;
void arrangeN(int N) {
if (N == 1) { //if N is 1, only that will be placed
cout << "1";
return;
}
if (N == 2 || N == 3) { //for N = 2 and 3, no such permutation is available
cout << "-1";
return;
}
int even_max = -1, odd_max = -1;
//find max even and odd which are less than or equal to N
if (N % 2 == 0) {
even_max = N;
odd_max = N - 1;
} else {
odd_max = N;
even_max = N - 1;
}
while (odd_max >= 1) { //print all odd numbers in decreasing order
cout << odd_max << " ";
odd_max -= 2;
}
while (even_max >= 2) { //print all even numbers in decreasing order
cout << even_max << " ";
even_max -= 2;
}
}
int main() {
int N = 8;
arrangeN(N);
} Đầu ra
7 5 3 1 8 6 4 2