nicknamecsharp
@nicknamecsharp

Как работает этот рекурсивный алгоритм разложения на слагаемые?

Помогите, пожалуйста, разобраться с принципом работы алгоритма, самому вникнуть не выходит
#include <iostream>
#include <vector>

int ans = 0;

void f(int n, int maxx, std::vector<int> vv) {
    if (n == 0) {
        ans++;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (i <= maxx) {
            vv.push_back(i);
            f(n - i, i, vv);
            vv.pop_back();
        }
    }
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> v;
    f(n, n, v);
    std::cout << ans;
}
  • Вопрос задан
  • 735 просмотров
Решения вопроса 2
gzhegow
@gzhegow
aka "ОбнимиБизнесмена"
Алгоритм и вправду написан "чудесно", поди разбери.

Но логика такая.
Берем цифру 5.
Её можно получить как
1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1
2 + 2 + 1
3 + 1 + 1
3 + 2
4 + 1
(остальные - повторы)

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

При этом в векторе `vv`, в месте где `ans++` происходит, содержится один набор слагаемых, а `ans` в конце скрипта пишет число возможных комбинаций.
Ответ написан
Комментировать
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Функция генерирует все разбиения числа n на слагаемые не больше maxx. Ддя этого ыункуия перебирает, а какое же максимальное число будет в разбиении (цикл по i), берет это число и рекурсивно разбивает оставшуюся часть. Обратите внимание, в качестве maxx в рекурсии передается i. Ведь именно это было максимальное число в перебираемом разбиении. Значит следующее не может его превышать.

Вся эта сложность с максимальным числом сделана, что бы не перебирать перестановки слагаемых. Ведь 4=1+2+1 можно по идее получить тремя способами, меняя порядок. Генерируя слагаемые в не возрастающем прядке, мы избавляемся от таких дубликатов.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы