Помогите пожалуйста с++

Question

Помогите пожалуйста с++

leyla nuriyeva Ученик (75), на голосовании 2 дня назад

Перечислите все разбиения целого положительного числа N на целые положительные слагаемые. Разбиения должны обладать следующими свойствами: • Слагаемые в разбиениях идут в невозрастающем порядке. • Разбиения перечисляются в лексикографическом порядке. Входные данные 4
Результат работы
1 1 1 1
2 1 1
2 2
3 1
4

Answer 1

Перечислить все разбиения целого положительного числа N на целые положительные слагаемые с указанными свойствами можно с помощью онлайн-калькулятора на сайте planetcalc.ru. Он выводит все представления числа n в виде суммы положительных целых чисел, при этом слагаемые перечисляются в невозрастающем порядке. 3

Также для решения этой задачи можно использовать рекурсивный алгоритм, например, как тот, что приведён на сайте cyberforum.ru. 2

Пример разбиений для числа 4: 1+1+1+1, 2+1+1, 2+2, 3+1, 4. 15

Важно учитывать, что число разбиений экспоненциально зависит от числа n.

Answer 2

 #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);
}

Answer 3

Можно использовать рекурсивный алгоритм.

Подход:
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; 
}