求嵌套for循环中语句执行次数。

Question

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
       for (int k = j + 1; k < n; k++) {
            count++;
       }
    }
}

以上循环中,count最后的值是怎么算出来的，求个计算过程，哪个大佬帮忙解答下，我算着算着老是绕晕了

Answer 1

• i=0 时，j 这层循环的执行次数为 n-1，k 这层循环的执行次数 为 (n-2)(n-3)/2 = (n-2)((n-2)-1)/2 = ((n-2)^2 - (n-2))/2
• i=1 时，j 这层循环的执行次数为 n-2，k 这层循环的执行次数 为 (n-3)(n-4)/2 = ((n-3)^2 - (n-3))/2
• ...
• i=n-3 时，j 这层循环的执行次数为 2，k 这层循环的执行次数 为 2/2 = 1
• i=n-2 时，j 这层循环的执行次数为 1，k 这层循环的执行次数 为 0/2 = 0

则 k 这层循环的执行总次数为：

   ((n-2)^2 - (n-2) + (n-3)^2 - (n-3) + ... + 2 + 0)/2
    = ((n-2)^2 + (n-3)^2 + ... + (n-(n-1))^2 + (n - n)^2)/2 + (n-2 + n-3 + ... + n-(n-1) + n-n)/2
    = (n-2)(n-1)(2n-3)/6/2 + (n-2)(n-1)/2/2
    = n(n-1)(n-2)/6
    = n(n^2 - 3n + 2)/6

相当于计算 (0·1 + 1·2 + 2·3 + ... + (n-2)(n-3))/2 即 ((1^2 + 2^2 + ... + (n-2)^2) + (1 + 2 + ... + n-2))/2
n^2的求和公式是n(n+1)(2n+1)/6
n的求和公式为n(n+1)/2

Answer 2

count默认值是0

Answer 3

n(n-1)(n-2)?我也晕

Answer 4

https://www.wolframalpha.com/...

sum_(i=0)^(n - 1)( sum_(j=i + 1)^(n - 1)( sum_(k=j + 1)^(n - 1) 1)) = 1/6 n (n^2 - 3 n + 2)

Answer 5

用断点调试看下，看看代码是怎么运行的

Answer 6

内部循环的次数受外部循环影响，加操作是在最内层循环，所以n不够大（小于3）的时候拿到的都是0
在后面的规律是这样：

• n = 3 -> 1
• n = 4 => 1 + (1 + 2)
• n = 5 -> 1 + (1 + 2) + (1 + 2 + 3)

公式不会推…思路的话
可以把k这层循环去掉，只观察i和j两层，k和j的关系 和 j和i的关系是一样的
可以在 count++ 后面接一句输出，观察变化

System.out.printf("count = %d, i = %d, j = %d, k = %d\n", count, i, j, k);

Answer 7

数学排列组合思路