嵌套for循环中的迭代次数？

Question

所以我从教科书中查看这段代码:

for (int i=0; i<N; i++)
   for(int j=i+1; j<N; j++)

作者指出,内部for循环完全迭代N*(N-1)/ 2次,但没有给出他如何达到这样一个等式的基础.我理解N*(N-1),但为什么除以2？我自己运行代码,当N为10时,内循环迭代45次(10*9/2).

我自己弄乱了代码并尝试了以下内容(仅将i分配给j):

for (int i=0; i<N; i++)
   for(int j=i; j<N; j++)

当N = 10时,这导致55.所以我在这里理解基础数学有困难.当然,我可以插入所有的价值观,并通过问题强行解决问题,但我觉得有一些必要的东西,非常简单,我很想念.您如何想出一个用于描述我刚刚构造的for循环的等式？有没有办法在不依赖输出的情况下做到这一点？非常感谢任何帮助,谢谢!

Answer 1

想想每次外循环迭代时会发生什么.第一次,i == 0所以内循环开始1并运行到N-1,这总是N-1迭代.下一次通过外部循环,i增加到1,所以内部循环开始2并运行到N-1总共N-2迭代.并且这种模式继续:第三次通过外循环,你得到N-3迭代,第四次通过N-4,等等.当你到达外循环的最后一次迭代时i == N-1,所以内循环开始j = N并立即停止.所以这是零迭代.

迭代总数是所有这些数字的总和:

(N-1) + (N-2) + (N-3) + ... + 1 + 0

看看它的另一种方式,这仅仅是从正整数的总和1来N-1.这个和的结果称为第(N-1)个三角形数,维基百科解释了如何找到第n个三角形数的公式是n(n + 1)/ 2.但是在这里你有第(N-1)个三角形数字,所以如果你设置n=N-1,你得到

(N-1)(N-1+1)/2 = N(N-1)/2

Answer 2

你正在看嵌套循环,其中外部循环运行N时间和内部循环(N-1).你实际上把1 + 2 + 3 +的总和加起来....

这N * (N+1) / 2是数学中的"经典"公式.年轻的卡尔·高斯,后来成为着名的数学家,被给予了课堂上的繁忙工作:将数字从1加到100.老师希望让孩子们忙碌一小时,但卡尔几乎立刻想出了答案:5050.他解释说:1 + 100; 2 + 99; 3 + 98; 4 + 97; 等等达到50 + 51.这是50个,每个101.您还可以将其视为(100/2)*(100 + 1); 这就是它的/2来源.

至于为什么它(N-1)而不是我提到的(N + 1)...这可能与从1而不是0开始,这会从内循环中删除一次迭代,我想.