Fibbonaci-подобная последовательность последних 3 чисел

Question

Есть ли нерекурсивный способ, которым я могу сделать последовательность, подобную Фибоначчи, добавив последние 3 числа?

Вот рекурсивный способ, которым я пытался это сделать.

def fib3(n):
    if n < 3:
        return 1
    else:
        return fib3(n-1) + fib3(n-2) + fib3(n-3)

возвращается 1+1+1+3+5+9+17...+(n-1) + (n-2) + (n-3)

Любая помощь будет оценена.

заранее спасибо

Answer 1

Да, и довольно элегантно, с возможностью множественного назначения Python:

>>> def fib3(n):
...     if n < 3:
...         return 1
...     a = b = c = 1
...     for i in range(3, n):
...         # We "shift" a, b, and c to the next values of the sequence.
...         a, b, c = b, c, (a + b + c)
...     return c
...
>>> fib3(4)
3
>>> fib3(5)
5
>>> fib3(6)
9
>>> fib3(7)
17

И итерационный метод определенно предпочтительнее рекурсивного метода - как пишет @mu, время выполнения рекурсивной реализации составляет примерно O(3^n), тогда как этот метод - O(n).

Answer 2

fib_sum для вычисления m последнего целого числа:

>>> def fib_sum(n,m):
        if n < m:
            return "n should be greater than m"
        a,b,sumit = 0,1,0
        for x in range(n):
            print b,
            if x >= n-m:
                sumit += b
            a,b = b,a+b
        return sumit

>>> fib_sum(3,4)
'n should be greater than m'
>>> fib_sum(3,2)
1 1 2
3
>>> fib_sum(3,1)
1 1 2
2
>>> fib_sum(2,1)
1 1
1
>>> fib_sum(2,2)
1 1 
2
>>> fib_sum(7,2)
1 1 2 3 5 8 13
21
>>> fib_sum(7,3)
1 1 2 3 5 8 13
26
>>> fib_sum(8,6)
1 1 2 3 5 8 13 21
52
>>> fib_sum(8,8)
1 1 2 3 5 8 13 21
54

Answer 3

Я опоздал на вечеринку, но: можно легко вывести формулу для получения n-го элемента любого линейного повторения, такого как последовательность Фибоначчи или его обобщение, без необходимости вычисления всех промежуточных элементов. Скажем, ваш рецидив: f[n] = a[1] f[n - 1] + a[2] f[n - 2] + ... + a[m] f[n - m]. Предположим, что f[n] = (некоторая константа)^n. (Это своего рода гипотеза "счастливой догадки", которая часто появляется в решениях для дифференциальных уравнений. Я не знаю, как это обосновать априори. Это можно оправдать после факта, фактически найдя такую ​​константу.) Тогда константа должен быть корнем многочлена x^m - a[1] x^(m - 1) - a[2] x^(m - 2) - ... - a[m]. Любая линейная комбинация решений также должна быть решением. Вы можете найти коэффициенты c [1],..., c [m] для линейной комбинации, решая линейную систему, полученную из первых значений m (очевидно, что значение всех более поздних значений в последовательности определяется первым м значения).

Для заданного повторения f[n] = f[n - 1] + f[n - 2] + f[n - 3] имеем [1] = a[2] = a[3] = 1 и корни x^3 - x^2 - x - 1 составляют - 0,6063 %i - 0,4196, 0,6063 %i - 0,4196, 1,839 соответственно. Дано, что первые 3 значения равны 1, 1, 1. Решение c[1] + c[2] + c[3] = 1, c[1] a[1] + c[2] a[2] + c[3] a[3] = 1, c[1] a[1]^2 + c[2] a[2]^2 + c[3] a[3]^2 = 1 для c [1 ], c [2], c [3] дает 0,3592 %i + 0,2822, 0,2822 - 0,3592 %i, 0,4356 соответственно. (Я написал их как приближенные числа с плавающей точкой. Как корни многочленов с рациональными коэффициентами, это алгебраические числа, но точные выражения могут легко стать грязными.)

Таким образом, f[n] = c[1] a[1]^n + c[2] a[2]^n + c[3] a[3]^n, с указанными значениями для a и c, является функцией, которая дает n-й элемент рекуррентности f[n] = f[n - 1] + f[n - 2] + f[n - 3], причем f[2] = f[1] = f[0] = 1.

Я рассчитал а и с в Максима. Я могу сказать больше о том, как я это сделал, если есть интерес.