И снова я ознакомился с задачей, которую решил автор канала
Задача
Каждый следующий элемент ряда Фибоначчи получается при сложении двух предыдущих. Начиная с 1 и 2 первые 10 элементов будут:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Найдите сумму всех чётных элементов ряда Фибоначчи, которые не превышают четыре миллиона.
Решение
Автор снова выбрал накопление суммы в цикле:
Это логично. Ряд чисел Фибоначчи рассчитывается исходя из текущего и предыдущего элемента, заодно они проверяются на чётность и складываются.
Я не увидел никакого принципиально иного решения, кроме того, что на чётность можно не проверять. Для этого нужно только заметить закономерность, что чётные (Ч) и нечётные (Н) числа идут в таком порядке:
Н-Н-Ч-Н-Н-Ч-Н-Н-Ч-...
Докажем, что данный порядок (два нечётных и чётное) сохраняется всегда.
Первые числа Фибоначчи это 1 и 2, то есть мы начинаем с наименьшего чётного числа 2. Перед ним стоит нечётное. Значит, следующее будет суммой чётного и нечётного, что всегда даст нечётное (1 + 2 = 3). Следующее после него опять будет суммой чётного и нечётного и опять даст нечётное (2 + 3 = 5). Наконец, следующее будет суммой двух нечётных и всегда даст чётное (3 + 5 = 8). И мы пришли к начальному состоянию "нечётное-чётное", которое будет повторяться вечно.
Стало быть, не нужно в цикле ждать, пока мы дойдём до очередного чётного числа. Нужно сразу прыгнуть к нему.
Назовём текущее чётное число fibo, а предыдyщее в ряду – prev.
Следующее число: fibo + prev
Следующее число: fibo + fibo + prev
Cледующее число: fibo + fibo + fibo + prev + prev
Получаем формулу: следующее чётное число равно fibo * 3 + prev * 2.
Перепишем цикл:
Сложность задачи не изменилась, она по-прежнему O(N), но всё-таки шагов цикла и условий стало меньше, что будет оказывать положительное влияние.
Ссылка на онлайн-компилятор языка C с текстом программы:
https://onlinegdb.com/tcsgFf3et
Возможна ли оптимизация?
Конечно, смысл задачи в том, чтобы сделать её самостоятельно, поэтому другие решения я стал искать уже после своего. Я спросил у железного болва друга ChatGPT, что он знает про ряды Фибоначчи. Он предложил формулу одномоментного получения суммы для любого N, но там есть нюанс.
Получение N-го элемента делается через возведение матрицы в степень, что математически выглядит как одна операция, но на деле является серией умножений матриц, так что цикл там всё равно присутствует, плюс сами операции с матрицами тяжёлые. Правда, сложность получения элемента уже O(log2 N), что сулит некие выгоды на очень больших N.
Но увы, таким способом можно получить только сумму всех элементов. Чтобы выбрать только чётные, всё равно нужен цикл. Либо ещё какая-то хитрая математика.
Меня же заинтересовало представление последовательности чисел в виде матрицы, но я его пока не понял. Когда пойму, то попробую об этом написать.
Вся подборка задач: