Nombre de permutacions emparellades P20410


Statement
 

pdf   zip

html

Una permutació d’n elements {0,…,n−1} es diu emparellada si els elements a les posicions parells són tots parells o tots senars i, si els elements en posicions senars es troben en ordre creixent. Les posicions es comencen a comptar des de zero per l’esquerra.

Per exemple, aquestes són totes les permutacions emparellades per a n=5:

0 1 2 3 4
0 1 4 3 2
2 1 0 3 4
2 1 4 3 0
4 1 0 3 2
4 1 2 3 0

i aquestes són totes les permutacions emparellades per a n=6:

0 1 2 3 4 5
0 1 4 3 2 5
1 0 3 2 5 4
1 0 5 2 3 4
2 1 0 3 4 5
2 1 4 3 0 5
3 0 1 2 5 4
3 0 5 2 1 4
4 1 0 3 2 5
4 1 2 3 0 5
5 0 1 2 3 4
5 0 3 2 1 4

Feu un programa de generació exhaustiva que llegeixi una seqüència de nombre naturals n i que, per a cadascun d’ells, escrigui el nombre de permutacions emparellades d’n elements. Especifiqueu adientment el procediment recursiu.

Public test cases
  • Input

    5
    6
    2
    3
    13
    

    Output

    6
    12
    2
    2
    5040
    
  • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python