了解嵌套循环将运行多少次

Question

我试图理解在下面的代码中执行语句"x = x + 1"多少次,作为"n"的函数:

for (i=1; i<=n; i++)
  for (j=1; j<=i; j++)
    for (k=1; k<=j; k++)
       x = x + 1 ;

如果我没有错,第一个循环执行n次,第二个循环执行n (n + 1)/ 2次,但在第三个循环中我丢失了.也就是说,我可以计算它将被执行多少次,但我似乎无法找到公式或用数学术语解释它.

你能？

顺便说一下,这不是家庭作业或任何东西.我刚刚在一本书上找到并认为这是一个有趣的概念.

Answer 1

考虑循环for (i=1; i <= n; i++).看到这个循环n次是微不足道的.我们可以将其绘制为:

* * * * *

现在,当你有两个这样的嵌套循环时,你的内循环将循环n(n + 1)/ 2次.注意这是如何形成一个三角形,事实上,这种形式的数字被称为三角形数字.

* * * * *
* * * *
* * *
* *
*

因此,如果我们将其扩展到另一个维度,它将形成一个四面体.由于我不能在这里做3D,想象每一个都是彼此叠加的.

* * * * *     * * * *     * * *     * *     *
* * * *       * * *       * *       *
* * *         * *         *
* *           *
*

这些被称为四面体数,由以下公式产生:

n(n+1)(n+2)
-----------
     6

你应该能够确认一个小的测试程序确实是这种情况.

如果我们注意到6 = 3!,不难看出这种模式如何推广到更高的维度:

n(n+1)(n+2)...(n+r-1)
---------------------
         r!

这里,r是嵌套循环的数量.