Programozás‎ > ‎Feladatok‎ > ‎

3N+1 probléma

Tekintsük a következő algoritmust, mely egy adott n számra a következő sorozatot adja:
Ha = 1, akkor vége a sorozatnak. Például n = 22 esetén a sorozat: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
A sejtés az, hogy a fenti algoritmus minden egész n-re (de legalábbis 1 és 1000000 között) véges sorozatot ad (utolsó eleme 1).
 

Feladat

Írjunk programot, ami i, j számokra megadja az n ∈ [ i] kezdőértékekkel generált sorozatok maximális elemszámát.

Bemenet

A bemenet sorai i , j számpárokat tartalmaznak (1 <= i < j < 1000000). 

Kimenet

A kimenet soraiba i-t, j-t és az j ] intervallum elemeire generált sorozatok maximális elemszámát kell írni (szóközökkel elválasztva).

Példa

Bemenet  Kimenet
1 10
100 200
201 210
900 1000
1 10 20
100 200 125
201 210 89
900 1000 174


Tesztadatok

Címkék

A feladat forrása: Steven Skienna, Programming Challenges 
Algoritmusok: dinamikus programozás

megoldás