Помогите пожалуйста с++
Перечислите все разбиения целого положительного числа N на целые положительные слагаемые. Разбиения должны обладать следующими свойствами: • Слагаемые в разбиениях идут в невозрастающем порядке. • Разбиения перечисляются в лексикографическом порядке. Входные данные 4
Результат работы
1 1 1 1
2 1 1
2 2
3 1
4
#include <iostream>
#include <vector>
using namespace std;
void f(vector<int> &t, int n, int end) {
if (n == 0) {
for (auto v: t) { cout << v << ' '; }
cout << '\n';
return;
}
int pos = t.size();
t.resize(pos + 1);
end = min(end, n);
for (t[pos] = 1; t[pos] <= end; ++t[pos]) {
f(t, n - t[pos], t[pos]);
}
t.resize(pos);
}
int main() {
int n;
cin >> n;
vector<int> t;
t.reserve(n);
f(t, n, n);
} Можно использовать рекурсивный алгоритм.
Подход:
1) Используем рекурсивную функцию для построения разбиений.
Невозрастающий порядок: Каждый следующий слагаемый должен быть меньше или равен предыдущему.
2) Для обеспечения лексикографического порядка будем перебирать первые элементы от 1 до N.
Алгоритм:
Начинаем с пустого разбиения, остатка суммы равного N, и максимального возможного слагаемого, равного N.
Если остаток суммы равен 0, выводим текущее разбиение.
Иначе, для каждого возможного слагаемого от 1 до минимального из текущего остатка суммы и предыдущего слагаемого:
1) Добавляем слагаемое в текущее разбиение.
2) Рекурсивно вызываем функцию с обновленным остатком суммы и текущим слагаемым как новым предыдущим слагаемым.
3) Удаляем слагаемое из текущего разбиения (backtracking).
В итоге разбиения выводятся в процессе рекурсивных вызовов, обеспечивая требуемый порядок
Реализация на c++:
#include <iostream>
#include <vector>
using namespace std;
void partition(int remaining_sum, int last_element, vector<int>& partition_so_far) {
if (remaining_sum == 0) {
for (size_t i = 0; i < partition_so_far.size(); ++i) {
cout << partition_so_far[i];
if (i + 1 < partition_so_far.size()) cout << " ";
}
cout << endl;
return;
}
for (int first_element = 1; first_element <= min(remaining_sum, last_element); ++first_element) {
partition_so_far.push_back(first_element);
partition(remaining_sum - first_element, first_element, partition_so_far);
partition_so_far.pop_back();
}
}
int main() {
int N;
cin >> N;
vector<int> partition_so_far;
partition(N, N, partition_so_far);
return 0;
} Перечислить все разбиения целого положительного числа N на целые положительные слагаемые с указанными свойствами можно с помощью онлайн-калькулятора на сайте planetcalc.ru. Он выводит все представления числа n в виде суммы положительных целых чисел, при этом слагаемые перечисляются в невозрастающем порядке. 3
Также для решения этой задачи можно использовать рекурсивный алгоритм, например, как тот, что приведён на сайте cyberforum.ru. 2
Пример разбиений для числа 4: 1+1+1+1, 2+1+1, 2+2, 3+1, 4. 15
Важно учитывать, что число разбиений экспоненциально зависит от числа n.
