P0017. Siracusa ataca de nou P14410


Statement
 

pdf   zip

html

Sigui n un natural qualsevol més gran que zero. Considereu aquest algorisme:

  • Si n = 1, pareu.
  • Si n és parell, dividiu-lo per 2.
  • Si n és senar, multipliqueu-lo per 3 i sumeu-li 1.

Per exemple, començant amb 6 s’obté 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

La conjectura 3n + 1 diu que començant en qualsevol n > 0, sempre s’arriba a 1. Encara que no se n’ha trobat cap demostració, sí que s’ha pogut comprovar, mitjançant ordinadors, que la conjectura és certa per a tota n ≤ 4035225266123964416.

Feu un programa que llegeixi dos naturals m i p i escrigui quins naturals entre 1 i m arriben a 1 en p o més passos. També cal dir fins a on de lluny arriben tots aquests m nombres, és a dir, quin és el nombre més gran contingut en les seves successions.

El vostre programa ha d’implementar i usar l’acció

void convergeix(int n, int& k, int& lluny);

que, donat un enter estrictament positiu |n|, desa al paràmetre |k| el nombre de passos que triga |n| en arribar a 1, i desa al paràmetre |lluny| el nombre més gran que s’hagi vist en el procés. Per exemple, |convergeix(6, k, lluny);| desa un 8 a |k| i un 16 a |lluny|. Similarment, |convergeix(4, k, lluny);| desa un 2 a |k| i un 4 a |lluny|, i |convergeix(1, k, lluny);| deixa un 0 a |k| i un 1 a |lluny|.

Entrada

L’entrada són dos naturals m i p, amb 1 ≤ m ≤ 50000.

Sortida

Cal escriure tots els nombres entre 1 i m que arriben a 1 en p o més passos, un per línia. A més, cal escriure el nombre més gran que s’ha produït, seguint el format dels exemples.

Public test cases
  • Input

    6 7
    

    Output

    3
    6
    S'arriba a 16.
    
  • Input

    16 0
    

    Output

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    S'arriba a 160.
    
  • Input

    1 0
    

    Output

    1
    S'arriba a 1.
    
  • Input

    2 1
    

    Output

    2
    S'arriba a 2.
    
  • Input

    30 200
    

    Output

    S'arriba a 9232.
    
  • Input

    50000 323
    

    Output

    35655
    S'arriba a 121012864.
    
  • Input

    447 140
    

    Output

    327
    S'arriba a 39364.
    
  • Information
    Author
    Professorat de P1
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Haskell