Nombre de façons de regrouper les étudiants - Programmation compétitive

Problème de regroupement — Solo ou Binôme

Lors de la préparation de la première épreuve éliminatoire organisée par les Olympiades Marocaines d'Informatique, le comité donne le choix aux étudiants de travailler seuls ou en binôme avec un autre étudiant.

Le problème se réduit à savoir de combien de manières les étudiants peuvent rester seuls ou en binôme.

Énoncé du problème

Entrée

• Un entier n représentant le nombre d'étudiants.

Sortie

• Le nombre de façons de regrouper les étudiants en solo ou en binômes.

3

4

4

10

40

8166103632745757696

Solution 1 — Approche récursive (Diviser pour régner)

Le problème peut être résolu avec la récursivité en considérant les choix que nous avons pour le n-ième étudiant :

• Cas 1 : Le n-ième étudiant reste seul → on récure pour les (n-1) étudiants restants.
• Cas 2 : Le n-ième étudiant se met en binôme avec n'importe lequel des (n-1) élèves restants, puis on récure pour les (n-2) étudiants restants. Le nombre de façons de faire est (n-1) × Rec(n-2).

si n ≤ 2 → retourner n

def CompterGroupes(n):
    if n <= 2:
        return n
    else:
        return CompterGroupes(n-1) + (n-1) * CompterGroupes(n-2)


n = int(input())
print(CompterGroupes(n))

#include <iostream>
using namespace std;

unsigned long long CompterGroupes(int n)
{
    if (n <= 2) return n;
    else return CompterGroupes(n-1) + (n-1) * CompterGroupes(n-2);
}

int main()
{
    int n;
    cin >> n;
    cout << CompterGroupes(n) << endl;
    return 0;
}

4

Solution 2 — Programmation Dynamique

Puisque la formule récursive ci-dessus (solution 1) a des sous-problèmes qui se chevauchent, nous pouvons la résoudre en utilisant la programmation dynamique.

Illustration des premières valeurs

def CompterGroupes(n):
    # Tableau DP
    dp = [0] * (n + 1)
    
    for i in range(n + 1):
        if i <= 2:
            dp[i] = i
        else:
            dp[i] = dp[i-1] + (i-1) * dp[i-2]
    
    return dp[n]


n = int(input())
print(CompterGroupes(n))

#include <iostream>
using namespace std;

unsigned long long CompterGroupes(int n)
{
    unsigned long long dp[n + 1];
    
    for (int i = 0; i <= n; i++) {
        if (i <= 2)
            dp[i] = i;
        else
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
    
    return dp[n];
}

int main()
{
    int n;
    cin >> n;
    cout << CompterGroupes(n) << endl;
    return 0;
}

8166103632745757696

unsigned long long CompterGroupes(int n) {
    if (n <= 2) return n;
    
    unsigned long long prev2 = 1;  // dp[1]
    unsigned long long prev1 = 2;  // dp[2]
    unsigned long long curr;
    
    for (int i = 3; i <= n; i++) {
        curr = prev1 + (i - 1) * prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    
    return curr;
}