-2

Можно ли сделать рекурсивно числа трибоначчи на питоне?

1

4 ответа 4

3
def tribonacci(n):
    if n in (1, 2):
        return 0
    if n in (3,):
        return 1
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)
6
  • вот смотри, если в tribonacci(n-1) подсунуть расчитанные tribonacci(n - 2), а в (n-2) уже будет расчитанно (n-3) - вот его и протащить вторым параметром до (n-1)
    – eri
    12 апр 2020 в 12:44
  • Нужно учитывать, что сложность вычисления быстро растёт и уже где-то 30-й элемент считается порядка 4 секунды. Так что для больших членов последовательности надо либо переписывать на не-рекурсивную версию, либо можно воспользоваться декоратором lru_cache из functools и тогда работает за микросекунды даже для очень больших номеров ряда.
    – CrazyElf
    12 апр 2020 в 12:47
  • если я ввожу print(tribonacci(0)) вылетает с ошибкой
    – Some_Body
    12 апр 2020 в 14:26
  • @eri Ясен пень не считать уже однажды считанное - и разумнее, и быстрее. Но задача учебная, и если у автора вопрос вообще возник - ему и такого решения за глаза хватит.
    – Akina
    12 апр 2020 в 17:12
  • @Some_Body если я ввожу print(tribonacci(0)) вылетает с ошибкой Текущий текст нумерует элементы, начиная с первого. Хотите с нулевого - уменьшите на единицу все границы у обоих IF-ов.
    – Akina
    12 апр 2020 в 17:14
1

В разы быстрее варианта @Akina, 70ый меньше чем за секунду

def tribonacci(n, n2=None, n3=None):
    if n in (1, 2):
        return 0
    if n in (3,):
        return 1

    n3 = n3 or tribonacci(n - 3)    
    n2 = n2 or tribonacci(n - 2, n3)

    return tribonacci(n - 1, n2, n3) + n2 + n3

tribonacci(70)

Но на кеше всеравно быстрее

import functools

@functools.lru_cache(maxsize=4)
def tribonacci(n):
    if n in (1, 2):
        return 0
    if n in (3,):
        return 1
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)

tribonacci(100)
2
  • Вообще это какое-то промежуточное решение. Либо полностью рекурсивно делать (и с кэшем, например, да), либо полностью не-рекурсивное решение делать. Так то, конечно, быстрее чем полностью рекурсивно, но ни туда ни сюда получается :)
    – CrazyElf
    12 апр 2020 в 13:23
  • это решение ещё остается рекурсивным)
    – eri
    12 апр 2020 в 13:25
0
  n=int(input())
  a=0
  b=0
  c=1
  while n>0:
    n-=1
    h=a+b+c
    a=b
    b=c
    c=h
  print(c-a-b)  
  print(a)
  print(b)
  print(c)
1
  • И что выдаст при n = 1? )
    – CrazyElf
    12 апр 2020 в 13:00
-2

Рекурсивное вычисление n-го числа ряда Фибоначчи

  1. Если n = 1 или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице.
  2. Во всех остальных случаях вызвать эту же функцию с аргументами n - 1 и n - 2. Результат двух вызовов сложить и вернуть в вызывающую ветку программы.
def fibonacci(n):
    if n in (1, 2):
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))

Допустим, n = 4. Тогда произойдет рекурсивный вызов fibonacci(3) и fibonacci(2). Второй вернет единицу, а первый приведет к еще двум вызовам функции: fibonacci(2) и fibonacci(1). Оба вызова вернут единицу, в сумме будет два. Таким образом, вызов fibonacci(3) возвращает число 2, которое суммируется с числом 1 от вызова fibonacci(2). Результат 3 возвращается в основную ветку программы. Четвертый элемент ряда Фибоначчи равен трем: 1 1 2 3.

0

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.