[Algorytmy] Problem Collatza

[majkz]

Witam!

Robię sobie w ramach treningu zadania z ProjectEuler. Aktualnie próbuję przepchnąć

Kod: Zaznacz cały

https://projecteuler.net/problem=14

i szczerze powiedziawszy utknąłem. Nie mogę znaleźć żadnego wyraźnego błędu w moim algorytmie, dlatego dobrze by było jakby sprawdził go ktoś nie tak pewien jego słuszności jak ja.

Algorytm to rasowy brute - lecę w pętli od 2 do 999999 i sprawdzam, która liczba generuje najdłuższy ciąg (mam nadzieję, że tak jest).

Z góry dziękuję za pomoc!

Kod: Zaznacz cały

#include <stdio.h>

int length(int x);

int main(){
    int max;
    int tmp = 0;
    int tmp2;

    int i;
    for(i = 2; i < 1000000; i++){
        tmp2 = length(i);
        if(tmp2 > tmp){
            tmp = tmp2;
            max = i;
        }

        printf("%d
", i);
    }

    printf("

%d
", max);

    return 0;
}

int length(int x){
    int result = 1;
    while(x > 1){
        if(x%2 == 0)
            x = x/2;
        else
            x = (3*x) + 1;

        result++;
    }

    return result;
}

[Zordon]

może spróbuj long longi, nie wiem czy Ci się zmienna nie przekręca

[majkz]

Otóż to. Dzięki!
Próbowałem wcześniej na longach i myślałem, że ew. na nich się wszystko zmieści, ale jak się okazuje dla szukanej wartości jeden z elementów ciągu, który się od niej zaczyna, przyjmuje wartość 2974984576 przez co wszystko się sypało.

[Vardamir]

Taka ciekawostka, jak poprawić złożoność (obliczeniową kosztem pamięciowej). Tylko, że C++

Jeśli wpadniemy na liczbę mniejsza niż podana to odczytujemy policzoną wcześniej wartość.

Kod: Zaznacz cały

#include <iostream>

int T[1000000];

int collatz (int _s)
{
    long int x_n0 = _s, x_n1;
    int i=1;
    while (true){
        x_n1 = (x_n0 % 2) ? (3 * x_n0 + 1) : (x_n0 / 2);
        if (x_n1<_s) return T[x_n1]+i;
        x_n0 = x_n1;
        i++;
    }
}

int main() {
    int max=0, answer;
    T[1]=1;
    for (int i = 2; i < 1000000; ++i) {
        T[i] = collatz(i);
        if(T[i]>max) {
            max = T[i];
            answer = i;
        }
    }
    std::cout<<answer;
    return 0;
}

Czas wykonania ok. 0.045 sec

Swoją drogą super sprawa, zabieram się do rozwiązywania. Dobry trening przed egzaminem z algorytmów.