Пазл, связанный с вложенными циклами

Для заданного ввода N сколько раз выполняет заключенный оператор?

for i in 1 … N loop for j in 1 … i loop for k in 1 … j loop sum = sum + i ; end loop; end loop; end loop; 

Может ли кто-нибудь найти простой способ или формулу для этого в целом. Пожалуйста, объясни.

  • Во-первых, я написал код C для генерации суммы:
 int main(){ int i =0, k =0, j =0, n =0; int N =0; int sum =0; N =10; for (n=1; n <= N; n++){ // unindented code here sum =0; for (i=1; i<=n; i++) for (j=1; j<=i; j++) for (k=1; k<=j; k++) sum++; printf("\n N=%d sum = %d",n, sum); } printf("\n"); } 
  • Простая компиляция и генерация результата для N=1 to N=10 :

$ gcc sum.c
$ ./a.out

  N=1 sum = 1 N=2 sum = 4 N=3 sum = 10 N=4 sum = 20 N=5 sum = 35 N=6 sum = 56 N=7 sum = 84 N=8 sum = 120 N=9 sum = 165 N=10 sum = 220 
  • Затем попытался изучить, How this works? с некоторыми диаграммами:

    Для N=1 :

 i<=N, (i=1) | j<=i, (j=1) | k<=j, (K=1) | sum=0. sum++ ---> sum = 1 

То есть (1) = 1

Для N=2 :

 i<=N, (i=1)-------(i=2) | |-----|-----| j<=i, (j=1) (j=1) (j=2) | | |----|----| k<=j, (K=1) (K=1) (K=1) (K=2) | | | | sum=0, sum++ sum++ sum++ sum++ --> sum = 4 

То есть (1) + (1 + 2) = 4

Для N=3 :

 i<=N, (i=1)-------(i=2)--------------------(i=3) | |-----|-----| |---------|-------------| j<=i, (j=1) (j=1) (j=2) (j=1) (j=2) (j=3) | | |----|----| | |----|----| |-----|-----| k<=j, (K=1) (K=1) (K=1) (K=2) (K=1) (K=1) (K=2) (K=1) (K=2) (K=3) | | | | | | | | | | sum=0, sum++ sum++ sum++ sum++ sum++ sum++ sum++ sum++ sum++ sum++ --> sum = 10 

То есть (1) + (1 + 2) + (1 + 2 + 3) = 10

 N = 1, (1) = 1 N = 2, (1) + (1 + 2) = 4 N = 3, (1) + (1 + 2) + (1 + 2 + 3) = 10 N = 4, (1) + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) = 20 N = 5, (1) + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4 + 5) = 35 

Наконец, я понял, что сумма N в трех циклах:

(1) + (сумма 0f 1 до 2) + ... + (сумма от 1 до (N-2)) + (сумма от 1 до (N-1)) + (сумма от 1 до N)

или мы можем написать это как:

=> (1) + (1 + 2) + ... + (1 + 2 + .... + i) + ... + (1 + 2 + .... + N-1) + (1 + 2 + .... + N)

= (N * 1) + ((N-1) * 2) + ((N-2) * 3) + ... + ((N-i + 1) * i) + ... + (1 * N)

Вы можете обратиться сюда для упрощения расчетов: (Я спросил ЗДЕСЬ )
введите описание изображения здесь

[ ВАШ ОТВЕТ ]

= ( ((N) * (N+1) * (N+2)) / 6 )

И, я думаю, это правильно. Я проверил следующее:

 N = 1, (1 * 2 * 3)/6 = 1 N = 2, (2 * 3 * 4)/6 = 4 N = 3, (3 * 4 * 5)/6 = 6 N = 4, (4 * 5 * 6)/6 = 10 N = 5, (5 * 6 * 7)/6 = 35 

Кроме того, сложность этого алгоритма O (n 3 )

EDIT :

Следующий цикл также имеет одинаковые числа отсчетов, то есть = ( ((N) * (N+1) * (N+2)) / 6 )

 for i in 1 … N loop for j in i … N loop for k in j … N loop sum = sum + i ; end loop; end loop; end loop; 
  • JavaScript: разница между .forEach () и .map ()
  • Цикл через массив имен переменных в Less
  • Страница непрерывной петли (не бесконечный свиток)
  • Когда это делать?
  • Суммарная сумма до достижения максимума, затем повторите с нуля в следующей строке
  • Почему объекты R не печатаются в функции или в цикле «для»?
  • Как создать цикл ViewPager?
  • Объединение по диапазону в R - Применение циклов
  • Однострочный цикл с обязательной парой фигурных скобок в Java
  • Усовершенствованный цикл «for» вызывает исключение ArrayIndexOutOfBoundsException
  • Как я могу перебирать все подпункты UIView, а также их подзоны и их подпрограммы
  • Давайте будем гением компьютера.