了解嵌套循环将运行多少次 [英] Understanding How Many Times Nested Loops Will Run

问题描述

我试图了解以下代码中作为"n"的函数执行了"x = x + 1"语句的次数:

I am trying to understand how many times the statement "x = x + 1" is executed in the code below, as a function of "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 次，但是在第三个循环中走开.也就是说，我可以指望它会执行多少次，但似乎找不到公式或用数学术语来解释它.

If I am not wrong the first loop is executed n times, and the second one n(n+1)/2 times, but on the third loop I get lost. That is, I can count to see how many times it will be executed, but I can't seem to find the formula or explain it in mathematical terms.

可以吗?

通过这种方式，这不是家庭作业或其他任何东西.我刚发现一本书，并认为这是一个有趣的概念.

By the way this is not homework or anything. I just found on a book and thought it was an interesting concept to explore.

推荐答案

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

Consider the loop for (i=1; i <= n; i++). It's trivial to see that this loops n times. We can draw this as:

* * * * *

现在，当您有两个这样的嵌套循环时，您的内部循环将循环 n(n + 1)/2 次.请注意，它是如何形成三角形的，实际上，这种形式的数字称为三角形数.

Now, when you have two nested loops like that, your inner loop will loop n(n+1)/2 times. Notice how this forms a triangle, and in fact, numbers of this form are known as triangular numbers.

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

因此，如果将其扩展另一个维度，它将形成四面体.由于我无法在此处进行3D操作，因此可以想象将它们层叠在一起.

So if we extend this by another dimension, it would form a tetrahedron. Since I can't do 3D here, imagine each of these layered on top of each other.

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

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

These are known as the tetrahedral numbers, which are produced by this formula:

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

使用小型测试程序，您应该可以确认确实如此.

You should be able to confirm that this is indeed the case with a small test program.

如果我们注意到 6 = 3！，那么

If we notice that 6 = 3!, it's not too hard to see how this pattern generalizes to higher dimensions:

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

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

Here, r is the number of nested loops.

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