Sắp xếp N số tự nhiên đầu tiên sao cho hiệu tuyệt đối liền kề > 1 trong C

Hoán vị 1..N sao cho |a[i] - a[i+1]| > 1 ∀i. Không có giải pháp cho N=2,3.

Giải pháp tham lam

Sắp số lẻ giảm dần, rồi số chẵn giảm dần.

Ví dụ

N=8 → 7 5 3 1 8 6 4 2

Chương trình

#include <iostream>
using namespace std;

void arrange(int N) {
    if (N == 1) { cout << "1"; return; }
    if (N == 2 || N == 3) { cout << "-1"; return; }
    
    int odd = (N % 2) ? N : N - 1;
    int even = (N % 2) ? N - 1 : N;
    
    while (odd >= 1) { cout << odd << " "; odd -= 2; }
    while (even >= 2) { cout << even << " "; even -= 2; }
}

int main() {
    arrange(8);
    return 0;
}

Kết quả

7 5 3 1 8 6 4 2