如何分析這個僞

Question

我有以下的僞代碼：

sum<-0 
inc<-0 
for i from 1-n 
    for j from 1 to i 
    sum<-sum+inc 
    inc<-inc+1 

問我找到一個封閉的公式。暗示是使用共同的總結。無論我如何看待它，我都無法以總結形式編寫此代碼。有人能給我一個總結看起來像甚麼遞歸公式的概念嗎？

Answer 1

假設for i from 1-n指：

for i from 1 to n 

甲關閉公式，可以通過一些數值分析來獲得。讓我們來看看通過循環的次數n（5和6）。

外環總是n倍和內環是任何i是對於每次迭代，因此對於n值，這裏是迭代計數：

n count 
= =========================================== 
1 (1)         = 1 
2 (1),(12)        = 3 
3 (1),(12),(123)       = 6 
4 (1),(12),(123),(1234)     = 10 
5 (1),(12),(123),(1234),(12345)   = 15 
6 (1),(12),(123),(1234),(12345),(123456) = 21 

這些封閉的公式最佳地示出如下：

n = 5: 5 + 4 + 3 + 2 + 1 
     | | | | | 
     | | V | | 
     | | 3 | | Formula is: (n+1)*((n-1)/2) + ((n+1)/2) 
     | +-> 6 <-+ |    [outer pair sets] + [inner value] 
     +-----> 6 <-----+ 
       -- 
       15 

這對於n所有奇數值的公式。對於偶數值，可以使用類似的方法：

n = 6: 6 + 5 + 4 + 3 + 2 + 1 
     | | |  | | | 
     | | +-> 7 <-+ | | Formula is: (n+1)*(n/2) 
     | +-----> 7 <-----+ |   [outer pair sets] 
     +---------> 7 <---------+ 
        -- 
        21 

這告訴你的n每個值的嵌套循環迭代的次數（我們稱之爲x）。

sum的最終值的計算非常相似。在第一次迭代中，您添加零。在第二次迭代中，您添加一個。在第三次迭代中，您添加兩個。這幾乎是正是你不得不做找出迭代次數同樣的事情，只是現在它是基於x而不是n和它的0+1+2+...而非1+2+3+...，這意味着我們可以使用完全相同的公式只是通過它應用到x-1，而比x。

所以我們可以使用：

if n is odd: 
    x <- (n+1) * ((n-1)/2) + ((n+1)/2) 
else: 
    x <- (n+1) * (n/2) 
x <- x - 1 
if x is odd: 
    sum <- (x+1) * ((x-1)/2) + ((x+1)/2) 
else: 
    sum <- (x+1) * (x/2) 

上n選中此對算法的前幾個值：

n algorithm formula 
- --------- ------- 
0  0   0 
1  0   0 
2  3   3 
3  15  15 
4  45  45 
5  105  105 

所以，絕配，至少withing選擇的樣本空間。實際上，你可以進一步將其轉化爲基於n的單一公式，而不是計算出中間值，但我會將其作爲練習給讀者。

---

提示：AC公式，同時適用於奇數和偶數號碼是：

x <- ((n+1) * ((n-(n%2))/2)) + ((n%2) * ((n+1)/2)) 

（雖然還沒有測試過的n負值 - 你應該把支票您使用前公式版本）。

Answer 2

最內層的循環（我們就叫i一個固定的號碼）：

inc遞增i倍。
sum已將inc加到它上面i次。 （i *（i-1）/ 2，對嗎？）

如果我們假設inc和sum開始藝術值0，那麼這是有效的。如果我們假定它們以不同的值開始，我們稱它們爲k和l，那麼我們知道inc將以值k+i結束。我們知道sum將最終在l+k*i + i*(i-1)/2。

現在，i本身會從1到n。呃...哼。讓我多想一想。