Задача несложная, решил буквально так, как написано в задании. Для ускорения работы программы использовал тернарную операцию при расчёте последовательности Коллатца.
Условия задачи
Следующая повторяющаяся последовательность определена для множества натуральных чисел:
n → n/2 (n - четное)
n → 3n + 1 (n - нечетное)
Используя описанное выше правило и начиная с 13, сгенерируется следующая последовательность:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Получившаяся последовательность (начиная с 13 и заканчивая 1) содержит 10 элементов. Хотя это до сих пор и не доказано (проблема Коллатца (Collatz)), предполагается, что все сгенерированные таким образом последовательности оканчиваются на 1.
Какой начальный элемент меньше миллиона генерирует самую длинную последовательность?
Примечание: Следующие за первым элементы последовательности могут быть больше миллиона.
Первый вариант программы
Никаких особых алгоритмов в этой задаче в голову не пришло.
В цикле перебираются все числа до 1000000 и для каждого из них генерируется последовательность Коллатца. Длина цепочки в программе каждый раз измеряется с помощью счетчика и обновляет значение числа, если цепочка самая длинная.
Единственной особенностью задачи является необходимость использования типа unsigned long long для промежуточных расчётов, т.к. в процессе вычисления цепочки получаются огромные числа.
Время работы программы - около 1 секунды.
Второй вариант программы
Поскольку в любом случае придётся перебирать все числа до 1000000 (поправьте, если я ошибаюсь), то попробовал ускорить вычисление самой цепочки Коллатца.
Вместо условного выражения if-else применил тернарную операцию вида:
<условие> ? <выраж.1 : <выраж.2>
Ответ на задачу:
Время работы программы сократилось до 0.8 - 0.9 секунд, т.е. тернарная операция работает немного быстрее условных выражений. Возможно кому-то понадобится.
P.S. Изначальная цель блога - получить "фидбек" в комментариях, чтобы более опытные "кодеры" указывали мне на ошибки, советовали и всячески помогали в саморазвитии.
Также приглашаю всех на мой сайт)
На нем Вы можете посмотреть ответ на задачу Эйлера 14 (когда необходима лишь небольшая подсказка) и последний, самый быстрый вариант решения.
В общем, добро пожаловать на канал))