Project Euler (answers)

Язык:

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

Проект Эйлера (2 задача) решаем, используя само определение ряда чисел Фибоначчи. Единственная хитрость – не вычислять одно и то же дважды.

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

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

Каждый следующий элемент ряда Фибоначчи получается при сложении двух предыдущих. Начиная с 1 и 2 первые 10 элементов будут:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Найдите сумму всех четных элементов ряда Фибоначчи, которые не превышают четыре миллиона.

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

Описание работы программы

Примечания

Используем операцию битового умножения в программе

Ответ на задачу Эйлера и скорость работы программы

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

Основные особенности алгоритма

Во-первых, нужно помнить, что согласно заданию и самому определению чисел Фибоначчи: “следующий элемент получается при сложении двух предыдущих” (fib_next = fib1 + fib2 в программе).
Во-вторых, четное число делится на 2 без остатка
Ну и главное, не нужно вычислять каждый элемент ряда каждый раз заново. Потому, как только будет получено число Фибоначчи, следующее за первыми двумя (fib_next = fib1 + fib2), значения обновляются.
fib1 <- fib2 // первое число принимает значение второго
fib2 <- fib_next // второе – третьего (суммы первых двух)
Такой цикл продолжается снова и снова до тех пор, пока в итоге не превысит искомые 4000000.

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

fib2 % 2 == 0

3 % 2 – возвращает остаток от целочисленного деления 3 на 2, т.е. 1
Если остаток от деления двух чисел равен нулю, то числа делятся нацело.
fib % 2 == 0 – сравнение на равенство, если остаток от деления равен нулю, то вернет true (истина), иначе – false (ложь)

if (! (fib % 2))

(fib % 2) – любое ненулевое число внутри оператора if() будет восприниматься как true (истина).
Условие будет срабатывать и будет работать код после if()
! – операция “не” инвертирует значение true в false и наоборот.
Таким образом if ( !(fib % 2) ) – сработает если остаток от деления будет равен нулю, следовательно числа делятся нацело

evens_summ += fib2

evens_summ += fib2 тоже самое что и evens_summ = evens_summ + fib2

Измеряем время работы программы - проект Эйлера (2 задача)

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

Используем операцию битового умножения в программе - проект Эйлера (2 задача)

Никогда не делайте так! Иначе получите все зачеты автоматом… еще и в Яндекс заберут, не дай бог))

Тут пугаться нечего, все три конструкции ниже работают одинаково:

!(fib2&1)
!(fib2%2)
fib2%2 == 0

Напомню, что в двоичной системе исчисления числа выглядят так:

1 -> 00000001
2 -> 00000010
9 -> 00001001
и так далее…

& – это операция битового умножения (“И“).

При нем каждый бит двух чисел сравнивается и возвращает 1 только если в обеих числах этот бит равен 1:

0 & 0 -> 0
1 & 0 -> 0
0 & 1 -> 0
1 & 1 -> 1

Побитовое умножение чисел 9 & 1 и 2 & 1 к примеру будет выглядеть так:

00001001 & 00000001 -> 00000001 (т.е. 1)
00000010 & 00000001 -> 00000000 (т.е. 0)

Еще раз. Работа конструкции !(fib2&1) основана на том, что все нечетные числа в двоичном виде имеют на конце 1, а четные – 0.

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

В итоге ответ на 2 задачу проекта Эйлера составил 4613732.

Программа работает мгновенно. Еще раз повторюсь, не следует вычислять одно и то же (да и делать что угодно) дважды.

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

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

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

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

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