开放形式和封闭形式

Question

如何将开放形式的再发生转换为其等效封闭形式。 此外，通常有效使用的一些常用封闭表格是 。

Answer 1

我想你是在谈论递归函数和数学。

例如考虑以下总和递归函数

sum(0) = 0 
sum(i) = sum(i-1) + i 

此表单未关闭。一个封闭的表格是sum(n) = (n+1)*n/2，其中您只使用基本操作，如+ - * /，功率，有时是阶乘。

对于您的问题，如何将开放式公式转换为封闭形式。答案是没有一般规则将所有开放形式转换为封闭形式，因为一些开放形式没有等价的封闭形式。

你可以参考Concrete Mathematics对这个问题的严肃处理。本书的主要目标是将大量递归函数/开放表单转换为封闭表单。

Answer 2

一个开放的形式通常是作为一个方程来解决。例如，

a(0) = 1   -- base case 
a(n) = b * a(n-1) -- recurrence relation 

要将其转换成封闭形式，你解决递推关系。在这种情况下，重复进行置换，直至到达基准情况给你

a(n) = b * a(n-1) = b * b + a(n-2) = ... = b * b * ... * b * a(0) = b^n 

这是更有效的，因为功率可以在对数时间来评价在Ñ（即正比于登录Ñ）而原始递归关系在n需要时间线性。

有许多技术用于解决复发关系。一些示例可以在wikipedia article中找到。但重要的是要认识到并非所有的复发关系都可以解决，但实际上大多数解决不了（这就是编程很重要的原因！）