与嵌套循环相关的拼图

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;