算法递归公式

Question

我正在阅读Robert Sedgewick在C++中的算法。它被提及作为本复发基本复发部产生用于通过输入回路，以消除一个项目 CN = CN-1 + N，对于N> = 2与C 1的递归程序= 1

Cn为约Nsquare/2。评估总和1 + 2 + ... + N是基本的。除此之外还提到以下声明。 “这个结果 - 两倍的价值追求 - 包括N项，其中每个总计为N + 1

我需要了解abouve声明的帮助是什么在这里N项以及如何各款项 N + 1，ASLO什么是“两倍的价值追求”的意思。

感谢您的帮助

Answer 1

我想他指的是这个基本的数学技巧来计算总和。虽然，我们很难断定，你举这么短的通道东西。我们假设N = 100。E .g。，总和是1 + 2 + 3 + .. + 99 + 100。
现在，让我们将总和对101：1 + 100,2 + 99, 3 + 98，...，50 + 51。这给了我们50（N/2）对与每个总和101（N + 1）：因此，总金额为50*101。

无论如何，你能否提供更多的上下文来引用？

Answer 2

的递推公式表示：

C1 = 1 
C2 = C1 + 2 = 1 + 2 = 3 
C3 = C2 + 3 = 3 + 3 = 6 
C4 = C3 + 4 = 6 + 4 = 10 
C5 = C4 + 5 = 10 + 5 = 15 
etc. 

但是也可以直接把它写： C5 = 1 + 2 + 3 + 4 + 5 = 15

然后使用旧的特技：

1 + 2 + 3 + ... + N 
+ N + N-1 + N-2 + ... + 1 
------------------------- 
(N+1) ...    (N+1) 

=（N + 1）* N

从那里，我们得到：1 + 2 + ... N = N *（N + 1）/ 2

对于轶事，上述式是由大数学家卡尔·弗里德里希高斯，当他在学校找到。

从那里，我们可以推导出一个递归算法是O（N方）和那也许正是罗伯特·塞奇威克做。