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

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.

  Exemples

Pour 3 étudiants les binômes sont listés ci-dessous :

•  {1}, {2}, {3}
•  {1, 2}, {3}
•  {1, 3}, {2}
•  {1}, {2, 3}

Le problème peut être résolu avec la récursivité en considérant les choix que nous avons pour le nième étudiant. Pour le nième étudiant,

•  Le nième étudiant reste seul, et nous récurons pour les (n-1) étudiants restants.
•  Le nième étudiant se met en binome avec n'importe lequel des (n - 1) élèves restants, puis nous récurons pour les (n-2) étudiants restants. Le nombre de façons de faire est de (n - 1) * Rec(n - 2).

Notez que s'il y a 2 étudiants, il y a 2 façons de les regrouper, et pour un seul étudiant, il n'y a qu'une seule façon de les regrouper. Donc pour n <= 2, la réponse sera 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;
}
                    

Complexité :

•  Complexité temporelle : exponentielle
•  Complexité spatiale : O(1) si l'espace de la pile de récursivité est ignoré.

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.

def CompterGroupes(n):
    dp= [0 for i in range(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[-1]


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

Complexité :

•  Complexité temporelle : O(n)
•  Complexité spatiale : O(n)