мемоизация должна была сработать

Question

без мемоизации это решение для Euler Project 14 отлично работает! Тогда с мемоизацией он должен работать быстрее ... но он останавливается почти на i = 1818 или около того. Как странно! в чем дело, пытаясь понять! вы можете помочь?

#include <stdio.h>

#define limit 1000000

int arr[limit];

int fun(long long int i) {
    long long int count = 1;
    long long int num;
    arr[limit];
    num = i;
    while (num > 1) {
        if (arr[num] != NULL) {
            count = count - 1 + arr[num];
            break;
        }
        if (num % 2 == 0) {
            num = num / 2;
            count++;
        } else {
            num = 3 * num + 1;
            count++;
        }
    }
    arr[i] = count;
    return count;
}

int main() {
    long long int i;
    for (i = 2; i < limit; i++) {
        long long int count = fun(i);
        printf("d %lld c: %lld\n", i, count);
    }
    return 0;
}

Answer 1

Хорошо, я думаю, что основная проблема с вашим кодом заключается в том, что последовательность Коллатца может дать вам числа, которые намного выше, чем то, с которого вы начали, прежде чем спуститься до 1. Согласно Project Euler 14 , вы должны найти начальное число ниже 1000000, которое дает самую длинную цепочку до достижения нуля. Но последовательность Коллатца, начинающаяся с 1819, включает числа, превышающие один миллион. В результате вы пытаетесь получить доступ к элементам arr[], выходящим за границы.

Кроме того, как указано в комментариях, оператор arr[limit]; в вашей функции fun() ничего не делает полезно. Если бы вы включили предупреждения в своем компиляторе, он, вероятно, пометил бы это, а также оператор if(arr[num]!=NULL), который сравнивает указатель void* с целым числом.

Если вы замените первый оператор своего while() блок с if (num < limit && arr[num]!=NULL), тогда вам следует по крайней мере избежать ошибки сегментации.

Ваша функция main() должна быть переписана, чтобы найти начальный номер, который дает самую длинную цепочку, вместо того, чтобы просто распечатать миллион строк данных.

Если хотите, вы можете попробовать запустить это вместо:

#include <stdio.h>

#define LIMIT 1000000

int arr[LIMIT] = { 0 };

long fun(long i) {
    long count = 1;
    long num;
    num = i;
    while (num > 1) {
        if (num < LIMIT && arr[num] != 0) {
            count = count - 1 + arr[num];
            break;
        }
        if (num % 2 == 0) {
            num = num / 2;
            count++;
        }
        else {
            num = 3 * num + 1;
            count++;
        }
    }
    arr[i] = count;
    return count;
}

int main(){
    long i, longest=0, maxstart;
    for (i=2; i<LIMIT; i++) {
        long count = fun(i);
        if (count > longest) {
            longest = count;
            maxstart = i;
        }
    }
    printf("%ld\n",maxstart);
    return 0;
}