Clasa a XI-a · Programare dinamicăRead in English

Numărul partițiilor unui număr în C++

În engleză: Number of partitions of a number

O(n²)C++1741 de linii2 exemple

Ideea

În câte moduri se poate scrie n ca sumă de numere naturale nenule, fără să conteze ordinea termenilor? (4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1, deci 5.) Backtracking-ul le-ar enumera pe toate; aici doar le numărăm. Introducem pe rând termenii posibili t = 1, 2, ..., n. nr[s] este numărul de moduri de a scrie s folosind doar termenii introduși până acum; când adăugăm termenul t, nr[s] += nr[s - t] (pentru s crescător, ca t să poată fi folosit de mai multe ori). Inițial nr[0] = 1.

Descrierea în engleză

In how many ways can n be written as a sum of non-zero natural numbers, where the order of the terms does not matter? (4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1, so 5.) Backtracking would enumerate them all; here we only count them. We introduce the possible terms t = 1, 2, ..., n one at a time. nr[s] is the number of ways to write s using only the terms introduced so far; when we add the term t, nr[s] += nr[s - t] (for increasing s, so that t can be used several times). Initially nr[0] = 1.

Complexitate
O(n²) timp, O(n) memorie
Clasa
Clasa a XI-a (Grade 11)

Exemple

Exemplul 1

Intrare

5

Ieșire așteptată

7
Exemplul 2

Intrare

10

Ieșire așteptată

42

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

numarul-partitiilor.cpp
/*
 * Titlu: Numărul partițiilor unui număr
 * Clasa: 11
 * Capitol: Programare dinamică
 * Descriere: În câte moduri se poate scrie n ca sumă de numere naturale nenule, fără să
 *            conteze ordinea termenilor? (4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1, deci 5.)
 *            Backtracking-ul le-ar enumera pe toate; aici doar le numărăm. Introducem
 *            pe rând termenii posibili t = 1, 2, ..., n. nr[s] este numărul de moduri de a
 *            scrie s folosind doar termenii introduși până acum; când adăugăm termenul t,
 *            nr[s] += nr[s - t] (pentru s crescător, ca t să poată fi folosit de mai multe
 *            ori). Inițial nr[0] = 1.
 * Complexitate: O(n²) timp, O(n) memorie
 *
 * Exemplu
 * Intrare: 5
 * Ieșire: 7
 *
 * Exemplu
 * Intrare: 10
 * Ieșire: 42
 */
#include <iostream>
using namespace std;

int main()
{
    int n;
    long long nr[205] = {0};
    cin >> n;
    nr[0] = 1;
    for (int t = 1; t <= n; t++)
    {
        for (int s = t; s <= n; s++)
        {
            nr[s] += nr[s - t];
        }
    }
    cout << nr[n] << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.