算法遞歸公式

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方）和那也許正是羅伯特·塞奇威克做。