我真的不知道如何找出嵌套循环的结果。例如在下面的伪代码中，我无法理清执行结束时会给出什么。如果有人给我一个简单的解决方案，我会很高兴。
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
问题是：
r代码的结果是什么，并给出结果n？
我写了它，但每次我都感到困惑。
问问题
1640 次
3 回答
2
在您的伪代码中，最内层循环k <- j to i+j可以写为k <- 0 to i（这是通过删除j）。因此，您的代码可以简化如下：
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
基于这个伪代码，我编写了一个 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++){
// 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");
}
该程序的输出类似于：
$ ./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
然后，试图探索，它是如何工作的？附上一些图表：
执行树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 )
那是 (1*2) = 2
树为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 )
那是(1 + 1) + (3 + 3) = 8
同样，我为 画了一棵树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++
那是(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
对于 N=6，我们也可以将上述序列写为：
(1*2) + (2*3) + (3*4) + (4*5) + (5*6) + (6*7)
最后，我可以理解N三个循环的总和是：
(1*2) + (2*3) + (3*4) + (4*5) + (5*6) + ... + (N * (N+1))
在 math.stackexchange.com 的帮助下，我可以简化这个方程：
我在这里问：如何根据 N 简化求和方程？
因此，正如我对您的问题的评论，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
于 2013-06-10T12:22:38.350 回答
0
尝试使用一些这样的代码来解决它......即编码它是什么以及你认为它应该是什么并测试它。
编辑：根据上面的评论更新。
public class CountLoop{
public static void main(String[] args){
for(int i=1;i<=10;i++)
System.out.println("It's "+run(i)+" and I think "+guess(i));;
}
public static int run(int n){
int r = 0;
for(int i=1;i<=n;i++)
for(int j=1; j <= i;j++)
for(int k=j; k <= i+j; k++)
r += 1;
return r;
}
public static int guess(int n){
// taken from the comments
int r = ((n * (n+1) * (n+2)) /3);
return r;
}
}
运行这个得到
It's 2 and I think 2
It's 8 and I think 8
It's 20 and I think 20
It's 40 and I think 40
It's 70 and I think 70
It's 112 and I think 112
It's 168 and I think 168
It's 240 and I think 240
It's 330 and I think 330
It's 440 and I think 440
所以我们很高兴。
于 2013-06-10T09:04:33.893 回答
0
我得到它是这样的：
n = 1: r = 2
n = 2: r = 8
n = 3: r = 20
n = 4: r = 40
n = 5: r = 70
n = 6: r = 112
n = 7: r = 168
n = 8: r = 240
n = 9: r = 330
n = 10: r = 440
让我们说n = 10,
r = 2 + 6 + 12 + 20 + 30 + 42 + 56 + 72 + 90 + 110 = 440
=> r = 2(1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 + 55)
直觉上，我认为
n = sum(n-1) + n * (n + 1).
在哪里
sum(n-1) = value of r for n-1
于 2013-06-10T09:23:37.303 回答