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

查看：133 发布时间：2018/1/27 22:52:47 loops time for-loop nested-loops

本文介绍了与嵌套循环有关的一个难题的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

对于给定的输入N，封闭语句执行多少次？

  for i in 1 ... N loop 
 for j in 1 ... i loop 
 for k in 1 ... j loop 
 sum = sum + i; 
结束循环; 
结束循环; 
结束循环;

任何人都可以找出一个简单的方法或公式来做到这一点。请解释。

解决方案

首先，我写了一个

 C  
 $ b 
 
 
  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 ++）{
 //这里的缩进代码
 sum = 0; （k = 1; k <= j; k ++ 1）;（b = 1; i = ）
 sum ++; 
 
 printf（\\\
 N =％d sum =％d，n，sum）; 
} 
 printf（\\\
）; 
 
 
 
 
 $ b $ ul 
 $ li $编译并生成结果为 N = 1到N = 10 ：

 
 
   $ gcc sum.c  
 
  $ ./a.out  
 
 
 $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ 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

< 对于 > N = 1 ： i <= N，（i = 1） | j <= i，（j = 1） | k <= j，（K = 1） | sum = 0。 sum ++ ---> sum = 1 即（1）= 1 对于 N = 2 ：（$ = $）$（$） | ----- | ----- | （j = 1）（j = 1）（j = 2） | | | ---- | ---- | （K = 1）（K = 1）（K = 1） | | | | sum = 0，sum ++ sum ++ sum ++ sum ++ - > （1）+（1 + 2）= 4

）= 4

对于 N = 3 ：

< blockquote>

i <= N，（i = 1）-------（i = 2）---------- ----------（i = 3） | | ----- | ----- | | --------- | ------------- | （j = 2）（j = 1）（j = 2）（j = 3） | | | ---- | ---- | | | ---- | ---- | | ----- | ----- | （K = 1）（K = 1）（K = 1）（K = 1）（K = 1）（K = 1） K = 2）（K = 3） | | | | | | | | | | sum = 0，sum ++ sum ++ sum ++ sum ++ sum ++ sum ++ sum ++ sum ++ sum ++ sum ++ - > （1）+（1 + 2）= 10

）+（1 + 2 + 3）= 10

  N = 1，（1）= 1 
 $ b （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 
  
 $ p $最后，我可以理解在三个循环中 N 的总和是： （1）和（N-1）之和（1）+（和0f 1到2）+ ... +（1到（N-2）的和）+ ））+（1到N之和）
 
 或者我们可以把它写成：
 
 $ p $ 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 * N）
 
 
用于简化计算：（我问了这里） 
 
  
 
 
 （您的答案]  
 $ b $  =（（（N）*（N + 1）*（N +2））/ 6） 
 
 
 而且，我认为它是正确的。我检查如下：
 
   N = 1，（1 * 2 * 3）/ 6 = 1 
 $ b （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 
   3 ） 
 
  编辑： 
 
 
以下循环也具有相同的计数值，即 =（（（N）*（ N + 1）*（N + 2））/ 6）  
 
 
  N循环
为j在i ... N循环
为k在j ... N循环
 sum = sum + 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 N=%d  sum = %d",n, sum); 
  }
  printf("\n");
}




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屋！

查看全文

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

问题描述

相关文章

其他开发最新文章

热门教程

热门工具

登录关闭

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

问题描述

相关文章

其他开发最新文章

热门教程

热门工具

登录 关闭

登录关闭