В чем проблема с моим кодом Longest Collatz Sequence?

Question

Я пытался решить эту проблему:

Для набора натуральных чисел определена следующая итерационная последовательность:

n → n / 2 (n четное) n → 3n + 1 (n нечетно)

Используя приведенное выше правило и начиная с 13, мы генерируем следующую последовательность: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Видно, что эта последовательность (начиная с 13 и заканчивая 1) содержит 10 членов. Хотя это еще не доказано (проблема Коллатца), считается, что все начальные числа имеют конечное число sh в 1.

Какое начальное число, составляющее менее миллиона, дает самую длинную цепочку?

ПРИМЕЧАНИЕ. После запуска цепочки условия могут превышать go на миллион.

, и я применил приведенный ниже код, но, похоже, это не дает мне правильного ответа. Он вычисляет 910107 как начальное число, которое дает самую длинную цепочку, но ответ должен быть 837799. Что с ним не так?

#include<stdio.h>

int main(void)
{

    int count=1;
    int last_count =0;
    int num=13;
    int temp;
    int Largest_Num=0;
    for(int i=num;i<1000000;i++)
    {
        temp = i;
        while(temp>1)
        {
            if(temp % 2 == 0)
            {
                temp/=2;
            }
            else
            {
                temp =(3*temp)+1;
            }
            count++;   

        }

        if(last_count < count)
        {
            last_count = count;
            Largest_Num = i;
        }

        count =1;
    }
    printf("%d\n",last_count);
    printf("%d",Largest_Num);

    return 0;
}

Answer 1

Я получаю 910107 в качестве начального номера, который дает самую длинную цепочку, но ответ должен быть 837799

int слишком мало для управления большими нужными числами для temp вы переполнены

Это означает, что ваш int находится на 32 битах, и в этом случае int использует только 31 бит для положительные числа при необходимости 32

Вы можете объявить temp как unsigned int (получая на 1 бит больше int , потому что вам нужно только положительные числа), или используйте long , если он для вас на 64 битах, или long , чтобы быть уверенным, что по крайней мере 64 бит

Answer 2

Как заметил @bruno в своем ответе, вы превышаете емкость типа данных int вашей системы. Эта проблема даже намекает на то, что это проблема, с которой вы можете столкнуться, когда она говорит:

ПРИМЕЧАНИЕ. После запуска цепочки допускается go свыше миллиона.

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

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

В этом случае легко избежать переполнения. Единственная переменная, которая требует наблюдения - это temp, и ее значение увеличивается только при вычислении temp =(3*temp)+1. Вы знаете, каково максимальное значение типа int (INT_MAX), и просто алгебраически определить максимальное значение temp, для которого это вычисление не превышает INT_MAX: это (INT_MAX - 1) / 3. Таким образом, вы можете сделать это:

#include <assert.h>
#define TEMP_BOUND ((INT_MAX - 1) / 3)

// ...

            if(temp % 2 == 0) {
                temp /= 2;
            } else {
                assert(temp <= TEMP_BOUND);
                temp = (3 * temp) + 1;
            }

Если в результате вы получите ошибку подтверждения (как при использовании типа int), вы можете повторить попытку с типом данных, который поддерживает большее максимальное значение ; просто убедитесь, что обновили макрос TEMP BOUND соответствующим образом для нового типа данных.

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