Количество итераций во вложенных циклах for?

Question

Итак, я искал этот код из учебника:

for (int i=0; i<N; i++)
   for(int j=i+1; j<N; j++)

Автор заявил, что внутренний цикл for повторяется ровно N * (N-1) / 2 раза, но не дает оснований для того, как он пришел к такому уравнению. Я понимаю N * (N-1), но зачем делить на 2? Я сам выполнил код и, конечно, когда N равно 10, внутренний цикл повторяется 45 раз (10 * 9/2).

Я сам возился с кодом и попробовал следующее (назначил только i для j):

for (int i=0; i<N; i++)
   for(int j=i; j<N; j++)

При N = 10 это приводит к 55. Поэтому у меня возникают проблемы с пониманием математики, лежащей здесь в основе. Конечно, я мог бы просто включить все значения и грубо преодолеть проблему, но я чувствую, что есть кое-что существенное и очень простое, что я упускаю. Как бы вы пришли к уравнению для описания только что построенного цикла for? Есть ли способ сделать это, не полагаясь на выходы? Буду очень признателен за любую помощь, спасибо!

Answer 1

Подумайте о том, что происходит каждый раз, когда внешний цикл повторяется.В первый раз, i == 0, поэтому внутренний цикл начинается с 1 и продолжается до N-1, что составляет N-1 итераций в общей сложности.В следующий раз во внешнем цикле значение i увеличилось до 1, поэтому внутренний цикл начинается с 2 и продолжается до N-1, в общей сложности N-2 итераций.И этот паттерн продолжается: в третий раз через внешний цикл вы получаете N-3 итераций, в четвертый раз через N-4 и т. Д. Когда вы переходите к последней итерации внешнего цикла, i == N-1, то есть внутреннийцикл начинается с j = N и сразу останавливается.Так что это ноль итераций.

Общее количество итераций является суммой всех этих чисел:

(N-1) + (N-2) + (N-3) + ... + 1 + 0

Чтобы взглянуть на это иначе, это всего лишь сумма натуральных чисел из1 до N-1.Результат этой суммы называется (N-1) -ым треугольным числом , и Википедия объясняет, как можно найти, что формула для n-го треугольного числа равна n (n+ 1) / 2.Но здесь у вас есть (N-1) -й треугольный номер, поэтому, если вы установите n=N-1, вы получите

(N-1)(N-1+1)/2 = N(N-1)/2

Answer 2

Вы смотрите на вложенные циклы, где внешний запускается N раз, а внутренний (N-1).По сути, вы складываете сумму 1 + 2 + 3 + ....

N * (N+1) / 2 - это «классическая» формула в математике.Молодому Карлу Гауссу, позже известному математику, дали занятие в классе: сложение чисел от 1 до 100. Учитель ожидал, что дети будут заняты в течение часа, но Карл почти сразу получил ответ: 5050. Он объяснил: 1 + 100;2 + 99;3 + 98;4 + 97;и так далее до 50 + 51. Это 50 сумм по 101 на каждого.Вы также можете видеть это как (100/2) * (100 + 1);вот откуда взято /2.

Что касается того, почему это (N-1) вместо (N + 1), о котором я говорил ... это может быть связано с началом с 1, а не с 0,я думаю, это отбросило бы одну итерацию из внутреннего цикла.

Answer 3

Посмотрите, сколько раз внутренний цикл (j) выполняется для каждого значения i.Когда N = 10, внешний цикл (i) выполняется 10 раз, а цикл j должен выполняться 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9 раз.Теперь вы просто сложите эти числа, чтобы увидеть, сколько раз работает внутренний цикл.Вы можете суммировать числа от 0 до N-1 по формуле N (N-1) / 2.Это очень небольшая модификация известной формулы для сложения чисел от 1 до N .

Для наглядности вы можете понять, почему 1 + 2 + 3+ ... + n = n * (n + 1) / 2

Answer 4

Если вы посчитаете итерации внутреннего цикла, вы получите:

1 2 3 4 5 6 7 8 9 10

Чтобы получить сумму за произвольное количество итераций, вы можете «обернуть» числа следующим образом:

0 1 2 3 4 
9 8 7 6 5

Теперь, если мы добавим каждый из этих столбцов, все будут добавлены к 9 (N-1), и будет 5 (N / 2) столбцов. Совершенно очевидно, что для любого четного N мы все равно получим N / 2 столбцов, каждый из которых суммируется с (N-1). Таким образом, когда общее число итераций четное, общее количество итераций всегда (N / 2) (N-1), которое (благодаря коммутативному свойству) мы можем переписать как N ( N-1) /2.

Если бы мы делали то же самое для нечетного числа итераций, у нас был бы один «нечетный» столбец, который не мог быть связан. В этом случае мы можем игнорировать «0», так как мы знаем, что это не повлияет на общую сумму в любом случае. Например, давайте рассмотрим N = 9 вместо N = 10. За это получаем:

1 2 3 4
8 7 6 5

Это дает нам (N-1) / 2 столбца (9-1 = 8, 8/2 = 4), каждый из которых складывается в N, поэтому сумма будет N * (N-1) / 2. Хотя мы пришли к этому немного по-другому, это точное совпадение с формулой выше, когда N чётно. Опять же, кажется довольно очевидным, что это останется верным независимо от количества используемых столбцов (т. Е. Общего числа итераций).

Для любого N (нечетного или четного) сумма чисел от 0 до N-1 равна N * (N-1) /2.