Mise à jour le 30/01/2022 : Ajout initial de la bibliothèque de modèles STL, cette section n'est pas encore complète
Introduction
Cet article présente des syntaxes et techniques pratiques pour la programmation compétitive (OI), adaptée aux participants aux Olympiades d'informatique. Les débutants ou les étudiants en informatique pourraient ne pas trouver cela directement applicable.
Pour plus d'informations ou de références syntaxiques, veuillez consulter http://cplusplus.com.
Pour les participants aux Olypmiades, la CCF (China Computer Federation) prend en charge C++11 pour les compétitions NOI. Cependant, comme la version la plus récente de C++ est C++20, cet article se concentrera sur C++98 et C++11, sans aborder C++14 et C++17.
Table des matières
- Opérations sur les fichiers
- Nombres aléatoires
- Fonction d'attente Sleep
- Bibliothèque de modèles standard (STL)
- Opérations sur les fichiers
Les opérations sur les fichiers sont fréquemment utilisées dans des compétitions comme \(CSP, NOIP\), et sont probablement familières à la plupart des programmeurs.
freopen("entree.txt", "r", stdin);
freopen("sortie.txt", "w", stdout);
Ces deux lignes de code réalisent la redirection des entrées et sorties. entree.txt et sortie.txt sont les noms de fichiers, r signifie lecture seule, w signifie écriture seule, tandis que stdin et stdout représentent l'entrée et la sortie standard du système.
Lorsque nous développons de petits programmes, nous pourr nous demander : freopen peut-il être fermé ? Deux fonctions courentes sont :
fclose(stdin);
fclose(stdout);
Après tests, on constate que ces fonctions ne ferment pas la redirection de freopen et ne rétablissent pas l'entrée clavier et la sortie console.
Examinons le code qui ferme réellement freopen :
#include <bits/stdc++.h>
using namespace std;
int main() {
int val1, val2;
cin >> val1 >> val2;
freopen("entree.txt", "r", stdin);
freopen("sortie.txt", "w", stdout);
cout << val1 << " " << val2 << endl;
freopen("CON", "r", stdin);
freopen("CON", "w", stdout);
cin >> val1 >> val2;
cout << val1 << " " << val2 << endl;
return 0;
}
Ici, CON fait référence à la console.
- Nombres aléatoires
Les nombres générés par la fonction aléatoire standard rand() sont des nombres pseudo-aléatoires, obtenus par le calcul d'une formule à partir d'une graine aléatoire. Si nous exécutons repeatedly le programme suivant, nous constatons que les nombres aléatoires sont identiques :
#include <bits/stdc++.h>
using namespace std;
int main() {
for(int i = 1; i <= 5; i++) {
cout << rand() << endl;
}
return 0;
}
Nous devons donc utiliser la fonction srand() pour changer la graine aléatoire. La méthode la plus simple est d'utiliser le temps comme graine, ce qui garantit que les données sont suffisamment aléatoires :
#include <bits/stdc++.h>
#include <ctime>
using namespace std;
int iterations = 10000;
int main() {
srand(unsigned(time(0)));
for(int i = 1; i <= iterations; i++) {
cout << rand() << endl;
}
return 0;
}
Cependant, nous remarquons que les plages de nombres aléatoires sont trop grandes. Peut-nous spécifier une plage pour les nombres générés ? Comme vous l'avez probablement deviné, nous pouvons utiliser l'opérateur modulo sur les nombres aléatoires !
#include <bits/stdc++.h>
#include <ctime>
using namespace std;
int iterations = 10000, max_val = 10;
int main() {
srand(unsigned(time(0)));
for(int i = 1; i <= iterations; i++) {
cout << rand() % max_val << endl;
}
return 0;
}
Pour vérifier la justesse de notre approche, nous pouvons afficher la probabilité d'apparition de chaque nombre :
Voici le code :
#include <bits/stdc++.h>
#include <ctime>
using namespace std;
int compteur[11], iterations = 100000000, max_val = 11;
int main() {
srand(unsigned(time(0)));
for(int i = 1; i <= iterations; i++) {
int x = rand() % max_val;
compteur[x]++;
}
for(int i = 1; i <= max_val; i++) {
double probabilite = double(compteur[i]) / double(iterations);
printf("La probabilité d'apparition de %d est de %.2lf%%\n", i, probabilite * 100);
}
return 0;
}
- Fonction d'attente Sleep
La fonction d'attente Sleep permet de suspendre l'exécution de la console pendant une période spécifiée L'utilisation est illustrée dans le code suivant :
#include <bits/stdc++.h>
#include <windows.h>
using namespace std;
int main() {
cout<<"Premier message";
Sleep(1000);
system("cls");
cout<<"Deuxième message";
return 0;
}
Cela affichera d'abord "Premier message", attendra 1 seconde, effacera l'écran, puis affichera "Deuxième message".
Notez que la \(S\) de Sleep doit être en majuscule, le fichier d'en-tête est windows.h, et l'unité de temps pour la fonction Sleep est le milliseconde.
- Bibliothèque de modèles standard (STL)
La bibliothèque de modèles standard (Standard Template Library, STL) est un ensemble de logiciels développés par le laboratoire HP. Elle a été créée par Alexander Stepanov, Meng Lee et David R Musser alors qu'ils travaillaient au laboratoire HP. Bien qu'elle soit principalement associée à C++, cette technologie existait déjà bien avant son introduction dans le langage. Le code de la STL se divise en trois catégories : algorithmes (algorithm), conteneurs (container) et itérateurs (iterator). Presque tout le code utilise des classes et fonctions templates, offrant ainsi de meilleures opportunités de réutilisation du code par rapport aux bibliothèques traditionnelles composées de fonctions et de classes.
4.1.vector
Tableau de longueur variable.
Définition : vector<type_donnees> nom
push_back(x) : ajoute un élément pop_back() : supprime le dernier élément size() : taille du tableau begin() : pointeur vers le premier élément end() : pointeur vers l'élément suivant le dernier élément
4.2.queue
File d'attente, souvent utilisée pour les algorithmes BFS.
Définition : queue<type_donnees> nom
size() : taille de la file empty() : vérifie si la file est vide front() : premier élément de la file pop() : supprime le premier élément push(x) : ajoute un élément à la fin de la file
4.3.priority_queue
File de priorité, souvent utilisée pour les algorithmes de plus court chemin.
Définition : priority_queue<type_donnees> nom
size() : taille de la file empty() : vérifie si la file est vide * top() : élément de plus haute priorité pop() : supprime l'élément de plus haute priorité push(x) : ajoute un élément à la file
* : Différence avec la file d'attente standard queue.
4.4.stack
Pile, souvent utilisée pour les algorithmes DFS.
Définition : stack<type_donnees> nom
size() : taille de la pile top() : élément au sommet de la pile pop() : supprime l'élément au sommet push(x) : ajoute un élément au sommet de la pile
4.5.map
Dictionnaire, comme son nom l'indique, permet des fonctiosn de recherche de type dictionnaire, stockant les données sous forme de paires clé-valeur, similaire à un tableau où les indices et les valeurs sont des types personnalisés.
Définition : map<type_clé, type_valeur> nom
Trois méthodes d'insertion :
nom.insert(pair<type_clé, type_valeur>(clé,valeur));nom.insert(map<type_clé, type_valeur>::value_type(clé,valeur));nom[clé] = valeur
Recherche d'élément : nom.find(clé). Si le résultat n'est pas égal à nom.end(), l'élément a été trouvé. La fonction renvoie un pointeur vers cet élément, dont la valeur peut être obtenue avec ->second. Si l'élément n'est pas trouvé, la fonction renvoie la valeur de nom.end().
- begin() : retourne un itérateur pointant vers le début du map
- clear() : supprime tous les éléments
- count() : retourne le nombre d'occurrences d'un élément spécifié
- empty() : retourne true si le map est vide
- end() : retourne un itérateur pointant vers la fin du map
- equal_range() : retourne une paire d'itérateurs pour un élément spécifique
- erase() : supprime un élément
- find() : recherche un élément
- get_allocator() : retourne l'allocateur du map
- insert() : insère un élément
- key_comp() : retourne la fonction de comparaison des clés
- lower_bound() : retourne la position du premier élément dont la clé est supérieure ou égale à l'élément donné
- max_size() : retourne le nombre maximal d'éléments que le map peut contenir
- rbegin() : retourne un itérateur inverse pointant vers la fin du map
- rend() : retourne un itérateur inverse pointant vers le début du map
- size() : retourne le nombre d'éléments dans le map
- swap() : échange deux maps
- upper_bound() : retourne la position du premier élément dont la clé est supérieure à l'élément donné
- value_comp() : retourne la fonction de comparaison des valeurs
4.6.set
Ensemble, stocke les données sous forme d'ensemble mathématique.
- insert(x) : ajoute x à l'ensemble