Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

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

 

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
Entrée du programmeSortie du programme
34
410
408166103632745757696

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

  •  {1}, {2}, {3}
  •  {1, 2}, {3}
  •  {1, 3}, {2}
  •  {1}, {2, 3}
Le nombre d'étudiants ne dépassera pas 50

Solution 1 (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 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é.

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.

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)

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.