Présentation de la simulation
La simulation est une technique fondamentale en informatique, souvent la première rencontrée par les étudiants en algorithmique. Sa difficulté peut varier considérablement, allant de problèmes simples comme « A+B » ou « Arbres devant l'école » à des défis complexes tels que « Porc Killer » ou « Batialle spatiale sur la planète Luanxi ». Cet article introduit la simulation dans le contexte des algorithmes et structures de données.
Concept de base
L'idée centrale de la simulation consiste à reproduire fidèlement le processus décrit par un problème pour obtenir le résultat attendu. Prenons l'exemple du problème [CSP-S 2023] Serrure à code :
Un cadenas possède cinq rouleaux numérotés de 0 à 9. Chaque rouleau fonctionne en cycle : un déplacement depuis 9 peut mener à 0 ou 8. Le propriétaire adopte une méthode de verrouillage simple : à partir du code correct, il effectue un seul mouvement aléatoire, soit en tournant un seul rouleau d'une certaine amplitude, soit en tournant simultanément deux rouleaux adjacents de la même amplitude. Par exemple, l'état « 0 0 1 1 5 » peut devenir « 1 1 1 1 5 », mais pas « 1 2 1 1 5 ». Après un certain temps, il consigne les n états observés (tous différents du code correct). L'objectif est de déterminer combien de codes corrects potentiels peuvent générer l'ensemble de ces n états via sa méthode de verrouillage.
Puisque le cadenas n'a que cinq chiffres, il est possible de tester tous les codes possibles (de 00000 à 99999). Pour chaque code candidat, on vérifie s'il peut produire chaque état observé en un seul mouvement valide. Un mouvement est valide s'il implique au plus un changement d'un seul chiffre, ou deux changements adjacents avec une amplitude identique. L'approche directe consiste à itérer sur tous les codes et compter ceux qui satisfont toutes les contraintes.
#include <iostream>
#include <vector>
using namespace std;
bool verifier(int code[], int etat[]) {
int differences = 0;
int position = -1;
for (int i = 0; i < 5; i++) {
if (code[i] != etat[i]) {
differences++;
position = i;
if (differences > 2) return false;
}
}
if (differences == 0) return false; // Aucun changement
if (differences == 1) return true; // Un seul chiffre modifié
if (differences == 2) {
// Vérifier si les deux chiffres sont adjacents
if (position == 0 || (position == 1 && code[0] == etat[0]) ||
(position == 4 && code[3] == etat[3]) ||
(position > 1 && position < 4 && code[position-1] == etat[position-1])) {
return false; // Les chiffres changés ne sont pas adjacents
}
// Calculer les amplitudes
int ampl1 = (code[position] - etat[position] + 10) % 10;
int ampl2 = (code[position-1] - etat[position-1] + 10) % 10;
return ampl1 == ampl2; // Les amplitudes doivent être égales
}
return false; // Plus de deux différences
}
int main() {
int n;
cin >> n;
vector<vector cin="" etats="" for="" i="0;" j="0;" n="" vector="">> etats[i][j];
}
}
int total = 0;
for (int d0 = 0; d0 < 10; d0++) {
for (int d1 = 0; d1 < 10; d1++) {
for (int d2 = 0; d2 < 10; d2++) {
for (int d3 = 0; d3 < 10; d3++) {
for (int d4 = 0; d4 < 10; d4++) {
int code[] = {d0, d1, d2, d3, d4};
bool valide = true;
for (int i = 0; i < n; i++) {
if (!verifier(code, etats[i].data())) {
valide = false;
break;
}
}
if (valide) total++;
}
}
}
}
}
cout << total << endl;
return 0;
}
</vector>
Le code ci-dessus illustre une implémentation directe, où la logique suit pas à pas la description du problème.
Problèmes avancés
Les simulations plus complexes nécessitent une attention accrue aux détails. Un exemple classique est le calcul des probabilités dans le jeu de poker Texas Hold'em :
Dans une partie de Texas Hold'em, deux joueurs ont chacun deux cartes privées, et trois cartes communes sont révélées. Deux cartes communes supplémentaires restent cachées. L'objectif est de calculer la probabilité de victoire pour le premier joueur, en tenant compte de toutes les combinaisons posssibles des deux cartes restantes. Les mains de poker sont évaluées selon des règles standard (quinte flush royale, quinte flush, carré, etc.).
La résolution repose sur l'énumération exhaustive de toutes les combinaisons possibles des deux cartes manquantes. Pour chaque combinaison, on détermine la meilleure main pour chaque joueur parmi les sept cartes disponibles (cinq communes plus deux privées), puis on compare les mains. Le rapport entre le nombre de victoires et le total des combinaisons donne la probabilité.
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
struct Carte {
int couleur; // 0:Pique, 1:Coeur, 2:Carreau, 3:Trèfle
int valeur; // 2-14 (14 pour As)
};
map<pair<int, int>, bool> cartes_utilisees;
bool operator==(const Carte& a, const Carte& b) {
return a.couleur == b.couleur && a.valeur == b.valeur;
}
int evaluer_main(vector<Carte>& main) {
// Logique simplifiée pour évaluer la main
// Retourne un score représentant la force de la main
// ... (implémentation détaillée omise pour brièveté)
return 0; // Placeholder
}
int main() {
vector<Carte> joueur1, joueur2, communes;
// Lire les cartes (exemple simplifié)
// ...
int victoires = 0, total = 0;
for (int c1 = 0; c1 < 4; c1++) {
for (int v1 = 2; v1 <= 14; v1++) {
for (int c2 = 0; c2 < 4; c2++) {
for (int v2 = 2; v2 <= 14; v2++) {
Carte carte1 = {c1, v1};
Carte carte2 = {c2, v2};
if (cartes_utilisees[{c1, v1}] || cartes_utilisees[{c2, v2}] || (c1 == c2 && v1 == v2))
continue;
total++;
vector<Carte> toutes_communes = communes;
toutes_communes.push_back(carte1);
toutes_communes.push_back(carte2);
// Évaluer la meilleure main pour chaque joueur
int score1 = evaluer_main(toutes_communes, joueur1);
int score2 = evaluer_main(toutes_communes, joueur2);
if (score1 > score2) victoires++;
}
}
}
}
double probabilite = (double)victoires / total;
cout << probabilite << endl;
return 0;
}
La difficulté réside dans la traduction des règles du jeu en code fiable. Une pratique régulière permet de maîtriser ces aspects.
Exercices pratiques
- Problème [CSP-S 2023] Structure
- Problème [THUPC 2023 Qualification] Bataille spatiale sur la planète Luanxi