與嵌套循環相關的拼圖

Question

對於給定的輸入N，封閉語句執行多少次？

for i in 1 … N loop 
    for j in 1 … i loop 
    for k in 1 … j loop 
     sum = sum + i ; 
    end loop; 
    end loop; 
end loop; 

任何人都可以找出一個簡單的方法或公式來做到這一點。請解釋。

Answer 1

• 首先，我寫了一個C代碼來生成和：

int main(){ 
    int i =0, k =0, j =0, n =0; 
    int N =0; 
    int sum =0; 
    N =10; 
    for (n=1; n <= N; n++){ 
    // unindented code here 
    sum =0; 
    for (i=1; i<=n; i++) 
     for (j=1; j<=i; j++) 
      for (k=1; k<=j; k++) 
       sum++; 

    printf("\n N=%d sum = %d",n, sum); 
    } 
    printf("\n"); 
} 

• 簡單的編譯和生成N=1 to N=10結果：

$ gcc sum.c
$ ./a.out

N=1 sum = 1 
N=2 sum = 4 
N=3 sum = 10 
N=4 sum = 20 
N=5 sum = 35 
N=6 sum = 56 
N=7 sum = 84 
N=8 sum = 120 
N=9 sum = 165 
N=10 sum = 220 

• 然後，在努力探索How this works?一些圖：

  對於，N=1：

i<=N,  (i=1)  
      | 
j<=i,  (j=1)  
      | 
k<=j,  (K=1)  
      | 
sum=0. sum++  ---> sum = 1 

即（1）= 1

對於，N=2：

i<=N,  (i=1)-------(i=2) 
      |  |-----|-----| 
j<=i,  (j=1) (j=1)  (j=2) 
      |  |  |----|----| 
k<=j,  (K=1) (K=1) (K=1) (K=2)    
      |  |  |  |  
sum=0, sum++ sum++ sum++ sum++ --> sum = 4 

即（1）+（1 + 2）= 4

對於，N=3：

i<=N,  (i=1)-------(i=2)--------------------(i=3) 
      |  |-----|-----|  |---------|-------------| 
j<=i,  (j=1) (j=1)  (j=2)  (j=1)  (j=2)  (j=3) 
      |  |  |----|----| |  |----|----| |-----|-----| 
k<=j,  (K=1) (K=1) (K=1) (K=2) (K=1) (K=1) (K=2) (K=1) (K=2) (K=3) 
      |  |  |  |  |  |  |  |  |  | 
sum=0, sum++ sum++ sum++ sum++ sum++ sum++ sum++ sum++ sum++ sum++ 
      --> sum = 10 

即（1）+（1 + 2）+（1 + 2 + 3）= 10

N = 1, (1) = 1           

N = 2, (1) + (1 + 2) = 4 

N = 3, (1) + (1 + 2) + (1 + 2 + 3) = 10 

N = 4, (1) + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) = 20 

N = 5, (1) + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4 + 5) = 35 

最後，我可以理解的N該總和在三個循環爲：

（1 ）+（總和0f 1至2）+ ... +（1至（N-2）之和）+（1至（N-1）之和）+（1至N之和）

或我們可以寫成：

=>（1）+（1 + 2）+ ... +（1 + 2 + ... + i）+ ... +（1 + 2 + .. ... + N-1）+（1 + 2 + ... + N）（N * 1）+（（N-1）* 2）+（（N-2）* 3）+ ... +（（N-1 + 1）* i）+ ...（1）其中， 。+（1 * N）

您可以參考這裏爲了簡化計算：(I asked HERE)

[你的答案]

= (((N) * (N+1) * (N+2))/6)

而且，我認爲它是正確的。我檢查如下：

N = 1, (1 * 2 * 3)/6 = 1 

N = 2, (2 * 3 * 4)/6 = 4 

N = 3, (3 * 4 * 5)/6 = 6 

N = 4, (4 * 5 * 6)/6 = 10 

N = 5, (5 * 6 * 7)/6 = 35 

此外，該算法的複雜度是O（n ）

EDIT：

下面的循環還具有計數的相同的數字，即是= (((N) * (N+1) * (N+2))/6)

for i in 1 … N loop 
    for j in i … N loop 
    for k in j … N loop 
     sum = sum + i ; 
    end loop; 
    end loop; 
end loop;