算法 递归公式

Question

我正在阅读 Robert Sedgewick 的《C++ 算法》。 Basic recurrences section it was mentioned as 这种循环出现在循环输入以消除一个项目的递归程序中 Cn = cn-1 + N，对于 N >=2 且 C1 = 1。

Cn 大约是 Nsquare/2。计算和 1 + 2 +...+ N 是基本的。除此之外，还提到了以下声明。 "这个结果 - 寻求值(value)的两倍 - 由 N 项组成，每一项总和为 N +1

我需要帮助来理解上面的陈述，这里的 N 项是什么以及每一项的总和是多少N +1，以及“寻求值(value)的两倍”是什么意思。

谢谢你的帮助

Answer 1

我认为他引用了这个基本的数学技巧来计算那个总和。虽然，很难从您引用的这么短的段落中得出任何结论。

让我们假设 N = 100。例如，总和为 1 + 2 + 3 + .. + 99 + 100。
现在，让我们将总和为 101 的元素对分组:1 + 100、2 + 99、3 + 98 , ..., 50 + 51。这为我们提供了 50 (N/2) 对，每个对中有总和 101 (N + 1):因此总和为 50*101。

无论如何，你能为这句话提供更多背景信息吗？