Cerința

Se dă un număr natural n. Construiți un șir format din primele 2n numere naturale, dispuse astfel:

• se pleacă de la șirul 1 2
• exact la mijlocul acestui șir se inserează șirul 3 4 și se obține 1 3 4 2
• exact la mijlocul acestui șir se inserează șirul 5 6 7 8 și se obține 1 3 5 6 7 8 4 2
• etc
• în general, la mijlocul șirului format din primele 2k numere naturale se inserează șirul ordonat format din următoarele 2k numere naturale.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran elementele șirului construit, separate prin câte un spațiu.

Restricții și precizări

• 2 ≤ n ≤ 15

Exemplu

Intrare

4

Ieșire

1 3 5 6 9 10 11 12 13 14 15 16 7 8 4 2

#include <bits/stdc++.h>
using namespace std;

int P[20];

void generare(int k , int n)
{
    if(k <= n)
    {
        //afisez numerele de la 2^(k-1)+1 la 2^k
        int mij = (P[k-1] + P[k])/2;
        for(int i = P[k-1] + 1 ; i <= mij ; i ++)
            cout << i << " ";
        generare(k+1 , n);
        for(int i = mij + 1 ; i <= P[k] ; i ++)
            cout << i << " ";
    }
}

int main()
{
    int n;
    cin >> n;
    P[0] = 1;
    for(int i = 1 ; i <= n ; i ++)
        P[i] = 2 * P[i-1];
    cout << 1 << " ";
    generare(1 , n);
    return 0;
}