Informatika gyűjtemény

Egy szinttel feljebb 3n+1 probléma

2004050607080910

NézetNyomtat

3n+1 probléma

Tekintsük a következő algoritmust, mely egy adott $n$ számra a következő sorozatot adja:
$a_1=n$
$ a_{i+1} = \left\{\begin{array}{l l} \frac{a_{i}}{2} & \textrm{ha } a_i \equiv 0 \textrm{ mod }(2),\\ 3a_{i}+1 & \textrm{ha } a_i \equiv 1 \textrm{ mod }(2). \end{array}\right. $
Ha $a_i=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

Készíts programot (3N_1.PAS, 3N_1.C, ...), megy egy adott $n\in[i,j]$ számokra meghatározza az algoritmus által generált sorozatok maximális elemszámát.

Bemenet

A 3N_1.BE szöveges állomány sorai $i$ és $j$ számpárokat tartalmaz ($1\le i < j < 1000000$).

Kimenet

A 3N_1.KI szöveges állomány soraiban az $i$, $j$ és az $[i,j]$ intervallum elemeire generált sorozatok maximális elemszáma (szóközökkel elválasztva).

Példa

3N_1.BE3N_1.KI
1 10
100 200
201 210
900 1000
1 10 20
100 200 125
201 210 89
900 1000 174

Tesztadatok