Блог

Главная - Вопросы по программированию - Нахождение суммы чисел Фибоначчи меньше n

Нахождение суммы чисел Фибоначчи меньше n

#python-3.x #fibonacci

#python-3.x #фибоначчи

Вопрос:

Я должен найти сумму всех чисел Фибоначчи перед значением n. Итак, последнее значение Фибоначчи, которое я получаю, меньше или равно n . Например, sum_of_fibonacci (10) будет 0 1 1 2 3 5 8 начиная с 8<10. У меня возникли проблемы с ограничением последовательности Фибоначчи до остановки до того, как она пройдет n. Куда мне идти дальше?

 sum_of_fibonacci(n):
    def fib(n):    
        if n == 0 or n == 1:
            return n
        else:
            return fib(n-1)   fib(n-2)

Комментарии:

1. Рассматривали ли вы переключение range(n) и sum возвращаемые значения из вашей fib функции?

2. для fib (4) вы хотите остановиться, 0 1 1 2 3 а для fib (7) вы хотите остановиться 0 1 1 2 3 5 ? Это ваша проблема? В первом случае 3 < 4 < 5 и вы хотите остановиться на 3 и для второго 5 < 7 < 8 , поэтому вы хотите, чтобы это остановилось на 5 ?

Ответ №1:

Вы можете сделать это, сохранив все числа Фибоначчи, которые меньше n, в списке, а затем вернуть его сумму

 def sum_of_fibonacci(n):
    if n == 0 : return 0
    fib = [0, 1]   #initializing the list of Fibonacci numbers
    i = 2   #position of next_fib
    next_fib = 1
    while next_fib <n :
        fib.append(next_fib)
        i  = 1
        next_fib = fib[i-1]   fib[i-2]
    return sum(fib)
print(sum_of_fibonacci(10))
# 20

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

 MAX_RANGE = 10000   #we'll consider the first 10000 Fibonacci numbers
fib = [0, 1]
for i in range(2, MAX_RANGE):
    fib.append((fib[i-1]   fib[i-2]))
def sum_of_fibonacci(n):
    if n == 0 : return 0
    return sum([f for f in fib if f<n])
Q = int(input())   #input the number of test cases
for i in range(Q):
    to = int(input())   #input each test case
    print(sum_of_fibonacci(to))
# input : 2
# input : 10
# output : 20
# input : 100
# output : 232

При использовании последнего метода при поиске sum_of_fibonacci из Q тестовых примеров сложность была бы O (Q * n MAX_RANGE) над O (Q * n ^ 2) с первым

Ответ №2:

Обновил мой ответ на основе этого варианта использования: For example sum_of_fibonacci(10) would be 0 1 1 2 3 5 8 since 8<10

Вы можете попробовать создать простой цикл и распечатать значения. Я не думаю, что вам нужен массив.

Вот решение, оптимизированное для пространства. Вы можете найти другие более быстрые решения.

 def sum_of_fib(n):
    a = 0
    b = 1
    if n < 0:
        print ('Incorrect input')
    elif n in (0,1): return n
    else:
        s = 0
        while b <= n:
            s  = b
            a,b = b,a b
        return s

print ('sum of fib till 0:',sum_of_fib(0))
print ('sum of fib till 1:',sum_of_fib(1))
print ('sum of fib till 2:',sum_of_fib(2))
print ('sum of fib till 3:',sum_of_fib(3))
print ('sum of fib till 4:',sum_of_fib(4))
print ('sum of fib till 5:',sum_of_fib(5))
print ('sum of fib till 6:',sum_of_fib(6))
print ('sum of fib till 7:',sum_of_fib(7))
print ('sum of fib till 8:',sum_of_fib(8))
print ('sum of fib till 9:',sum_of_fib(9))
print ('sum of fib till 10:',sum_of_fib(10))

Вывод:

 sum of fib till 0: 0
sum of fib till 1: 1
sum of fib till 2: 4
sum of fib till 3: 7
sum of fib till 4: 7
sum of fib till 5: 12
sum of fib till 6: 12
sum of fib till 7: 12
sum of fib till 8: 20
sum of fib till 9: 20
sum of fib till 10: 20