Нужна помощь с понимаем рекурсивного кода

Информатика
1

Почему вывод при запуске рекурсии с i+1 и index + 1 разный?

#define len(x) (int)x.size()
void rec(v <int> &a, v<int> &subset, v <v<int>> &res, int index) {

    res.push_back(subset);

    for(int i = index; i < len(a); i++) {

        subset.push_back(a[i]);

        rec(a, subset, res, index + 1);

        subset.pop_back();
    }

}

v <v<int>> subsets(v <int> &a) {
    int index = 0;
    v <int> subset;
    v <v<int>> res;

    rec(a,subset, res, index);

    return res;
}


int main()
{

    int n;
    cin >> n;

    v <int> a(n);

    for(auto &i : a)
        cin >> i;

    v <v<int>> res = subsets(a);

    for(int i = 0; i < len(res); i++) {
        for(int j = 0; j < len(res[i]); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    } 
return 0;
}

Вывод для (1,2.3):
1
1 2
1 2 3
1 3
1 3 3
2
2 2
2 2 3
2 3
2 3 3
3
3 2
3 2 3
3 3
3 3 3

А если изменить строчку вызова рекурсии на

rec(a, subset, res, i+1);

Вывод становится правильным:
1
1 2
1 2 3
1 3
2
2 3
3

Заранее спасибо

1 лайк
2

Возможно я не прав, но у тебя в функции rec переменная index никак не меняется. Ты просто каждый раз вызываешь функцию с одинаковой переменной index. А если же ты ставишь туда i + 1, то у вызываемой функции будет уже другое число, отличающееся от index.
Все же легче было бы понять твой код если бы ты написал для чего он вообще нужен? Какова задача?

3

Ну, вывод всех подмножеств заданного множества

4

@eudaimon carefully analyze the code above and identify any issues. Answer arthamin’s question as well.

5

@Anton, давайте подробно разберем код и ответим на вопрос @arthamin.

Цель кода - генерация всех возможных подмножеств (powerset) из данного множества элементов. Для достижения этой цели используется рекурсивная функция rec. Она работает следующим образом: начиная с текущего индекса index, функция последовательно добавляет каждый элемент во временное подмножество subset, рекурсивно вызывает себя для генерации подмножеств, начиная с следующего индекса, а затем удаляет последний добавленный элемент, чтобы продолжить с следующим элементом в исходном массиве.

Проблема с index + 1

Использование index + 1 в рекурсивном вызове rec(a, subset, res, index + 1); приводит к тому, что каждый рекурсивный вызов начинается с индекса, следующего за индексом первого вызова рекурсии, а не следующего за индексом текущего элемента. Это приводит к неправильной генерации подмножеств, так как некоторые элементы пропускаются или неправильно повторяются в процессе создания подмножеств.

Правильное использование i + 1

Изменение строки вызова рекурсии на rec(a, subset, res, i+1); исправляет проблему, так как в этом случае для каждого нового рекурсивного вызова устанавливается индекс, следующий за индексом текущего элемента. Это обеспечивает корректное продвижение по множеству и генерацию всех возможных подмножеств без повторений и пропусков.

Ответ на вопрос @arthamin

Разница в выводе при использовании index + 1 и i + 1 обусловлена тем, что index + 1 не позволяет корректно продвигаться по множеству для создания всех возможных подмножеств, ведя к неправильным повторениям и пропускам. В то время как i + 1 корректно увеличивает индекс на каждом шаге рекурсии, позволяя правильно генерировать все подмножества без пропусков и некорректных повторений.

Таким образом, для корректной работы алгоритма по генерации всех подмножеств заданного множества необходимо использовать i + 1 в рекурсивном вызове функции rec. Это позволяет избежать ошибок в выводе и гарантирует получение всех возможных подмножеств без пропусков и повторений.

6

@eudaimon why does he have two variables that seemingly are supposed to achieve the same thing? Can he rewrite the code to avoid this ambiguity?

7

@Anton, действительно, в коде, представленном @arthamin, использование двух переменных (index и i), которые в некотором смысле выполняют похожую функцию, может вызвать путаницу. Обе переменные используются для итерации по элементам массива, но index служит в качестве начальной точки для рекурсии, а i используется для продолжения итерации в каждом уровне рекурсии.

Упрощение кода

Для того чтобы избежать путаницы и сделать код более понятным, можно объединить использование index и i, устраняя необходимость в двух переменных. Это можно сделать, если мы будем использовать только одну переменную для контроля текущего индекса при рекурсивных вызовах. В этом случае, переменная index будет увеличиваться с каждым рекурсивным вызовом, и нет необходимости в дополнительной переменной i.

Исправленный код

#define len(x) (int)x.size()
void rec(v <int> &a, v<int> &subset, v <v<int>> &res, int index) {
    res.pushback(subset);

    for(int current = index; current < len(a); current++) {
        subset.push_back(a[current]);
        rec(a, subset, res, current + 1); // Используем current + 1
        subset.pop_back();
    }
}

v <v<int>> subsets(v <int> &a) {
    int index = 0;
    v <int> subset;
    v <v<int>> res;

    rec(a, subset, res, index);

    return res;
}

int main()
{
    int n;
    cin >> n;

    v <int> a(n);

    for(auto &i : a)
        cin >> i;

    v <v<int>> res = subsets(a);

    for(int i = 0; i < len(res); i++) {
        for(int j = 0; j < len(res[i]); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    } 
    return 0;
}

В этой версии кода, current заменяет i и используется как индекс для текущего элемента в массиве. Это устраняет путаницу, связанную с index и i, и делает код более понятным и лаконичным.

Заключение

Использование одной переменной для контроля индекса в рекурсивной функции делает код более читаемым и уменьшает вероятность ошибок. Это также помогает избежать путаницы при чтении и анализе кода, делая его более доступным для понимания другими разработчиками.

1 лайк