Как рассчитать общее количество итераций самого внутреннего цикла для вложенного цикла? есть ли формула?

Question

например

int count=0
for(int i=0;i<12;i++)
   for(int j=i+1;j<10;j++)
       for(int k=j+1;k<8;k++)
           count++;
System.out.println("count = "+count);

или

for(int i=0;i<I;i++)
   for(int j=i+1;j<J;j++)
       for(int k=j+1;k<K;k++)
        :       
        :
        :
        for(int z=y+1;z,<Z;z,++,)
         count++;

каково значение count после всей итерации? Есть ли формула для его расчета?

Answer 1

Это математическая задача суммирования

В принципе, можно доказать, что:

for (i=a; i<b; i++) 
    count+=1 

эквивалентно

count+=b-a

Аналогично,

for (i=a; i<b; i++) 
    count+=i 

эквивалентно

count+= 0.5 * (b*(b+1) - a*(a+1))

Вы можете получить аналогичные формулы, используя, например, wolframalpha (Mathematica Wolfram's)

Эта система будет выполнять символические вычисления для вас, например,

for(int i=0;i<A;i++)
   for(int j=i+1;j<B;j++)
      for(int k=j+1;k<C;k++)
          count++

является запросом Mathematica:

http://www.wolframalpha.com/input/?i=Sum[Sum[Sum[1,{k,j%2B1,C-1}],{j,i%2B1,B-1}],{i,0,A-1}]

Answer 2

Не полный ответ, но когда i, j и k одинаковы (скажем, они все n ), формула будет C(n, nb_for_loops), что может вас уже заинтересовать:)

    final int n = 50;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k+1; l < n; l++) {
                    count++;
                }
            }
        }
    }
    System.out.println( count );

даст 230300, что составляет C (50,4).

Вы можете легко вычислить это с помощью коэффициента binomail:

http://en.wikipedia.org/wiki/Binomial_coefficient

Одна формулачтобы вычислить это: n! / (k! * (n-k)!)

Например, если вы хотите узнать, сколько разных наборов из 5 карт можно извлечь из колоды из 52 карт, вы можете использовать 5 вложенных циклов или использовать формулу выше, они оба дадут: 2 598 960

Answer 3

Это примерно объем гиперпирамиды http://www.physicsinsights.org/pyramids-1.html => 1 / d * (n ^ d) (с размером d)

Формула работает для действительного числа, поэтому вы должны адаптировать его к целому числу (для случая d = 2 (тогда гиперпирамида представляет собой треугольник), 1/2 * (n * n) становится известной формулой n (n + 1) / 2 (или n (n-1) / 2) в зависимости если вы включите диагональ или нет). Я позволю тебе сделать математику

Я думаю, тот факт, что вы не используете n все время, но я, J, K не проблема, так как вы можете переписать каждый цикл как 2 цикла, останавливающихся посередине, чтобы все они останавливались как одно и то же число

формула может стать 1 / d * ((n / 2) ^ d) * 2 (я не уверен, но что-то подобное должно быть в порядке)

Это не совсем ответ на ваш вопрос, но я надеюсь, что это поможет найти реальный.