Пожалуйста, рассмотрите следующую тройную вложенную петлю:
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
for (int k = j; k <= n; ++k)
// statement
Здесь утверждение выполняется ровно раз Может кто-нибудь объяснить, как эта формула была получена? Спасибо.
Ответы:
Вы можете подсчитать, сколько раз выполняется самый внутренний цикл for, подсчитывая количество триплетов для которых он выполняется.(i,j,k)
По условиям цикла мы знаем, что: . Мы можем свести его к следующей простой проблеме комбинаторики.1≤i≤j≤k≤n
Итак, нам просто нужно посчитать количество способов выбора 3 блоков из блоков, что составляет ( n + 2n + 2 .( п+23)
источник
для меня легче заметить, что внутренний цикл выполняется раз, а общее количество выполнений во внутреннем циклеn−i
источник