Как посчитать совокупные вызовы функции Фибоначчи?

Question

Я пытался:

def fibonnaci(n):
        total_call = 0
        if n ==0 or n == 1:
            return 1
        else:
            if n== 2 or n == 1:
                total_call +=0
            else:
                total_call +=2

            return fibonnaci(n - 1) + fibonnaci(n - 2), total_call


n = 8
print(fibonnaci(n))

, но я получил ошибку:

TypeError: can only concatenate tuple (not "int") to tuple

Как отобразить количество вызовов для Фибоначчи?

Answer 1

Использование декораторов

1. Использование атрибутов функций

Ссылка

Код

def call_counter(func):
    " Does the call count for any function "
    def helper(x):
        helper.calls += 1
        return func(x)
    helper.calls = 0
    return helper

@call_counter
def fib(n):
  if n ==0 or n == 1:
    return 1
  return fib(n - 1) + fib(n - 2)

Использование

fib(5)
print(fib.calls)

fib(10)

print(fib.calls)  # Keeps running total so will be from previous 
                  # fib(5) plus current fib(10)

# To reset counter
fib.calls = 0

Использование класса

Ссылка

Код

class countCalls(object):
    """Decorator that keeps track of the number of times a function is called.
    ::

        >>> @countCalls
        ... def foo():
        ...     return "spam"
        ... 
        >>> for _ in range(10)
        ...     foo()
        ... 
        >>> foo.count()
        10
        >>> countCalls.counts()
        {'foo': 10}

    Found in the Pythod Decorator Library from http://wiki.python.org/moin web site.
    """

    instances = {}

    def __init__(self, func):
        self.func = func
        self.numcalls = 0
        countCalls.instances[func] = self

    def __call__(self, *args, **kwargs):
        self.numcalls += 1
        return self.func(*args, **kwargs)

    def count(self):
        "Return the number of times this function was called."
        return countCalls.instances[self.func].numcalls

    @staticmethod
    def counts():
        "Return a dict of {function: # of calls} for all registered functions."
        return dict([(func.__name__, countCalls.instances[func].numcalls) for func in countCalls.instances])


@countCalls
def fib(n):
  if n ==0 or n == 1:
    return 1
  return fib(n - 1) + fib(n - 2)

Пример

print(fib(3))      # Output 3
print(fib.count()) # Output 5

Преимущество

Позволяет получить количество всех зарегистрированных функций (т.е. зарегистрированных с помощью декоратора)

@countCalls
def f(n):
  pass  # dummy function

@countCalls
def g(n):
  pass  # dummy function

for i in range(5):
  f(i)

for i in range(10):
  g(i)

print(countCalls.counts())

# Outputs: {'f': 5, 'g': 10}

Answer 2

def fib(n):

    if n <= 1:
        return n, 1
    fib_one = fib(n - 1)
    fib_two = fib(n - 2)
    #Return the result and the number of function calls (+ 1 for the current call)
    return fib_one[0] + fib_two[0], fib_one[1] + fib_two[1] + 1




if __name__ == '__main__':
    number_of_function_calls = fib(4)[1]

Fib (4) должен вернуть 9, что он делает

                      fib(4)  
              fib(3)            fib(2)
          fib(2)   fib(1)   fib(1)     fib(0)
      fib(1)  fib(0)

Answer 3

В вашем операторе return результатом обоих fibonnaci(n - 1) и fibonnaci(n - 2) может быть кортеж (argument > 1) или одно целое число (argument <= 1), таким образом, + означает конкатенацию, когда первый кортеж Но когда n == 3 in return fibonacci(n - 1) + fibonacci(n - 2), total_call fibonacci(2) является кортежем ((2, total_call)), а fibonacci(1) является целым числом (1). Итак, вы хотите объединить кортеж с целым числом, что невозможно.

Answer 4

Проблема «очевидна», если вы пытаетесь отследить значения, которые вы используете:

        return fibonnaci(n - 1) + fibonnaci(n - 2), total_call

Когда n равно 3, это попытается «добавить» fibonnaci (2), a кортеж и fibonnaci (1), целое число 1. Это не законная операция. Вы должны упорядочить ваши возвращаемые значения. Вы не можете волшебным образом вернуть значение в одиночку (не в счет), когда это то, что вы хотите; Вы должны явно запрограммировать разницу: расчленить кортеж и добавить значения компонентов.

Начните с базового варианта:

return 1, 0

В вашем рекурсивном случае необходимо добавить компоненты. Внедрение оставлено s упражнение для студента.

Answer 5

Вот еще один ответ с использованием декоратора. Преимущество использования декоратора состоит в том, что базовая функция fib не нуждается в изменении. Это означает, что код total_count и несколько возвращаемых значений могут быть отброшены с вашей первоначальной попытки -

@counter(model = fib_result)
def fib(n = 0):
  if n < 2:
    return n
  else:
    return fib(n - 1) + fib(n - 2)

Наш декоратор counter принимает model, чтобы мы могли реагировать на поведение декорированной функции. Наш украшенный fib вернет fib_result, например { result: ?, count: ? }. Это означает, что нам также необходимо обработать fib(?) + fib(?), поэтому мы также определили __add__ -

class fib_result:
  def __init__(self, result, count = 0):
    if isinstance(result, fib_result):
      self.result = result.result
      self.count = result.count + count
    else:
      self.result = result
      self.count = count
  def __add__(a, b):
    return fib_result(a.result + b.result, a.count + b.count)

Как видите, этот fib_result указывает c на подсчет fib вызовов. Для подсчета других рекурсивных функций, которые возвращают результаты других типов, может потребоваться другая модель.

Теперь осталось только определить наш обобщенный c counter декоратор. Наш декоратор принимает аргументы и возвращает новый декоратор lambda f: ..., который просто захватывает переданные аргументы lambda *args: ... и создает новый model с результатом f(*args) и базовым счетом 1 -

def counter(model = tuple):
  return lambda f: lambda *args: model(f(*args), 1)

Вот как работает вся программа -

r = fib(4)
print(f"answer: {r.result}, recurs: {r.count}")
# answer: 3, recurs: 9

r = fib(10)
print(f"answer: {r.result}, recurs: {r.count}")
# answer: 55, recurs: 177