Понимание того, сколько раз будут выполняться вложенные циклы

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 - количество вложенных циклов.

Answer 2

Это число равно количеству троек {a, b, c}, где a <= b <= c <= n. <Br /> Поэтому это может быть выражено как комбинация с повторениями. . В этом случае общее количество комбинаций с повторениями составляет: n (n + 1) (n + 2) / 6

Answer 3

Математическая формула здесь .

Это сложность O (n ^ 3).

Answer 4

Вы знаете, сколько раз выполняется второй цикл, так что можете заменить первые два цикла одним, верно? как

for(ij = 1; ij < (n*(n+1))/2; ij++)
   for (k = 1; k <= ij; k++)
      x = x + 1;

Применение той же формулы, которую вы использовали для первой, где 'n' - это время, когда у вас будет n (n + 1) / 2 ((n (n + 1) / 2) * (n (n + 1) ) / 2 + 1)) / 2 - раз выполняется x = x + 1.

Answer 5

1 + (1 + 2) + (1+ 2+ 3) + ...... + (1 + 2 + 3 + ... n)

Answer 6

3-й внутренний цикл такой же, как и 2-й внутренний цикл, но вместо этого n является формулой.

Итак, если ваш внешний цикл равен n раз ...

и ваш второй цикл n(n+1)/2 раз ...

ваш третий цикл ....

(n(n+1)/2)((n(n+1)/2)+1)/2

Это скорее грубая сила, и ее, безусловно, можно упростить, но это всего лишь алгоритмическая рекурсия.