Из рекурсии в итерацию

[Вероника99]

Здравствуйте. Помогите разобраться как в следующей программе сделать вместо рекурсивной функции - итерационную. Программа выводит последовательности длинно k, полученные с чисел 1,2 ...n.

int n, k;
bool mas[200];
 
 
void func(int lst, int cnt)
{
    if(cnt == k) 
    {
        for(int i = 0; i <n; i++) 
        {
            if(mas[i])
            {
                cout << i+1 << " ";
            }
        }
        cout << endl;
        return;
    }
 
    if(lst + 1 >= n) 
    {
        return;
    }
 
    mas[lst + 1] = true;
    func(lst + 1, cnt + 1);
 
    mas[lst + 1] = false;
    func(lst + 1, cnt);
    return;
}

Как параметры в рекурсию передаются func(-1, 0);
Спасибо

[GreenWizard]

скинь исходную задачу т. к. код такой, что.... кхм... у меня вон проект на 20+ solutions и то проще понять
если же тебе оно реально нужно, а не лишь бы сдать, то попробуй написать рекурсивную версию проще, а потом на иттеративную перенесёшь.

[Вероника99]

Это сочетания (Сочетаниями из n элементов по k называются соединения, которые можно образовать из n элементов, собирая в каждое соединение k элементов; ). Результат на скрине. Вроде как должны быть циклы:

for (int i = 1; i <= n-k+1; i++) {
    for (int j = 0; j < k; j++) {
        cout <<i+j <<" ";
    }
    cout <<"\n";
}

Но нужно добавить условия проверки, я по этой рекурсии я не понимаю,как их внедрить в итерацию.

[Вероника99]

Не подскажите?

[GreenWizard]

Тут не программирование, а математика, ещё и мутная..... всем лень)
Сейчас загуглил "вывод сочетаний код" и нашёл, например, весьма хороший сборник по комбинаторике... почитай, там твоя задача, вроде, есть

[evg_m]

http://programmersforum.ru/showthrea...F0%E5%E1%EE%F0
Это не С, и не совсем число сочетаний (нет требования различности элементов).
Но перебор и с помощью циклов (итераций).

[Вероника99]

Сообщение от Вероника99

mas[lst + 1] = true;
func(lst + 1, cnt + 1);

mas[lst + 1] = false;
func(lst + 1, cnt);

}
[/CODE]

Проблема в том,что я не понимаю принцип этой рекурсии, а именно строки,
которые я выделила. Что это может значить? mas[lst + 1] присваивается истина, потом вызывается функция func(lst + 1, cnt + 1);, а при каких услових вызывается func(lst + 1, cnt);. Вообще не понимаю

[GreenWizard]

Сообщение от Вероника99

Проблема в том,что я не понимаю принцип этой рекурсии, а именно строки,
которые я выделила. Что это может значить? mas[lst + 1] присваивается истина, потом вызывается функция func(lst + 1, cnt + 1);, а при каких услових вызывается func(lst + 1, cnt);. Вообще не понимаю

Пардон за мой французский, но говно это редкостное.... думал это ты написала, поэтому предложил переписать более вменяемо.
Смысл в том что при func(lst + 1, cnt + 1) у нас mas[lst + 1] = true, а в др. случаях - false.... оно, конечно, смысл имеет, это часть того самого префикса, пусть и в скрытом виде, НО лучше забить и написать\найти иттеративный вариант с нуля

[evg_m]

mas[] массив признаков использования чисел [0... n-1] +1 для генерации (вывода) последовательности

 if(mas[i]) 
            {
                cout << i+1 << " ";

lst подставляемое число 0..n
мы всегда имеем ДВА варианта (использовать/неиспользовать) данное число

mas[lst + 1] = true;
func(lst + 1, cnt + 1); // выполнить "спуск" с УВЕЛИЧЕНИЕМ (cnt+1) числа использованных чисел

mas[lst + 1] = false;
func(lst + 1, cnt ); // выполнить "спуск" БЕЗ увеличения (cnt) числа использованных

    if(cnt == k)  //МЫ набрали нужное нам количество чисел для вывода 

    if(lst + 1 >= n)  // МЫ перебрали ВСЕ допустимые числа

[ura_111]

Обычно в рекурсии используется один вызов функции. Но два...

Ну, попробуй нарисовать "всю работу программы" - может что-то прояснится. Типа такого (красный цвет - это вызов рекурсивной функции, а синяя- возврат):

132.jpg

Как ты видишь два вывода рекурсии резко увеличивает сложность задачи. Легче не имитировать этот кусок кода, а "придумывать" с нуля.