ACM RTK - 1. skupina

Collatz++

Collatzevo zaporedje je zaporedje naravnih števil, v katerem je vsak člen izračunan iz prejšnjega po naslednjem pravilu: če je prejšnji člen — recimo mu n — deljiv z 2, je naslednji člen enak n/2, sicer pa je naslednji člen enak 3n + 1. Ustavimo se, ko pridemo do števila 1.

Konkretno zaporedje, ki ga na ta način dobimo, je odvisno od tega, s katerim številom začnemo. Na primer, Collatzevo zaporedje z začetnim členom 15 je:

15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Gojmir je napisal funkcijo, ki poišče takšno število k z območja od vključno a do vključno b, da Collatzevo zaporedje z začetkom k nekje doseže maksimalno vrednost. Npr. na območju od 30 do 50 je takšno število k = 31, saj je pripadajoče zaporedje:

31, 94, 47, 142, 71, 214, ..., 6154, 3077, 9232, 4616, 2308, 1154, ..., 5, 16, 8, 4, 2, 1.

To zaporedje doseže maksimum 9232. Če izberemo kot začetni člen katerokoli drugo celo število z območja od 30 do 50, tega ne bomo presegli.

Kmalu pa je opazil, da ima njegova funkcija pomanjkljivost, saj k = 41 prav tako doseže enak maksimum. Ker je izčrpan in ne more več programirati, potrebuje tvojo pomoč. Napiši podprogram oz. funkcijo PoisciVse(a, b), ki poišče vsa takšna števila. (Tvoja funkcija lahko rezultat vrne v obliki seznama, tabele, vektorja ali česa podobnega, lahko pa ga izpiše na standardni izhod ali v kakšno datoteko, karkoli ti je lažje.)

Primer: PoisciVse(30, 50) mora najti števila 31, 41 in 47 — če se namreč Collatzevo zaporedje začne z enim od teh treh števil, bo sčasoma doseglo vrednost 9232; in te vrednosti ne bo nikoli doseglo (ali preseglo), če se začne s katerimkoli drugim številom od 30 do 50.