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

Вопрос 1 – в следующем двойном вложенном цикле каким будет финальное значение в 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

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

Вопрос 3. Что вы порекомендуете для решения подобных проблем?

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

Ответ:

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

loops for-loop nested-loops
person Developer    schedule 31.10.2011    source источник
comment
Это действительно математический вопрос. sum(1 ≤ i ≤ n-2) sum(i+1 ≤ j ≤ n-1) sum(j+1 ≤ k ≤ n) 1. Следующий шаг — обратиться к вашему любимому учебнику по дискретной математике. Первая рекомендация для решения подобных задач — прийти на прием к профессору.   -  person Raymond Chen    schedule 31.10.2011
comment
@everybody: я решил проблему и нашел ответ, который искал, и указал выше в вопросе. Это на языке Python. Не стесняйтесь использовать его в любом случае без ограничений!   -  person Developer    schedule 31.10.2011

Ответы (2)


arrow_upward
2
arrow_downward

Q3: Найдите закономерность в вопросе.

Вопрос 2. Предположим, что 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: Вы сами догадываетесь об этом. Подсказка: это суммирование сумм...

person Cambium    schedule 31.10.2011
comment
Вопрос был решен спрашивающим, и ответ можно найти в вопросе. - person Developer; 31.10.2011
comment
@Cambium, вы совершенно неправильно поняли, так как ответ, который вы дали, нестандартен. - person Developer; 06.01.2012

arrow_upward
0
arrow_downward

Ответ:

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

f

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

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
person Developer    schedule 31.10.2011