Каково общее количество выполнений вложенных циклов?

Question

Q1 - В следующем цикле с двойным вложением, каким будет окончательное значение в m, если цикл имеет значение для n. Конечно, нежелательно делать цикл и смотреть, что такое m! Поскольку n может быть очень большим!

m = 0
for i = 1 to n-2
   for j = i+1,n-1
       for k = j+1,n
           m += 1

Q2 - Как вы нашли ответ? Я имею в виду, какой алгоритм / метод вы использовали для решения проблемы?

Q3 - Что вы посоветуете для решения подобных проблем?

---

Вот ответ, который я искал:

Ответ:

def ntn(n,k):
    """returns the number of iterations for k nested dependent loops(n)"""
    return long(np.prod(n-np.arange(k,dtype=float)) / 
                np.prod(np.arange(k,dtype=float)+1))

пример:

>>> ntn(1000,4)
41417124750L

>>> ntn(1e20,3)
166666666666666650797607483335462097315368077619447843520512L

Answer 1

Q3: найдите образец для вопроса.

Q2: Предполагается, n:=10

Обратите внимание, что i будет повторяться с 1 to 8

Следовательно, j будет повторяться с

2 to 9
3 to 9
...
9 to 9

Следовательно, k будет цикл с

             loops                                        value             index
3 to 10, 4 to 10, 5 to 10, ..., 10 to 10          8 + 7 + 6 + ... + 1         8
         4 to 10, 5 to 10, ..., 10 to 10              7 + 6 + ... + 1         7
                  5 to 10, ..., 10 to 10                  6 + ... + 1         6
                           ...      ...                           ...       ...
                                10 to 10                            1         1

Обратите внимание на шаблон здесь: если мы начинаем индекс с нижнего числа (1), чтобы получить m -ое число в последовательности, вы просто суммируете от 1 до m.

Q1: Вы решаете это самостоятельно. Подсказка: это суммирование сумм ...

Answer 2

Ответ:

Формула комбинации выглядит следующим образом:

может быть использовано для этой цели. В Python в пакете scipy есть функция comb(), которую тоже можно использовать. Однако следующее решение гораздо более гибкое и быстрое, а полученные цифры намного длиннее.

import numpy as np

def ntn(n,k):
    """returns the number of iterations for k nested dependent loops(n)"""
    return long(np.prod(n-np.arange(k,dtype=float)) / 
                np.prod(np.arange(k,dtype=float)+1))

Примеры:

>>> ntn(1000,4)
41417124750L

>>> ntn(1e20,3)
166666666666666650797607483335462097315368077619447843520512L