据估计，一个特定的社交网站每月的用户数量如下。找到以下算法的递归关系方程

F(n)= F(n-1)*120% + 100*n where F(0)=0

，这意味着每个月100新用户，因为广告和20％以上的用户，每月增加的添加，由于用户邀请的人的社交网络。在第一个月也没有用户。

不管怎么说，如果我们插上编号，这个递归，我们将得到：

F(0)=0 
F(1)=F(0)*1.2 + 100*1=100 
F(2)=F(1)*1.2 + 100*2=320 
F(3)=F(2)*1.2 + 100*3=684 
F(4)=F(3)*1.2 + 100*4=1220.8 
F(5)=F(4)*1.2 + 100*5=1964.96 
....

反正我有回答这个问题的第一部分。现在我被困在解决递归关系中。我需要找到一个解决复发关系的方程。换句话说，如果我在哪里传递数字2，那么它将输出320，而不必自己调用。

答案居然是： enter image description here

我不明白怎么去该解决方案。我从HERE得到了答案。我想了解如何解决它，而不仅仅是获得解决方案。

来源

2012-03-03 Tono Nam

数学观

代替1.2我将使用a并且代替100 I将使用b（！一个> 1，B = 0）：

F(n) = aF(n-1) + bn ==> 
F(n) = a (aF(n-2) + bn) + bn 
    = a^2 F(n-2) + ab(n-1)+bn 
    = a^3F(n-2) + a^2 * b * (n-2)+a*b*(n-1)+b*n=... 
    = a^n F(0) + a^(n-1) * b * (n-(n-1)) + .... + bn 
    = 0 + a^(n-1)* nb + a^(n-2)* (n-1)b + ... + a^0 *1*b - 
      [a^(n-1)* (n-1)b + a^(n-2) * (n-2)b + ... + 0)

如果我们写：

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

You ne编辑找到A-B。

然后

A = b (a^n + a^n-1 + a^n-2 + ....)' 
B = b/a * (a^(n-1)+....)' - a

，如果我们让C = a^n + a^n-1 + a^n-2 + ....我们知道C = (a^(n+1) - a)/(a - 1)，简单地就可以计算出C”，最后就可以计算出A和B以及它们的区别A - B。

算法和实际工作视图

但是，如果我想在算法方面讲，我很在乎O和Θ和Ω，......不是确切的运行时间。

所以，当我看到你的算法，我说这是Θ（一^ñ）没有任何计算，因为如果更换亿与1，它不会影响你的Θ符号，因为你的函数呈指数级增长，以便消除一些常量或多项式函数（不将它们转换为零）不会改变指数运行时间，它只是从最终结果中删除一些多项式函数。所以在这种情况下，我从来没有尝试过坚实的数学。我会用坚实的数学书写学术论文或考试，而不是在现实生活中。

来源

2012-03-03 18:22:14

-1

我希望我想出了我之前发布的解决方案。这是我已经制定出来的，我猜想，因为我得到了一个可以是正确解决方案的等式（非递归）。

enter image description here

来源

2012-03-03 18:12:19

F（N）= A * F（N-1）+ B * N

我们这里看起来像线性相加指数。

的想法是找到C和d这使得真以下等式：

F（N）+ C * N + d = A *（F（N-1）+ C *（N-1 ）+ d）

然后我们可以引入另一个函数：G（N）= F（N）+ C * N + d

G（N）= A * G（N-1）

G（n）= E * A^n（E可以从起始条件中找到）

F（n）= A^nC * nD

现在让我们实际上发现C和d：

B * N = A * C *（N-1）+ A * DC * ND =（A * CC）* N + A * DDA * C

B = C *（A-1） - 这会给我们C

0 = A * DDA * C - 这会给我们d（提供的C是已知的）

来源

2012-03-03 21:58:31 maxim1000

f(n)=af(n-1)+bn =a[af(n-2)+b(n-1)+b(n-1)]=a^2f(n-2)+(a+1)b(n-1) -ab

一般

f（n）= a^n * x + n * y + z

现在 F（1）= A * X + Y + Z = 1架 F（2）=（A^2）* X + 2Y + Z = F（3）= ...

我们可以单独使用这个线性系统来获得x，y，z

来源

2014-03-25 13:41:07 user1105089

找到以下算法的递归关系方程

回答

数学观

算法和实际工作视图

相关问题