Почему ошибка сегментации броска кода?

Question

Задача состоит в том, чтобы найти число i <= n, n <= 500000, для которого существует самый длинный ряд Коллатца. Ряд Коллатца для числа n оканчивается на 1, и условия таковы, если n четное, следующий член = n / 2, если n нечетный, следующий член = 3 * n + 1 </p>

Ну, по сути ряд коллатца всегда заканчивается на 1 для всех чисел.

Следовательно, любое число не повторяется в его серии коллатца. Используя этот факт, я написал следующий код LOGI C: я запускаю некоторое время l oop, которое продолжается до n, и для каждой итерации я сохраняю длину ряда для этого i. Если i встречается в ряду некоторого n> = r> i, то i завершает l oop и добавляет длину i к r. Например, скажем, серия 3 равна 3, 10, 5, 16, 8, 4, 2, 1. Теперь длина, соответствующая 2, уже будет сохранена в массиве series_length, поэтому я использую это значение.

Затем для l oop рядом с этим находит самую длинную серию и отображает ответ.

Код работает нормально при n <= 1818, если быть точным, но показывает ошибку сегментации и далее (не знаю почему :( Пожалуйста, помогите </p>

КОД:

#include <stdio.h>

int length = 0, series_length[500000], maxlength = 0;

void store_length(int n) {
    while(n > 1 && series_length[n] == 0) {
        length++;
        if(n%2 == 0) {
            n = n/2;
        }
        else {
            n = 3*n + 1;
        }
    }
    length += series_length[n];
}

int main() {
    int n, i = 1, result;
    scanf("%d", &n);
    series_length[1] = 1;//redundant statement

    while(i <= n) {
        store_length(i);
        series_length[i] = length;
        length = 0;
        i++;
    }

    for(int i = 1;i <= n; i++) {
        if(maxlength <= series_length[i]) {
            maxlength = series_length[i];
            result = i;
        }
    }

    printf("%d %d\n", result, maxlength);

    return 0;
}

ВХОД - 10 ВЫХОД - 9 20 (как ожидается)

ВХОД - 100000 ВЫХОД - Ожидается ошибка сегментации - 77031 351

Answer 1

Ваше значение для n выходит за пределы диапазона.

У вас есть строка n = 3*n + 1; в функции store_length

Запуск этого с GDB с вводом как 100000 т

 Thread 1 received signal SIGSEGV, Segmentation fault.
 0x0000000000401545 in store_length (n=532060) at 29_01.c:6
6           while(n > 1 && series_length[n] == 0) {
(gdb) p n
$1 = 532060

Answer 2

• сохраняйте его, только если он подходит
• ... и используйте его, если он уже был вычислен
• избегайте глобальных переменных
• предпочитайте значения без знака
• [используйте описательные имена переменных]

---

#include <stdio.h>

#define THE_SIZE 500000

unsigned series_length[THE_SIZE]= {0,};

unsigned get_length(unsigned val) {
    unsigned steps;
    for (steps=0; val > 1 ; steps++) {
        if (val < THE_SIZE && series_length[val]) { steps += series_length[val]; break; }
        if(val %2 ) val = 3*val + 1;
        else val /= 2;
    }
    return steps;
}

int main( int argc, char **argv) {
    unsigned top, val , result;
    unsigned  best,maxlength ;

    sscanf(argv[1], "%u", &top);

    series_length[1] = 1;//redundant statement

    best = maxlength = 0;
    for(val=1;val <= top; val++) {
        result = get_length(val);
        // store it if it fits;
        if(val<THE_SIZE) series_length[val] = result;
        if (result < maxlength) continue;
        best = val; maxlength = result;
    }


    printf("%u %u\n", best, maxlength);

    return 0;
}

---

Наконец, просто ради интереса, уменьшите массив

#define THE_SIZE 500

, и Программа должна дать тот же результат для данного значения. (это делает)

Answer 3

Вы получите максимальное значение 24 648 077 896 при n = 487039.

Таким образом, вы должны использовать тип long long int для n, и вы должны использовать массив из 24 648 077 896 целых чисел, чтобы избежать ошибки сегментации. К сожалению, мне никогда не удавалось выделить блок в 100 ГБ. Таким образом, ваша оптимизация нежизнеспособна.

Без оптимизации массива я могу отсканировать все значения 500000 n за 265 мс.

Вот мой код:

#include <stdio.h>

int collatz_length(int n) {
    int length = 0;
    long long int v = (long long int)n;
    while (v > 1) {
        if ((v&1) == 0)
            v = v / 2;
        else
            v = v*3 + 1;
        length++;
    }
    return length;
}

int main() {
    int max_i, max_l = 0;
    for (int i = 500000; i > 0; i--) {
        int l = collatz_length(i);
        if (l > max_l){
            max_l = l;
            max_i = i;
        }
    }
    printf("i: %d l: %d\n", max_i, max_l);
    return 0;
}