Successió de Farey P62377


Statement
 

pdf   zip

thehtml

La successió de Farey d’ordre n és la seqüència ordenada de totes les fraccions irreductibles p/q tals que 0 ≤ p/q ≤ 1 i 1 ≤ qn. A l’exemple d’entrada podeu trobar les successions de Farey per a diversos valors d’n.

Hi ha un parell de propietats matemàtiques que permeten obtenir fàcilment la successió de Farey d’ordre n:

  • Els dos primers termes són 0/1 i 1/n.
  • Donats dos termes consecutius a/b i c/d, el terme següent és (x · ca)/(x · db), on x = ⌊ (n + b)/d ⌋.

Feu un programa que escrigui la successió de Farey per a diversos valors d’n.

Entrada

L’entrada consisteix en diverses n, totes entre 1 i 100.

Sortida

Per a cada n, escriviu la successió de Farey d’ordre n.

Observació

No podeu usar vectors, matrius o similars.

Public test cases
  • Input

    1
    2
    3
    5
    

    Output

    0/1 1/1
    0/1 1/2 1/1
    0/1 1/3 1/2 2/3 1/1
    0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
    
  • Information
    Author
    Jordi Cortadella
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++