一个与嵌套循环相关的谜题 [英] A puzzle related to nested loops

问题描述

对于给定的输入 N，所包含的语句执行多少次?

for i in 1 … N 循环对于 j in 1 … i 循环for k in 1 … j 循环总和 = 总和 + i ;结束循环；结束循环；结束循环；

任何人都可以找出一种简单的方法或公式来执行此操作.请解释.

解决方案

• 首先，我写了一段C代码来生成sum:

<块引用>

int main(){int i =0, k =0, j =0, n =0;整数 N = 0;int sum =0;N = 10;对于 (n=1; n <= N; n++){//这里没有缩进的代码总和 = 0;对于 (i=1; i<=n; i++)对于 (j=1; j<=i; j++)对于 (k=1; k<=j; k++)总和++；printf("
 N=%d sum = %d",n, sum);}printf("
");}

• 简单编译并生成N=1 to N=10的结果:

$ gcc sum.c
$ ./a.out

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

• 然后，尝试用一些图表探索这是如何工作的?:

  对于，N=1:

<块引用>

i<=N, (i=1)|j＜=i，(j=1)|k＜＝j，(K＝1)|总和=0.总和++ --->总和 = 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++ -->总和 = 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) = 1N = 2, (1) + (1 + 2) = 4N = 3, (1) + (1 + 2) + (1 + 2 + 3) = 10N = 4, (1) + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) = 20N = 5, (1) + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4 + 5) = 35

最后，我可以理解三个循环中 N 的总和是:

(1) + (sum 0f 1 to 2) + ... + (sum of 1 to (N-2)) + (sum of 1 to (N-1) ) + (sum of 1 to N)

或者我们可以写成:

=> (1) + (1 + 2) + ...+ (1 + 2 +....+ i) + ... + (1 + 2 + ....+ N-1)+ (1 + 2 + ....+ N)

=> ( N * 1 ) + ( (N-1) * 2) + ( (N-2) * 3) +...+ ( (N -i+1) * i ) +...+ ( 1 * N)

您可以参考此处进行简化计算:(我问这里 )

[你的答案]

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

而且，我认为它是正确的.我检查如下:

N = 1, (1 * 2 * 3)/6 = 1N = 2, (2 * 3 * 4)/6 = 4N = 3, (3 * 4 * 5)/6 = 6N = 4, (4 * 5 * 6)/6 = 10N = 5, (5 * 6 * 7)/6 = 35

另外，这个算法的复杂度是 O(n³)

编辑:

以下循环也有相同的计数，即 = ( ((N) * (N+1) * (N+2))/6 )

for i in 1 … N 循环for j in i … N 循环for k in j … N 循环总和 = 总和 + i ;结束循环；结束循环；结束循环；

For a given input N, how many times does the enclosed statement executes?

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;

Can anyone figure out an easy way or a formula to do this in general. Please explain.

解决方案

• First, I written a C code to generate sum:

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=%d  sum = %d",n, sum); 
  }
  printf("
");
}

• Simple compile and generate result for 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

• Then, Tried to explore How this works? with some diagrams:

  For, N=1:

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

That is (1) = 1

For, 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

That is (1) + (1 + 2) = 4

For, 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

That is (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

Finally, I could understood that sum of N in three loop is:

(1) + (sum 0f 1 to 2) + ... + (sum of 1 to (N-2)) + (sum of 1 to (N-1) ) + (sum of 1 to N)

or we can write it as:

=> (1) + (1 + 2) + ...+ (1 + 2 +....+ i) + ... + (1 + 2 + ....+ N-1) + (1 + 2 + ....+ N)

=> ( N * 1 ) + ( (N-1) * 2) + ( (N-2) * 3) +...+ ( (N -i+1) * i ) +... + ( 1 * N)

You can refer here for simplification calculations: (I asked HERE )

[YOUR ANSWER]

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

And, I think its correct. I checked as follows:

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   

Also, The complexity of this algorithm is O(n³)

EDIT:

The following loop also has same numbers of count, that is = ( ((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;

这篇关于一个与嵌套循环相关的谜题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！