Блог

Я пишу программу для поиска самой длинной последовательности Collatz, начинающейся с 1 000 000.

Я действительно гордился этим кодом, он казался таким эффективным, чистым и хорошо написанным… пока я не попытался его запустить. После небольшой отладки, чтобы заставить ее скомпилироваться, я обнаружил, что при запуске программы происходит сбой.

Я использовал оба

 int array[1000000];
  

и

 int *array;
array = (int*)calloc(s, sizeof(int));
  

(где s=1000000 )

объявить массив из 1 000 000 пробелов.

Итак, часть А) моего вопроса: смешно или возможно объявить массив такого размера?

и часть B) моего вопроса: это используется для своего рода «контрольного списка», проверяющего, какие числа уже были просмотрены. Есть ли более простой или лучший или просто другой метод «проверки» чисел, который я должен использовать вместо этого?

код выглядит следующим образом:

 // This is a program to find the longest Collatz sequence starting under 1,000,000

#include <stdio.h>
#include <stdlib.h>

int main()
{

// Collatz sequence: IF EVEN n/2  ::  IF ODD 3n 1

//define ints
int i;
int n; 
int c; // counter of sequence length
int longestsequence = 0;
int beststart;
int s = 1000000; //size of array

//define int array
    //int array[999999];

//define array using calloc
//define pointer for calloc int array
int *array; 
// do your calloc thing
array = (int*)calloc(s, sizeof(int)); // allocates 1,000,000 spots (s) of size "int" to array "array"

//fill array
for(i = 0; i < 1000000; i  ) 
{
    array[i] = i;
}

for(i = 999999; i > 500000; i--)
{
    if(array[i] == 0) // skip if number has already been seen
        goto done;

    n = i;
    c = 0;

    //TEST
    printf("Current starting number is: %dn", i);
    //TEST

    while(n != 4) // run and count collatz sequence
    {

        //TEST
        //printf("test1n");
        //TEST

        if(n % 2 == 0) // EVEN
            n = n/2;
        else           // ODD
            n = 3 * n   1;

        //TEST
        //printf("test2n");
        //TEST

        c  ;

        //TEST
        //printf("test3n");
        //TEST

        if(n < 1000000 amp;amp; array[n] != 0) // makes note of used numbers under 1000000
            array[n] = 0;

        //TEST
        //printf("test4n");
        //TEST

    }

    if(longestsequence < c)
    {
        longestsequence = c;
        beststart = i;
        //TEST
        printf("Current best start is: %dn", beststart);
        //TEST
    }

    done:
}

printf("the starting number that produces the longest Collatz sequence is...n");
printf("%dn", beststart);


getchar();
return 0;
}
  

Спасибо за любую помощь и предложения! Ссылки на полезные источники всегда приветствуются.

ОБНОВЛЕНИЕ!

1.My код теперь выглядит так ^^^^

и

2. Программа запускается, а затем таинственным образом останавливается на i значении 999167

 for(i = 999999; i > 4; i  )
  

Здесь вы легко выходите за пределы массива. Я думаю, вы имели в виду

 for(i = 999999; i > 4; --i)
                //     ^^^
  

Кроме того, как и в вашей реализации, 1 миллиона элементов недостаточно.

Возьмите n == 999999 в качестве примера. На 1-м шаге вы вычисляете 3 * n 1 , что, очевидно, намного больше 1000000. Простым решением было бы изменить

     if(array[n-1] != 0) // makes note of used numbers
        array[n-1] = 0;
  

в

     if(n < s amp;amp; array[n-1] != 0) // makes note of used numbers
        array[n-1] = 0;
  

который просто отключает поиск результатов при n превышении границы массива.

Вы могли бы использовать простой связанный список чисел, который уменьшит требования к памяти за счет «длительного» времени поиска. Я всегда замечал немного повторений:

 1
2 → 1 (already seen in 1, so link to the existing 1)
3 → 5 → 16 → 8 → 4 → 2 (already seen in 2, so link to the existing 2)
4 (link to existing after 8)
5 (link to existing after 5)
etc.
  

У вас было бы число A и, возможно, еще одно число B, связанное с числом N для некоторых чисел, но N будет ссылаться только на одно число C. Например:

  A ->  N -> C
 3 -> 10 -> 5
20 -> 10 -> 5
 B ->  N -> C
  

Конечно, вы могли бы оптимизировать его, сохранив длину списка и дополнительный указатель, содержащий следующее соседнее число, что позволит вам реализовать двоичный поиск, используя эту длину в качестве ориентира.

Однако, если вы ищете только самую длинную длину последовательности, а не саму последовательность, почему вы просто не сохраняете самую длинную найденную длину и не сравниваете ее с длиной текущей последовательности? Сохранение чисел только для вычисления длины кажется излишним. Что-то вроде следующего псевдокода:

 Longest := 0

For N = 1 To 1000000
    Length := 1
    X := N

    While X != 1
        Length := Length   1

        If IsEven(X) Then
            X := 3 * X   1
        Else
            X := X / 2
        End If
    End While

    If Length > Longest Then
        Longest := Length
    End If
End For
Print("Longest sequence less than 1000000 is: ", Longest)
  

Строка

         n = 3 * n   1;
  

в итоге устанавливается значение n , превышающее допустимый индекс. Самый высокий допустимый индекс равен 999999 . Вы должны убедиться, что n это меньше или равно 1000000 , прежде чем обращаться к массиву в:

      if(array[n-1] != 0) // makes note of used numbers
        array[n-1] = 0;
  

Вы не проверяете индекс массива [n-1] в цикле while, чтобы убедиться, что он не превышает границ массива в 1 000 000. Например, в вашем первом цикле i = 999,999 , который делает `n = 999999*3 1 = 2,999,998′.

Решение состоит в том, чтобы убедиться n , что размер вашего массива не превышает ваш.