С#: N для циклов

Ответ 1

ОК, вам нужно нерекурсивное решение, которое параметризуется в num и имеет постоянное количество вложенных циклов, да?

Вот эскиз метода, который это делает. Заполнение деталей остается в виде упражнения.

Во-первых, я предполагаю, что у вас есть неизменяемый тип "Вектор", который может быть 0-кортежем, 1-кортежем, 2-кортежем, 3-кортежем,... n-кортежем.

Метод принимает размер вектора и возвращает последовательность векторов такого размера.

IEnumerable<Vector> MakeVectors(int num)
{
    Vector current = new Vector(num); // make an all-zero vector with num items.
    while(true)
    {
        yield return current;
        Vector next;
        bool gotAnother = GetNextVector(current, out next);
        if (!gotAnother) break;
        current = next;
    }
}

Там. Теперь проблема сводилась к двум меньшим проблемам:

1) Для вектора размера num, является ли он последним вектором в последовательности?

2) Если нет, то какой следующий вектор?

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

Имеют смысл?

Ответ 2

Обычно вы используете рекурсию для сценариев, где у вас есть вложенные циклы, где количество вложенных циклов неизвестно во время компиляции. Что-то с идеей:

void func(const vector<int> &times, int depth) {
    if (depth == times.size()) return;
    for (int i = 0; i < times[depth]; ++i) {
        cout << depth;
        func(times, depth + 1);
    }
}

Ответ 3

Принимая ваше слово, что это не домашнее задание, см. ниже:

    public void LoopRecursively(Stack<int> valuesSoFar, int dimensions)
    {
        for (var i = 0; SumOf(valuesSoFar) + i <= dimensions; i++)
        {
            valuesSoFar.Push(i);
            if (valuesSoFar.Count == dimensions)
            {
                Console.WriteLine(StringOf(valuesSoFar));
            }
            else
            {
                LoopRecursively(valuesSoFar, dimensions);
            }
            valuesSoFar.Pop();
        }
    }

    private int SumOf(IEnumerable<int> values)
    {
        return values.Sum(x => x);
    }

    private string StringOf(IEnumerable<int> values)
    {
        return string.Join(" ", values.Reverse().Select(x => x.ToString()).ToArray());
    }

Ответ 4

В качестве альтернативы манипулированию цифрами отдельно, как это делается в рекурсивных решениях и тех, которые используют Vector < > , вы можете положиться на представления машин и арифметику. Это не так быстро, если вам нужно каждый раз проверять каждую цифру в цикле, но если вы выполняете итератор, это уменьшит пространство для хранения в итераторе, и если вы не используете каждое значение, оно может также повысить эффективность. В любом случае, это интересный эквивалентный подход. Здесь идет...

Сначала подумайте о более общем случае, когда у вас есть n вложенные циклы, каждый из которых отсчитывается от 0 до num. В этом случае вы, по существу, просто считаете от 0 до num^n - 1 в базе num. Итак, вы можете сделать что-то вроде этого:

for( int x=0; x<(num^n); x++ )
{
   int digit_0 = x % num;
   int digit_1 = (x/num) % num;
   int digit_2 = (x/num^2) % num;
   // etc.
}

Обратите внимание, что:

• Если собственный тип целого не достаточно велик для вашего приложения, вам придется использовать какой-то большой целочисленный класс. Это уменьшит эффективность элементов хранения и увеличения, хотя, возможно, не так много, как использование вектора длины num.
• Если вы действительно смотрите каждую цифру каждый раз, вам нужен вектор цифр, и вы ничего не получили. Это действительно очень полезно, когда вы не смотрите на все цифры каждый раз.
• Все делители должны быть предварительно вычислены, поэтому вам нужно поддерживать вектор для этого!

В любом случае, для вашего конкретного вопроса, вы не хотели рассчитывать на num каждый раз, вы хотели бы рассчитывать на num - (the sum of the already decided digits). Простейший способ объяснить это просто, поставив соответствующее условие continue в ваши циклы. Здесь есть некоторые значения, подставляемые в, когда n=2 и num=10:

for( x=0; x<100; x++ ) // i.e. x < num*num
{
   int ones = x%10; // i.e. x % num
   int tens = (x/10) % 10; // i.e. (x/num) % num

   if( ones + tens < 10 )
   {
     // actually do work
   }
}

(В случае, если это не очевидно, я не хочу, чтобы вы действительно использовали 100 и 10 в коде, это просто иллюстративный пример.)

Вы можете сделать это более эффективным, вычислив, сколько для увеличения x, или путем уменьшения диапазона x, а затем непосредственно сопоставления с вашим подпространством, а не ко всему пространству. (Но в 2-х и 3-х случаях вы используете ровно половину возможных значений, так что дополнительная работа приведет только к ускорению 2. Я думаю, что это то же самое, когда n > 3, но я слишком ленив, чтобы понять это прямо сейчас, извините!)