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). 2 už je 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). 2 už je 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 (1 má 1, 2 má 2, 3 má 8 a 4 má 3)

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

Java

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

Java

import java.util.Scanner;

public class LongestCollatzSequence
{
    private static final int CACHE_SIZE = 5_000_000;

    // stores collatz sequence for number at index
    private static int[] cache = new int[CACHE_SIZE + 1];

    // stores number with max collatz sequence at index
    private static int[] collatzCache = new int[CACHE_SIZE + 1];

    public static void main(String[] args)
    {
        precomputeCache();

        Scanner scanner = new Scanner(System.in);
        int tests = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < tests; i++)
        {
            int n = Integer.parseInt(scanner.nextLine());
            System.out.println(collatzCache[n]);
        }

        scanner.close();
    }

    private static void precomputeCache()
    {
        cache[0] = 1;
        cache[1] = 1;
        collatzCache[0] = 1;
        collatzCache[1] = 1;
        int maxSeq = 0;
        int maxNum = 0;
        for (int j = 2; j <= CACHE_SIZE; j++)
        {
            int collatzSeq = 0;
            long number = j;
            while (number > 1)
            {
                if(cache[j] > 0)
                {
                    collatzSeq += cache[j];
                    break;
                }
                collatzSeq++;
                if(number % 2 == 0)
                {
                    number >>= 1;
                }
                else
                {
                    number = 3 * number + 1;
                }
            }
            cache[j] = collatzSeq;
            if(collatzSeq >= maxSeq)
            {
                maxSeq = collatzSeq;
                maxNum = j;
            }
            collatzCache[j] = maxNum;
        }
    }
}

import java.util.Scanner;

public class LongestCollatzSequence

{

private static final int CACHE_SIZE = 5_000_000;

// stores collatz sequence for number at index

private static int[] cache = new int[CACHE_SIZE + 1];

// stores number with max collatz sequence at index

private static int[] collatzCache = new int[CACHE_SIZE + 1];

public static void main(String[] args)

{

precomputeCache();

Scanner scanner = new Scanner(System.in);

int tests = Integer.parseInt(scanner.nextLine());

for (int i = 0; i < tests; i++)

{

int n = Integer.parseInt(scanner.nextLine());

System.out.println(collatzCache[n]);

}

scanner.close();

}

private static void precomputeCache()

{

cache[0] = 1;

cache[1] = 1;

collatzCache[0] = 1;

collatzCache[1] = 1;

int maxSeq = 0;

int maxNum = 0;

for (int j = 2; j <= CACHE_SIZE; j++)

{

int collatzSeq = 0;

long number = j;

while (number > 1)

{

if(cache[j] > 0)

{

collatzSeq += cache[j];

break;

}

collatzSeq++;

if(number % 2 == 0)

{

number >>= 1;

}

else

{

number = 3 * number + 1;

}

cache[j] = collatzSeq;

if(collatzSeq >= maxSeq)

{

maxSeq = collatzSeq;

maxNum = j;

}

collatzCache[j] = maxNum;

}

Pavol Pidanič

Dokážem na 10 prstoch napočítať do 1023

Hackerrank – Project Euler+ #014 – Longest Collatz sequence

Hackerrank – Popis problému

Riešenie

Java

Leave a Reply Cancel reply