@FandH

Что думаете об этом решении задачи?

Решил я заняться выполнением задач проекта эйлера. И на второй задаче я встал в ступор,
так как сразу откинул решение с перечислением всех чисел фибоначчи.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
Смотря на последовательность, я понял что каждое четное число можно вычислить.
Четное число фибоначчи равно сумме предыдущего четного числа последовательности умноженного на 4
и запредыдущего четного числа:
34 = 8 * 4 + 2
144 = 34 * 4 + 8
Исходя из этого я значительно ускорил скорость работы скрипта, так как мне перестало быть нужным перечислять
нечётные числа. Сам скрипт:
# n и b - это первые четные 2 числа фибоначчи
n = 2
b = 8
sum_of_numbers = 0

while True:
    # Здесь я задаю меньшей переменной значение следующего числа
    if n < b:
        n = 4 * max(n, b) + min(n, b)
    else:
        b = 4 * max(n, b) + min(n, b)

    sum_of_numbers += max(n, b)
    if max(n, b) >= 4000000:
        break

# Прибавляю 10, так как изначально опустил первые 2 четных значения, и минусую последнее четное число,
# так как оно больше 4000000
print((sum_of_numbers + 10) - max(n, b))
  • Вопрос задан
  • 114 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Это ваше тождество хорошо бы доказать.

Но, так-то там числа фиббоначи, не превышающие 4000000. Их таких дай бог 100. Там можно их все считать по несколько раз- вы разницу скорости работы скрипта не измерите никак.

Что касается кода: ваш разбор случаев, что там больше - весьма странен. Код тяжело читать и он в несколько раз медленее, чем мог бы быть из-за постоянных вызовов максимума и минимума. Может даже медленнее простого вычисления чисел фиббоначи без пропусков нечетных.

Заведите вы третью временную переменную и считайте через нее, чтобы в цикле всегда n было большим числом (m = 4*n+b; b=n; n=m). Или вообще воспользуйтесь фишками питона и делайте множественное присвоение:
b, n = n, 4*n+b;
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Rhonda Software Владивосток
от 60 000 до 120 000 ₽
ModuleWorks Симферополь
от 600 до 2 000 €
PrimatLab LLC Таганрог
от 90 000 до 120 000 ₽
28 нояб. 2021, в 10:02
7000 руб./за проект
28 нояб. 2021, в 09:33
15000 руб./за проект