Project Euler (answers)

Проект Эйлера: Ответ и решение 25 задачи (1000-значное число Фибоначчи)

Проект Эйлера (25 задача) имеет крайне простой алгоритм решения, однако дает прекрасную возможность поработать с большими числами.

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

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

Последовательность Фибоначчи определяется рекурсивным правилом:
F_n = F_n−1 + F_n−2, где F₁ = 1 и F₂ = 1.
Таким образом, первые 12 членов последовательности равны:
F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144
Двенадцатый член F₁₂ – первый член последовательности, который содержит три цифры.
Каков порядковый номер первого члена последовательности Фибоначчи, содержащего 1000 цифр?

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

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

Описание структуры данных “большое число”
Непосредственно решение
Измеряем время работы программы

Функции, использующиеся в программе

Функция, которая задает начальные значения числа
Функция, которая получает количество цифр в числе
Функция, которая получает следующее значение числа Фибоначчи
Функция, которая определяет превышение переменной своего предельного значения и выводит предупреждение

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

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

Описание структуры данных "большое число"

Поскольку речь в задаче идет о 1000-значных числах, потому для хранения чисел понадобится массив. Однако в этот раз решил сделать не просто char-массив длиной 1000, а более полноценную структуру данных (смотрите выше).

Она включает в себя:

int-массив для хранения большого числа. Поскольку используется тип int, потому каждая ячейка массива будет хранить девятизначные числа ([123456789, 123456789, 999999999…]). Т.е. в итоге 1000-значное число хранится не в char-массиве длиной 1000, а в int-массиве длиной 112.
Длина хранящегося большого числа.

Поскольку в данном случае мы работаем с числами Фибоначчи, потому также храним:

Порядковый номер числа (в ряду): F_1,F_2,F₃…;
Относительное расположение двух соседних чисел Фибоначчи относительно друг друга в ряду. Так первое число – F₁будет prev (предыдущим), а второе – F₂– next (последующим). Однако для следующей пары чисел очередность изменится: F₂станет prev, а next уже будет F_{3 .}

Для хранения относительного расположения применяем перечисление enum. Оно будет принимать всего два значения: prev и next.

На самом деле в памяти будут храниться числа 0 и 1, однако применение именно перечисления имеет свои преимущества:

Понятный код – потому что, читая код, гораздо легче понять для чего служит prev, чем 0.
Данному перечислению невозможно присвоить какие-то другие значения по ошибке.

Непосредственно решение (проект Эйлера - 25 задача)

Поскольку очередное число Фибаначчи вычисляется, как сумма предыдущих:

F_n = F_n−1 + F_n−2, где F₁ = 1 и F₂ = 1.

… потому для вычисления ответа нам понадобится всего два числа: предыдущее число (prev) и следующее за ним (next).

Задаем первых два числа:

F₁ = 1 (prev)
F₂ = 1 (next)

Вычисляем следующее число:

F₃ = F₁ + F₂ = 1 + 1 = 2

Переопределяем порядок чисел:

F2 = 1 (prev)
F3 = 2 (next)

Далее алгоритм повторяется (смотрите скриншот выше):

F4 = F₂ + F₃ = 1 + 2 = 3
F3 = 2 (prev)
F4 = 3 (next)

… до тех пор, пока длина очередного числа не достигнет искомой 1000 знаков.

При этом нет необходимости в дополнительных счетчиках и переменных, потому что все необходимые данные хранит структура “большого числа”.

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

Для измерения времени работы программы подключаем библиотеку 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

Функции, использующиеся в программе (проект Эйлера - 25 задача)

Функция, которая задает начальные значения числа

Поскольку при создании структуры начальные данные не инициализируются, потому создадим отдельную функцию для этого.

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

Функция, которая получает количество цифр в числе

Функция “отрезает “от числа младший разряд до тех пор, пока число “не кончится”. Количество разрядов в итоге и возвращается как длина числа.

По сути ее короткий код можно было просто включить в другие функции. Однако, руководствуясь принципом DRY “не повторяй себя дважды”, все-таки вынес ее, чтобы не дублироваться.

Функция, которая получает следующее значение числа Фибоначчи

Функция принимает два “больших” числа и, по сути, просто складывает числа в двух массивах столбиком. При этом:

Результаты сложения двух чисел (prev + next) сохраняются в числе prev.
В ячейку массива сохраняется только часть результата сложения, меньшая 1000000000 (т.е. только 9 цифр числа).
Старший разряд, не влезший в ячейку, заносится в остаток и переносится на следующую ячейку.
В итоге, при сложении двух чисел, например F₃ = F₁ + F2, результат сложения (F₃) заносится в F₁и, по сути, остаются два числа F2 и F₃.

После завершения сложения чисел:

Вычисляется и обновляется длина числа prev (F₁).
Меняется индекс числа prev (F1 -> F₃).
Меняются очередности чисел:
F2 (next -> prev)
F3 (prev -> next)

Также в функции контролируется правильность порядка задания аргументов функции (next и prev), а также выход числа за пределы массива.

Функция, которая определяет превышение переменной своего предельного значения и выводит предупреждение

Как ясно из названия, функция сравнивает два значения.

Если контролируемое значение превысит свой предел, то функция вернет true и выведет предупреждение.

Иначе вернет false.

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

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

В итоге ответ на 25 задачу проекта Эйлера составил 4782, программа считает ответ практически мгновенно – за 5 миллисекунд.

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

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

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

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

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