Как упростить этот цикл?

Question

Учитывая массив a[i], i=0,1,...,g, где g может быть любым заданным числом и a[0]=1.

for a[1]=a[0]+1 to 1 do 
    for a[2]=a[1]+1 to 3 do 
     for a[3]=a[2]+1 to 5 do 
     ... 
      for a[g]=a[g-1]+1 to 2g-1 do 
       #print a[1],a[2],...a[g]# 

Проблема заключается в том, что каждый раз, когда мы изменяем значение g, нам нужно изменить код, эти петли выше. Это не хороший код.

Answer 1

Рекурсия - это один из способов решить эту проблему (хотя я был рад видеть итеративное решение).

!!! Предупреждение, непроверенный код ниже !!!

template<typename A, unsigned int Size> 
void recurse(A (&arr)[Size],int level, int g) 
{ 
    if (level > g) 
    { 
    // I am at the bottom level, do stuff here 
    return; 
    } 

    for (arr[level] = arr[level-1]+1; arr[level] < 2 * level -1; arr[level]++) 
    { 

     recurse(copy,level+1,g); 
    } 
} 

Тогда звоните с recurse(arr,1,g);

Answer 2

Я бы сказал, что вы не хотите, вложенные циклы, в первую очередь. Вместо этого, вы просто хотите, чтобы вызвать соответствующую функцию, принимая текущий уровень вложенности, максимальный уровень вложенности (т.е. g), начало цикла, и независимо от того, если потребности в качестве контекста для вычисления в качестве аргументов:

void process(int level, int g, int start, T& context) { 
    if (level != g) { 
     for (int a(start + 1), end(2 * level - 1); a < end; ++a) { 
      process(level + 1, g, a, context); 
     } 
    } 
    else { 
     computation goes here 
    } 
} 

Answer 3

Представьте, что вы представляете числа с массивом цифр. Например, 682 будет [6,8,2].

Если вы хотите считать от 0 до 999 можно было бы написать:

for (int n[0] = 0; n[0] <= 9; ++n[0]) 
    for (int n[1] = 0; n[1] <= 9; ++n[1]) 
     for (int n[2] = 0; n[2] <= 9; ++n[2]) 
      // Do something with three digit number n here 

Но если вы хотите, чтобы сосчитать до 9999 вам нужен дополнительный цикл.

Вместо этого вы используете процедуру добавления 1 к числу: приращение последней цифры, если она переполняется, переходят к предыдущей цифре и так далее. Ваша петля завершается, когда первая цифра переполняется. Это обрабатывает числа с любым количеством цифр.

Вам нужна аналогичная процедура для добавления «1» к вашим переменным цикла.

Приращение окончательной «цифры», то есть a[g]. Если он переполняется (т. Е. Превышает 2g-1), перейдите к следующей наиболее значимой «цифре» (a[g-1]) и повторите. Небольшое усложнение по сравнению с этим с числами состоит в том, что, возвращаясь через массив в качестве переполнения значений, вам нужно идти вперед, чтобы сбросить переполненные цифры до их новых базовых значений (которые зависят от значений слева).

Следующий код C# реализует оба метода и печатает массивы на консоли.

static void Print(int[] a, int n, ref int count) 
{ 
    ++count; 
    Console.Write("{0} ", count); 
    for (int i = 0; i <= n; ++i) 
    { 
     Console.Write("{0} ", a[i]); 
    } 
    Console.WriteLine(); 
} 

private static void InitialiseRight(int[] a, int startIndex, int g) 
{ 
    for (int i = startIndex; i <= g; ++i) 
     a[i] = a[i - 1] + 1; 
} 

static void Main(string[] args) 
{ 
    const int g = 5; 

    // Old method 
    int count = 0; 
    int[] a = new int[g + 1]; 
    a[0] = 1; 
    for (a[1] = a[0] + 1; a[1] <= 2; ++a[1]) 
     for (a[2] = a[1] + 1; a[2] <= 3; ++a[2]) 
      for (a[3] = a[2] + 1; a[3] <= 5; ++a[3]) 
       for (a[4] = a[3] + 1; a[4] <= 7; ++a[4]) 
        for (a[5] = a[4] + 1; a[5] <= 9; ++a[5]) 
         Print(a, g, ref count); 

    Console.WriteLine(); 
    count = 0; 

    // New method 

    // Initialise array 
    a[0] = 1; 
    InitialiseRight(a, 1, g); 

    int index = g; 
    // Loop until all "digits" have overflowed 
    while (index != 0) 
    { 
     // Do processing here 
     Print(a, g, ref count); 

     // "Add one" to array 
     index = g; 
     bool carry = true; 
     while ((index > 0) && carry) 
     { 
      carry = false; 

      ++a[index]; 
      if (a[index] > 2 * index - 1) 
      { 
       --index; 
       carry = true; 
      } 
     } 
     // Re-initialise digits that overflowed. 
     if (index != g) 
      InitialiseRight(a, index + 1, g); 
    } 
}