如何计算斐波那契函数的累积调用次数？

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_calln = 8print(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), total_call

当是 3 时，它尝试“添加”斐波那契（2），元组，和斐波那契（1），整数。这不是一项合法的行动。您需要正则化返回值。你不能神奇地只返回值（而不是计数），而这正是你想要的;你必须明确地编程差异：肢解元组并添加组件值。n1

从您的基本案例开始

return 1, 0

递归情况需要添加组件。实施留给学生练习。