сколько раз будет выполняться этот цикл

Question

Мне было просто интересно, сколько раз такой циклический цикл будет выполняться

int sum = 0;
for(int i = 0; i < total; i++) {
    for(int j = i + 1; j < total; j++) {
        for(int k = j; k < total; k++) {
            sum++;    
        }
    }
}
System.out.println(sum);

Я легко вижу вывод суммы, но я хотел бы иметь возможность математически рассчитать сумму sum с любым числом для total.

Answer 1

Эта функция зациклится (total/6)*(total*total - 1) раз Ниже приведен фрагмент кода, подтверждающий, что

var total = 100
var sum = 0;
for(var i = 0; i < total; i++) {
    for(var j = i + 1; j < total; j++) {
        for(var k = j; k < total; k++) {
            sum++;    
        }
    }
}

function calc(n) {
  return n*(n-1)*(n+1)/6
}

console.log("sum: "+sum)
console.log("calc: "+calc(total))

Answer 2

Простой цикл вроде этого:

for (i = a; i < b; i ++) {
    ....
}

запускает b-a итерации (i принимает значения: a, a+1, a+2 ... b-2, b-1), если a < b и 0 итерации в противном случае. Ниже мы будем предполагать, что a < b всегда.

Его число итераций может быть вычислено с использованием простой математической формулы:

Применение формулы к вашему коду

Начнем с самого внутреннего цикла:

for(int k = j; k < t; k++) {
    sum++;    
}

Число итераций:

Используя формулу выше, значение U равно (t-1)-j+1, что означает:

U = t - j

Добавление средней петли

При добавлении среднего цикла количество итераций становится равным:

Условия второй суммы t-(i+1), t-(i+2), ... t-(t-2), t-(t-1).
Решив скобки и поместив их в обратном порядке, они могут быть записаны как:
1, 2, ... t-i-2, t-i-1.

Пусть p = t - j. Вторая сумма теперь становится:

Это сумма первых t-i-1 натуральных чисел и ее значение:

Добавление внешнего цикла

При добавлении внешнего цикла сумма становится:

В последней сумме выражение (t - i) начинается с t (когда i = 0), продолжается с t-1 (когда i = 1) и продолжает уменьшаться, пока не достигнет 1 (когда i = t - 1). При замене q = t - i последняя сумма становится:

Последнее выражение вычитает сумму первых n натуральных чисел из сумму первых n квадратных чисел . Его значение:

Теперь легко упростить выражение:

Окончательный ответ

Количество итераций размещенного кода:

Answer 3

Первая итерация среднего цикла добавляет

total-1 + total-2 + ... + 1 

к сумме.

Вторая итерация среднего цикла добавляет

total-2 + total - 3 + ... + 1 

на сумму

Последняя итерация среднего цикла добавляет

1

к сумме.

Если вы сложите все эти условия, вы получите

(total - 1) * 1 + (total - 2) * 2 + (total - 3) * 3 + ... + 2 * (total - 2) + 1 * (total - 1)

Прошло много времени с тех пор, как я изучал математику, поэтому я не помню, есть ли более простая формула для этого выражения.

Например, если всего 10, вы получите:

9 * 1 + 8 * 2 + 7 * 3 + 6 * 4 + 5 * 5 + 4 * 6 + 3 * 7 + 2 * 8 + 1 * 9 =
9 + 16 + 21 + 24 + 25 + 24 + 21 + 16 + 9 = 
165

Answer 4

Если мы запустим этот цикл 100 раз и сгенерируем набор данных, а затем построим график, то получим:

Теперь этот график явно кубический. Таким образом, мы можем сделать решение, используя кубическое уравнение ax ^ 3 + bx ^ 2 + cx + d.

Используя 4 балла, все они имеют значения:

Итак, полное уравнение:

y=x^3/6-x/6
y=x(x^2/6-1/6)
y=(x/6)(x^2-1)

Интерактивный график:

<iframe src="https://www.desmos.com/calculator/61whd83djd?embed" width="500px" height="500px" style="border: 1px solid #ccc" frameborder=0></iframe>

Answer 5

Как мы знаем, сумма арифметической прогрессии равна:

Самая внутренняя петля зациклится на

раз, что является функцией j.

Вы суммируете это и получаете функцию для i, иначе:

Вы снова суммируете его и получаете функцию для total, иначе:

---

Для Mathematica пользователей, результат:

f[x_]:=Sum[Sum[x-j,{j,i+1,x-1}],{i,0,x-1}]

С здесь , мы можем видеть это более четко, и результат FINAL :

, где x равно total.

Answer 6

