0

我偶然发现了这个函数来计算加泰罗尼亚语数：

def catalan(n):
    if n == 0:
        return 1
    else:
        sum = 0
        for i in range (n):
            sum +=(catalan(i))*(catalan(n-1-i))
    return sum

我的问题是如何sum获取值，例如 n=2：

sum = (catalan(0))*(catalan(2-1-0)) + (catalan(1))*(catalan(2-1-1) + (catalan(2))*(catalan(2-1-2))

catalan(2-1-0)如果我们n=1只为

4

1 回答 1

2

笔和纸评估

加泰罗尼亚语 (0)

# 1

加泰罗尼亚语 (1)

#  = 0 + catalan (0) * catalan (1-1-0)
#  = 0 + 1 * catalan (0)
#  = 0 + 1 * 1
#  = 0 + 1

加泰罗尼亚语 (2)

#  = 0
#  + catalan (0) * catalan (2-1-0)
#  + catalan (1) * catalan (2-1-1)

#  = 0 
#  + 1 * catalan (1) 
#  + 1 * catalan (0)

#  = 0
#  + 1 * 1
#  + 1 * 1

#  = 1
#  + 1

#  = 2

加泰罗尼亚语 (3)

#  = 0
#  + catalan (0) * catalan (3-1-0)
#  + catalan (1) * catalan (3-1-1)
#  + catalan (2) * catalan (3-1-2)

#  = 0
#  + 1 * catalan (2) 
#  + 1 * catalan (1)
#  + 2 * catalan (0)

#  = 0
#  + 1 * 2
#  + 1 * 1
#  + 2 * 1

#  = 0
#  + 2
#  + 1
#  + 2

#  = 5

浪费的周期

让我们看一个朴素的斐波那契过程——</p> 

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

这个过程作为一个典型的树递归很有指导意义，但它是计算斐波那契数的一种糟糕的方法，因为它做了很多冗余计算。请注意下面的整个计算fib(3)，几乎一半的工作，是重复的。事实上，不难证明该过程将计算的次数fib(1)或fib(0)（通常是上述树中的叶子数）是fib(n + 1). 为了了解这有多糟糕，可以证明 的值fib(n)随着SICP n -  Tree Recursion呈指数增长

浪费的斐波那契

你的程序也发生了类似的问题catalan，但程度更糟。呼叫catalan(3)将产生六(6) 个额外catalan呼叫

# catalan (3)
#  = 0
#  + catalan (0) * catalan (3-1-0)
#  + catalan (1) * catalan (3-1-1)
#  + catalan (2) * catalan (3-1-2)
#  ...
#  = 5

有多种技术可以避免这个问题。请按照上面的引文获取有关该主题的更多帮助。

于 2019-01-02T17:55:33.637 回答