P0017. Siracusa ataca de nou P14410
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ó
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.
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.
- Author
- Professorat de P1
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++ Haskell