Project Euler (answers)

Проект Эйлера: Ответ и решение 14 задачи (Самая длинная последовательность Коллатца)

Проект Эйлера (14 задача) сама по себе несложная, однако решение “в лоб” будет неэффективным и медленным. Потому ускорим программу в сто раз

Узнать больше в телеграм-канале: ProjectEuler++

Условия задачи

Следующая повторяющаяся последовательность определена для множества натуральных чисел:
n → n/2 (n – четное)
n → 3n + 1 (n – нечетное)
Используя описанное выше правило и начиная с 13, сгенерируется следующая последовательность:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Получившаяся последовательность (начиная с 13 и заканчивая 1) содержит 10 элементов. Хотя это до сих пор и не доказано (проблема Коллатца (Collatz)), предполагается, что все сгенерированные таким образом последовательности оканчиваются на 1.
Какой начальный элемент меньше миллиона генерирует самую длинную последовательность?
Примечание: Следующие за первым элементы последовательности могут быть больше миллиона.

Содержание статьи

Решение задачи

Самый простой алгоритм
Ускоряем работу программы в сто раз
Еще чуть-чуть ускоряем работу

Ответ и скорость работы программы

Решение - проект Эйлера (14 задача)

Поскольку функция main() получилась несколько длинной – разделил ее на два скриншота.

Самый простой алгоритм

Порядок работы программы очень простой и будет следующим:

Перебираем числа до миллиона.
Для каждого числа рассчитываем длину цепочки по формуле из задания.
Запоминаем число, с которого начинается самая длинная цепочка.
Наслаждаемся целой секундой времени до вычисления результата.
Начинаем думать, как ускорить программу.

Ускоряем работу программы в сто раз

Рассмотрим цепочку из задания:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Прежде чем мы дошли до числа 13 и начали вычислять цепочку, вероятно, были вычислены цепочки для чисел 1,2,3… 11,12.

Потому дойдя до числа 10 в цепочке:

13 → 40 → 20 → 10

… можно прекратить расчет и просто добавить длину цепочки, начинающейся с 10.

10 → 5 → 16 → 8 → 4 → 2 → 1 (7 чисел)

В итоге мы (смотрите скриншот выше):

Создаем массив.
Сохраняем в него длины вычисленных цепочек.
Когда в процессе вычисления встретится число с уже посчитанной длиной цепочки – прерываем расчет и добавляем длину (его цепочки).

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

* Примечание:

#define

Директива препроцессора #define заменяет строку LEN_ARR в программе на цифры 1000000

Еще чуть-чуть ускоряем работу

Используем побитовое умножение

Для определения четности можно использовать не только нахождение остатка от деления:

n % 2 == 0

… но и побитовое сложение:

n & 1

Как это работает:

Возьмем для примера 7 & 1. В двоичном виде это будет выглядеть так 00000111 & 00000001

Сравниваем числа побитово (т.е. 1 & 1 = 1, все остальные варианты 0)

00000111 (7)
& 00000001 (1)
= 00000001 – в итоге обнуляются все цифры кроме последней и 7 & 1 = 1 – число (7) нечетное.

Сравним 8 & 1:

00001000 (8)
& 00000001 (1)
= 00000000 – в итоге обнуляются все цифры и 8 & 1 = 0 – число (8) четное.

Главная хитрость в том, что в двоичном виде все четные числа имеют на конце – 0, а нечетные – 1

Используем битовый сдвиг

Деление на два

n / 2

… также можно заменить на битовый сдвиг вправо

n >> 1

Возьмем для примера число 8 (00001000). Сдвинув бит вправо (00000100) мы получим число 4.

* Примечание:

n = !(n & 1) ? (n >> 1) : (3 * n + 1);

Тернарная операция. Можно заменить на более понятную конструкцию:

if(n%2 == 0)
- n = n/2 :
else
- n = (3 * n + 1);

Измеряем время работы программы

Для измерения времени работы программы подключаем библиотеку time.h:

#include <time.h>

С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.

* Примечания:

clock_t

clock_t это тип данных, определенный через typedef. По сути это обычный целочисленный long

(double)

(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)

CLOCKS_PER_SEC

CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000

Проект Эйлера (14 задача) - ответ и скорость работы программы

В итоге ответ на 14 задачу проекта Эйлера составил 837799, программа считает ответ за 20 миллисекунд.

По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.

Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))

Есть вопросы, господа?

Политика конфиденциальности

Конфиденциальность