嵌套循环结果 [英] Nested loops result

问题描述

我真的不知道如何找出嵌套循环的结果。
例如在下面的伪代码中，我无法理清在执行结束时会给出的内容。我会很高兴，如果有人给我一个简单的解决方案。

  r < -  0 
 for i< ;对于j< -1，对于k< -j到i + j do 
r< -r + 1 
 return r 
  

问题是：

什么是代码结果并以 n 的形式给出结果 r ？

我写这个，但是每次都感到困惑。在你的伪代码中，Inner most loop， k < - j to i + j 可以写成 k < - 0到i （这是通过移除 j 的）。因此，你的代码可以简化如下：

  r < -  0 
 for i < -  1 to n做
给j <-1给我做
给k <-0给我do //注意这里`j`去掉
r < -  r + 1 
 return r 
  

基于这个伪代码，我写了一个C程序（如下）生成序列对于N = 1到10.（你最初标记的问题为 java 但是我正在写 c 代码，因为什么你希望独立于语言限制）

  #include< stdio.h> 
 int main（）{
 int i = 0，k = 0，j = 0，n = 0; 
 int N = 0; 
 int r = 0; 
 N = 10; 
 for（n = 1; n <= N; n ++）{
 //这里的缩进代码
 r = 0; （k = 0; k <= i; k ++）时，对于（i = 1;j≤i; j ++）
， ）
 r ++; 
 printf（\\\
 N =％d result =％d，n，r）; 
} 
 printf（\\\
）; 
 
 
 
 
 
 
这个程序的输出是这样的：
 
 
  $ ./a.out 
 N = 1结果= 2 
 N = 2结果= 8 
 N = 3结果= 20 
 N = 4结果= 40 
 N = 5结果= 70 
 N = 6结果= 112 
 N = 7结果= 168 
 N = 8结果= 240 
 N = 9结果= 330 
 N = 10结果= 440 
  
然后，试图探索它是如何工作的：
 
 $ b 
执行树对于 N = 1 ：
 
 $ p $  1 <= i <= 1，（i = 1）
 | （K = 1）
（b = 1）
 1 <= j <= | | 
 r = 0 r ++ r ++ => r = 2 
（1 + 1）
  

即 1 * 2）= 2

树对于 N = 2 ：

  1 <= i <= 2，（i = 1）---------------- -------（i = 2）
 | | --------- | ------ | （j = 1）（j = 1）（j = 2）
 1< = j< = \ / | （K = 0）（K = 1）（K = 0）（K = 1）（K = 2）（K = 0）（K = 1） k = 2）
 | | | | | | | | 
 r = 0 r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ => 8 
 -------------- ------------------------------- -  
（1 + 1）（3 + 3）
  

即：



  1 <= i <= 3，（i = 1） - ---------------------（I = 2）------------------------ --------------------（i = 3）
 | | --------- | ------ | | ---------------------- | ---------------------- | （j = 1）（j = 1）（j = 2）（j = 1）（j = 2）（j = 3）
 / 1 / | \ / | \ / | | \ / | | \ / | | （K = 0）（K = 1）（K = 0）（K = 1）（K = 2）（K = 0）（K = 1） k = 2）/ | | \ / | | \ / | | \ 
 | | | | | | | | （k = 0）（k = 1）（k = 0）（k = 1）（k = 0）（k = 1） （k = 2）（k = 3）
r = 0 r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ r ++ 
  （1 + 1）+（3 + 3）+（4 + 4 + 4）= 20  N = 2，（1 + 1）+（$）
 
 
  （3 + 3）= 8 
 N = 3，（1 + 1）+（3 + 3）+（4 + 4 + 4）= 20 
 N = 4，（1 + 1）+ （3 + 3）+（4 + 4 + 4）+（5 + 5 + 5 + 5）= 40 
 N = 5，（1 + 1）+ （1 + 1）+（3 + 3）+（4 + 4）+（5 + 5 + 5 + 5）+（6 + 6 + 6 + 6 + 6）= 70 
 + 4）+（5 + 5 + 5 + 5）+（6 + 6 + 6 + 6 + 6）+（7 + 7 + 7 + 7 + 7 + 7）= 112 
  
 
 
 
 
 
 
对于N = 6，我们也可以写成上面的顺序： （1 * 2）+（2 * 3）+（3 * 4）+（4 * 5）+（5 * 6）+（6 * 7）
  
最后，我可以理解在三个循环中 N 的总和是： p> 
 
 <$ p （1 * 2）+（2 * 3）+（3 * 4）+（4 * 5）+（5 * 6）+ ... +（N *（N + 1） ））
  

在math.stackexchange.com的帮助下，我可以简化这个等式： b $ b我在这里问：如何简化求和方程以N计？

（（（N）*（N + 1）*（N + 2））/ 3）。我交叉检查如下：

  N = 1，（1 * 2 * 3）/ 3 = 2 
 
 N = 2，（2 * 3 * 4）/ 3 = 8 
 
 N = 3，（3 * 4 * 5）/ 3 = 20 
 
 N = 4，（4 * 5 * 6）/ 3 = 40 
 
 N = 5，（5 * 6 * 7）/ 3 = 70 
  / pre> 
I really don't know how to find out the result of nested loops. 
For example in the following pseudo-code, I can't sort out what will be given at the end of execution. I'll be so glad if anyone gives me a simple solution.
r <- 0
for i <- 1 to n do 
  for j <- 1 to i do
    for k <- j to i+j do
      r <- r + 1
return r
Question is: 

What is the result of the code and give the result r in terms of n? 

I write it but every time I get confused. 
解决方案
In your pseudo-code, Inner most loop, k <- j to i+j can be written as k <- 0 to i (this is by removing j). Hence your code can be simplified as follows: 
r <- 0
for i <- 1 to n do 
    for j <- 1 to i do
      for k <- 0 to i do   // notice here `j` removed
        r <- r + 1
return r
Based on this pseudo-code, I have written a C program(as below) to generate sequence for N = 1 to 10. (you originally tagged question as java but I am writing c code because what you wants is independent of language constraints)
#include<stdio.h>
int main(){
  int i =0, k =0, j =0, n =0;
  int N =0; 
  int r =0;
  N =10;
  for (n=1; n <= N; n++){
  // unindented code here
  r =0;
  for (i=1; i<=n; i++)
      for (j=1; j<=i; j++)
          for (k=0; k<=i; k++)
              r++;    
  printf("\n N=%d  result = %d",n, r); 
  }
  printf("\n");
}
Output of this program is something like:
 $ ./a.out     
 N=1  result = 2
 N=2  result = 8
 N=3  result = 20
 N=4  result = 40
 N=5  result = 70
 N=6  result = 112
 N=7  result = 168
 N=8  result = 240
 N=9  result = 330
 N=10  result = 440
Then, Tried to explore, How does it work? with some diagrams:  

Execution Tree For N=1:    
1<=i<=1,              (i=1)
                        |
1<=j<=i,              (j=1)
                      /   \
0<=k<=i,          (K=0)    (K=1)
                   |        |  
r=0                r++      r++    => r = 2
                 ( 1   +    1 )
That is     (1*2) = 2 

Tree For N=2:
1<=i<=2,         (i=1)-----------------------(i=2)
                  |                 |---------|------|
1<=j<=i,        (j=1)           (j=1)              (j=2)
                /   \          /  |  \            /  |  \
0<=k<=i,    (K=0)    (K=1)  (K=0)(K=1)(k=2)    (K=0)(K=1)(k=2)
              |        |      |     |    |       |     |    |
r=0          r++      r++   r++   r++  r++     r++   r++  r++    => 8
            --------------  ---------------------------------
            ( 1   +    1)   (     3         +      3        )
That is (1 + 1) + (3 + 3) = 8

Similarly I drawn a tree for N=3:
1<=i<=3,        (i=1)-----------------------(i=2)--------------------------------------------(i=3)
                  |                 |---------|------|                  |----------------------|----------------------|
1<=j<=3,        (j=1)             (j=1)            (j=2)            (   j=1   )           (   j=2    )           (   j=3    )
                /   \            /  |  \          /  |  \          / |       |  \        / |       |  \          / |       | \
0<=k<=i,    (K=0)   (K=1)    (K=0)(K=1)(k=2)   (K=0)(K=1)(k=2)    /  |       |   \      /  |       |   \        /  |       |  \
              |       |        |    |    |       |    |    |     (K=0)(K=1)(k=2)(k=3)  (K=0)(K=1)(k=2)(k=3)  (K=0)(K=1)(k=2)(k=3)
r=0          r++     r++      r++  r++  r++     r++  r++  r++     r++  r++   r++  r++   r++  r++  r++  r++   r++  r++   r++   r++
That is (1 + 1) + (3 + 3) + (4 + 4+ 4)= 20
N = 1,   (1 + 1) = 2  
N = 2,   (1 + 1) + (3 + 3) = 8  
N = 3,   (1 + 1) + (3 + 3) + (4 + 4 + 4)= 20  
N = 4,   (1 + 1) + (3 + 3) + (4 + 4 + 4) + (5 + 5 + 5 + 5)  =  40  
N = 5,   (1 + 1) + (3 + 3) + (4 + 4 + 4) + (5 + 5 + 5 + 5) + (6 + 6 + 6 + 6 + 6) = 70  
N = 6,   (1 + 1) + (3 + 3) + (4 + 4 + 4) + (5 + 5 + 5 + 5) + (6 + 6 + 6 + 6 + 6) + (7 + 7 + 7 + 7 + 7 + 7)= 112  
For  N=6 we can also be write above sequence as:
(1*2) + (2*3) + (3*4) + (4*5) + (5*6) + (6*7)    
Finally, I could understand that sum of N in three loop is:
(1*2) + (2*3) + (3*4) + (4*5) + (5*6) + ... + (N * (N+1))
With help from math.stackexchange.com, I could simplify this equation:

I asked here: How to simplify summation equation in terms of N?       

  
    
So as I commented to your question, Result in term of N is ( ((N) * (N+1) * (N+2)) / 3 ).

And, I think its correct. I cross checked it as follows:
N = 1,    (1 * 2 * 3)/3  = 2

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

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

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

N = 5,    (5 * 6 * 7)/3 =  70    


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