Hackerrank - Project Euler+ #014 - Longest Collatz sequence

Hackerrank - Popis problému

Celý popis zadania sa nacháza - Hackerrank.

Riešenie

Máme zadané pravidlá, ako sa mení zadané číslo cez Collatzovú postupnosť:

  • ak je n párne, urobím n/2
  • ak je n nepárne, urobím 3n + 1

Zadanie problému obsahuje mnoho čísel, teda počítať každý samostatne nám zaberie množstvo času.

Moje riešenie spočíva v predvýpočítaní si hodnôt sekvencie, ako keby boli zadané čísla od 1 po 5 000 000 a prepoužití už vypočítaných Collatzových sekvencii pre už vypočítané čísla.

Začneme si určením počiatočných hodnôt.

Pre 1 je Collatz sekvencia veľká 1 jednotku.

Pre 2 použijem pravidlo a vydelím ho 2 lebo je párne. Sekvencia už bude dlhá 2. Výsledok po delení je 1. Pozriem sa do cache a zistím, že mám už dĺžku sekvencie pre 1 a to je 1. Teda pre 2 je sekvencia dlhá 2.

Pre 3 podobne: Nemám nič v cache, musím násobiť. Dostanem 10 (už mám dĺžku 1). 10 nie je v cache, musím deliť. Dostanem 5 (už mám dĺžku 2). 5 nie je v cache, musím násobiť, dostanem 16 (dĺžka sekvencie 3). 16 nie je v cache vydelím 2, dostanem 8 (dĺžka 4). 8 nie je v cache, musím deliť, dostanem 4 (dĺžka 5). 4 nie je v cache, delím 2, dostanem 2 (dlžka 6). 2je v cache. Jej dlžka je 2. Teda pripočítam: 6 + 2. Dĺžka sekvencie pre 3 bude 8.

Pre 4: Nie je v cache, delím 2, dostanem 2 (dĺžka 1). 2je v cache s hodnotou 2. Pripočítam 1 + 2. Dostanem dĺžku 3.

atď...

Súčasne si pamätám, aká je najdlšia sekvencia od 1 po dané číslo.

  • pre 1: od 1 po 1 je najdlhšia sekvencia 1
  • pre 2: od 1 po 2 je najdlhšia sekvencia 2 (1 má sekvenciu dlhú 1)
  • pre 3: od 1 po 3 je najdlhšia sekvencia 8
  • pre 4: od 1 po 4 je najdlhšia sekvencia 8 (11, 22, 38 a 43)

Vytvoril som riešenie v týchto programovacích jazykoch:

Všetky riešenia sú dostupné aj na mojom GitHub profile.

Java

Pridaj komentár