Развертывание 'm' зависимых циклов

Question

Считайте, что у меня есть следующие вложенные for-loops:

for(i1=1 to n)
   for(i2=1 to i1)
       for(i3=1 to i2)
           for(i4=1 to i3)
               for(i5=1 to i4)
                   count++;

Сколько раз будет count увеличиваться?

Если существует m таких зависимых циклов, как мы можем вычислить значение переменной count?

Answer 1

Вы можете попробовать какое-то число и получить ответ. (в вашем примере возьмите m = 5 вы получите 1,6,21,56,126 для n равно 1,2,3,4,5)

Подсказка - это будет Binomial coefficients C(n,5) (вы можете использовать Онлайн-энциклопедия целочисленных последовательностей , чтобы найти это)

Таким образом, для вложенного цикла m вы получите count, равный C(n+m-1,m) ->, поскольку минимум выбирает элемент m, поэтому первый элемент m в биномиальных коэффициентах m равен 0 - вы можете узнать больше в здесь .

Почему это ответ? это на самом деле математический вопрос, но простое объяснение: проверьте Pascal's triangle - это сумма разностей между числами - ваш случай, каждый цикл принимает сумму обоих верхних - в вашем цикле, каждый делает до верхнего индекса - та же методология