Задача 7: Разбиение на невозрастающие слагаемые, лексикографический порядок

Условие задачи:

Дано натуральное число \(N\). Рассмотрим его разбиение на натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых, будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.

Входные данные:

Задано единственное число \(N (N ≤ 40)\).

Выходные данные:

Необходимо вывести все разбиения числа \(N\) на натуральные слагаемые в лексикографическом порядке.

Решение:

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int n, k, ans;
vector <int> rez;


void f(int i, int s, int m){
    if (i == n){
        if (s == n){
            for(auto e: rez){
                if (e) {
                    cout << e << " ";
                }
            }
            cout << endl;
            ans += 1;
        }
        return;
    }
    if (n - s < m){
        for (int j = 0; j < n - s + 1; j++){
            rez[i] = j;
            f(i + 1, s + rez[i], rez[i]);
        }
    } else {
        for (int j = 0; j < m + 1; j++){
            rez[i] = j;
            f(i + 1, s + rez[i], rez[i]);
        }
    }
}

int main()
{
    cin >> n;
    rez.resize(n);
    f(0, 0, n);
    return 0;
}

Задача 7: Разбиение на невозрастающие слагаемые, лексикографический порядок

Условие задачи:

Входные данные:

Выходные данные:

Решение:

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик

Пожалуйста, подождите загрузки решения