Tornar

L'algoritme 3n+1

El problema que es planteja aquí és estudiar un dels algoritmes més clàssics no resolts de la ciència de l'Algorítmica: l'algoritme 3n+1. Considerem el següent algoritme:

  1. entrar n

  2. imprimir n

  3. si n =1 aleshores ACABA EL PROGRAMA 

  4. si n es senar aleshores n:=3n+1

  5. en cas contrari, és a dir, si n es parell, aleshores n:=n/2

  6. tornar a la línia 2

Per exemple, donat el número 22 el programa imprimiria la següent seqüència de números: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1. Aquesta seqüència rep el nom de cicle del número 22. Aquest és un cicle de longitud 16. 

És una conjectura no demostrada que aquest algoritme acaba sempre, és a dir, que el cicle de tot nombre enter és un cicle finit.

El problema que es planteja és determinar el cicle de longitud màxima i el de longitud mínima de entre els nombres compresos entre dos llegits en un fitxer.

El fitxer d'entrada consistirà en dos nombres enters positius més petits que 10.000 (i i j). El fitxer de sortida haurà de contenir el nombre comprés entre i i j (ambdós inclosos) que té un cicle més petit, la longitud d'aquest cicle, el nombre comprés entre i i j (ambdós inclosos) que té un cicle més gran i la longitud d'aquest últim cicle:

Exemple:

5

6

7

8

9

10

16

3

22

4

28

5

8

10

11

2

14

16

4

5

34

1

7

8

2

16

17

22

4

1

8

52

11

2

4

26

34

1

2

13

17

4

1

40

52

2

20

26

1

10

13

5

40

16

20

8

10

4

5

2

16

1

8

4

2

1

 

fitxer d'entrada:

5 10

 

fitxer de sortida:

8 4

9 20

 

Tornar