当f(0)=c时，f(n)=(1-f(n-1))*c+f(n-1)的递归解是什么?

该公式不像斐波那契数列，因为它只依赖于前一个结果，而斐波那契数列依赖于前两个项。

首先，你应该转换方程，使前一项只出现一次，而不是两次。这是给定的:

𝑓<子>𝑛=(1−𝑓<子>𝑛−1)𝑐+𝑓<子>𝑛−1

但这可以重写为:

𝑓<子>𝑛=(1−𝑐)𝑓<子>𝑛−1+𝑐

现在让我们分析一下这个公式是如何展开的，从基本情况开始:

𝑓₀=𝑐

𝑓<子>= 1(1−𝑐)𝑓<子>0+𝑐
         = ( 1−𝑐)𝑐+𝑐

𝑓<子>2子>1+𝑐
         = ( 1−𝑐)[(1−𝑐)𝑐+𝑐]+𝑐
         = ( 1−𝑐)<一口>2>

𝑓<子>3=(1−𝑐)𝑓<子>2+𝑐
         = ( 1−𝑐)[(1−𝑐)<一口>2>         = ( 1−𝑐)<一口>3𝑐+(1−𝑐)<一口>2>

    ...

𝑓<子>𝑛子><子>𝑘= 0 . .𝑛(1−𝑐)<一口>k𝑐
         = 𝑐∑<子><子>𝑘= 0 . .𝑛(1−𝑐)<一口>k

这个和是一个几何级数，所以我们可以写:

𝑓<子>𝑛子>𝑛+ 1>         = 1−(1−𝑐)<一口>𝑛+ 1

显然，这很容易编程为O(1)算法。

这种复杂性假定在所选的编程语言中，算术运算需要常数时间。但是，如果要使用任意大整数，则这些算术运算不需要常数时间。

f(n) = (1-f(n-1))*c + f(n-1)
= c - c*f(n-1) + f(n-1)
= c + (1-c)*f(n-1)

这不是指数的，它不类似于斐波那契级数。形式为:f(n) = a*f(n-1) + b

你可以直接实现这个，这将是线性时间(使O(n)调用函数f)。

或，你可以通过求解线性一阶递归关系，将方程简化为直接表达式，得到:

f(n) = 1 - (1-c)^n + c*(1-c)^n

可在O(1)

中计算

我只能给你递归代码。

c = 2 # You can use any number.
def algorithm(num):
if not num: return c #(returns c if num == 0
fminus1 = algorithm(num - 1)
return (1 - fminus1) * c + fminus1

这个递归式解为

f (n) = - (1 - c)<一口>n + 1>

为了了解原因，让我们首先注意到递归步骤可以重写为

f(n) = (1 - c)f(n - 1) + c.

这是一个线性异质递归关系。要解它，我们首先解相关方程

f(n) = (1 - c)f(n - 1)

得到通解f(n) = a(1 - c)ⁿ。

下一步，我们寻找一般递归式

的任意解

f(n) = (1 - c)f(n - 1) + c

，然后加进去。我们猜测答案的形式是s，因为这通常是这些东西的工作方式，然后解出方程

f (n) = (1 - c) f (n - 1) + c→s = (1 - c) (s) + c

这意味着

s = (1 - c)s + c

s - (1 - c)s = cS (1 - 1 + c) = c

cs = c

s = 1

所以解的一般形式是a(1 - c)ⁿ+ 1。求解边界条件f(0) = c得到

a(1 - c)⁰+ 1 = c

a + 1 = c

a = c - 1

所以递归式解为

f (n) = (c - 1) (1 - c)<一口>n>

或

f (n) = - (1 - c)<一口>n + 1>

让我们试一下。对于c = 0，得到f(n) = -1ⁿ+ 1 = 0，得到

• f(0) = 0
• f(1) = (1 - 0)f(0) + 0 = 0
• f(2) = (1 - 0)f(1) + 0 = 0
• …

c = 1,我们有f (n) = -(1 - 1)<一口>n>

• f(0) = 1
• f(1) = (1 - 1)f(0) + 1 = 1
• f(2) = (1 - 1)f(1) + 1 = 1
• …