Уравнение как ниже и k равно общему:

Answer 7

внешний цикл выполняется «общее» количество раз.

для каждого внешнего цикла, средний цикл запускается 'total-i' раз.

то есть всего * всего + всего * (всего-1) + всего * (всего-2) .... всего * 1

= всего * (всего + всего-1 + всего-2 ... 1)

= всего * (1 + 2 + 3 .... всего)

= итого * (сумма первых «итоговых» натуральных чисел)

= всего * (всего * (всего + 1) / 2)

теперь самый внутренний цикл также выполняет 'total-j' раз для каждого среднего цикла

т.е. всего * (всего * (всего + 1) / 2) * (общая + (всего-1) + (всего-2) .... + 1)

= всего * (всего * (всего + 1) / 2) * (1 + 2 + 3 .... + всего)

= всего * (всего * (всего + 1) / 2) * (сумма первых «общих» натуральных чисел)

= всего * (всего * (всего + 1) / 2) * (всего * (всего + 1) / 2) .. Итак, наконец вы получите что-то близкое к

всего * (всего * (всего + 1) / 2) * (всего * (всего + 1) / 2).

Извините, есть исправление, так как @andreas упомянул самые внутренние и средние циклы, которые выполняются только до общего значения i-1 в этом случае это будет сумма первых (итоговых-1) no.s, которые должны быть (итоговые-1) * total / 2, поэтому конечный результат должен составлять

всего * (всего * (всего-1) / 2) * (всего * (всего-1) / 2).

Answer 8

Требуется лишь немного знаний о программировании. Фактически логика, которая работает позади, - это всего лишь вычислительная вещь. скажем:

total=10,sum=0

- когда мне 0:

В это время j также инициализируется 1 (i + 1) и k. Таким образом, k приведет нас к выполнению цикла 9 раз, а при увеличении j это приведет к выполнению оператора суммирования 8 раз и 7 раз, а затем 6 раз до 1 раза. (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 раз.)

- когда я 1:

Это время j также инициализируется с помощью 2 и k. Таким образом, оператор суммирования будет выполняться 8 раз, затем 7 раз, а затем 6 раз до 1. (8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 раз).

- когда мне 2:

То же самое происходит многократно, но начинается с разницы, поэтому на этот раз (7 + 6 + 5 + 4 + 3 + 2 + 1 = 28)

• Таким образом, эта последовательность продолжается до тех пор, пока не возникнет значимость возникновения условия с истинностью. Это происходит до тех пор, пока мне не исполнится 9.

Итак, окончательный ответ: 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 = 165.

Answer 9

TL; DR

Цикл будет выполняться для ((total ^ 3) - total) / 6 раз, и, следовательно, это будет значение sum в конце цикла.

---

int sum = 0;
for(int i = 0; i < total; i++) { 
    for(int j = i + 1; j < total; j++) {
        for(int k = j; k < total; k++) {
            sum++;    
        }
    }
}

Легко видеть, что внешний цикл работает total раз. Второй цикл сложнее

Давайте попробуем решить это

i = 0, j работает с 1..total - 1

i = 1, j работает с 2..total - 1

i = 2, j работает с 3..total - 1

... i = total - 2, j запускается с total - 1 ..total - 1 (будет запускаться только один раз)

i = total - 1, внутренний цикл не выполняется, поскольку условие завершения цикла выполняется.

Третий цикл зависит от второго внутреннего цикла - k начинается с j..total - 1

Давайте возьмем всего 6

j выполняется из 1..5 -> k выполняется 5 раз (j = 1) + 4 раза (j = 2) + 3 раза (j = 3) + 2 раза (j = 4) + 1 раз (j = 4)

(Отображение минифицированной версии для других)

2..5 -> 4+3+2+1
3..5 3+2+1
4..5 2+1
5..5 1

Что такое

1 + 2 + 3 + 4 + 5+
1 + 2 + 3 + 4 + 
1 + 2 + 3 +
1 + 2 +
1

Вообще,

1 + 2 + 3 + .. n +
1 + 2 + 3 +..n - 1+
1 + 2 + 3 +..n - 2+
1 + 2 + 3 +
1 + 2 +
1

Это сводится к сумме n * (n - 1)) / 2

Для все значения из n в диапазоне от 1 to total

Это можно проверить с помощью приведенного ниже

int res = 0;
for (int i = 1; i <= total; i++) {
    res += (i * (i - 1))/2;
}

res будет равно вашему sum.

Математически, выше

((total ^ 3) - total) / 6

Вывод:

Ссылка:

Суммы первых русских натуральных чисел

Сумма квадратов первых русских натуральных чисел