Programmation Dynamique
Problème du Sac à Dos
Sac à Dos 0/1
Approche : La programmation dynamique décompose un problème complexe en sous-problèmes plus simples. Pour le sac à dos 0/1, nous définissons une représentation d'état avec une propriété et calculons les transitions.
Considérons les premiers i objets avec un volume total j dans le sac. Soit dp[i][j] la valeur maximale pour cette configuration. Les transitions sont :
- Ne pas inclure l'objet i :
dp[i][j] = dp[i-1][j] - Inclure l'objet i (si j ≥ volume de l'objet) :
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + val[i])
La condition initiale est dp[0][0] = 0. L'algorithme parcourt les objets et les volumes, et le résultat est le maximum dans la dernière ligne.
Optimisation avec un tableau roulant : parcourir j de manière décroissante.
Code Complet (Version de Base)
#include <stdio.h>
int nombreObjets, capacite;
const int MAX_OBJ = 1010;
int volume[MAX_OBJ], valeur[MAX_OBJ];
int memo[MAX_OBJ][MAX_OBJ];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d %d", &nombreObjets, &capacite);
for (int i = 1; i <= nombreObjets; i++) {
scanf("%d %d", &volume[i], &valeur[i]);
}
for (int i = 1; i <= nombreObjets; i++) {
for (int j = 0; j <= capacite; j++) {
memo[i][j] = memo[i-1][j];
if (j >= volume[i]) {
memo[i][j] = maximum(memo[i][j], memo[i-1][j - volume[i]] + valeur[i]);
}
}
}
printf("%d\n", memo[nombreObjets][capacite]);
return 0;
}
Code Complet (Version Optimisée)
#include <stdio.h>
int nombreObjets, capacite;
const int MAX_OBJ = 1010;
int memo[MAX_OBJ];
int volume[MAX_OBJ], valeur[MAX_OBJ];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d %d", &nombreObjets, &capacite);
for (int i = 1; i <= nombreObjets; i++) {
scanf("%d %d", &volume[i], &valeur[i]);
}
for (int i = 1; i <= nombreObjets; i++) {
for (int j = capacite; j >= volume[i]; j--) {
memo[j] = maximum(memo[j], memo[j - volume[i]] + valeur[i]);
}
}
printf("%d\n", memo[capacite]);
return 0;
}
Sac à Dos Complet
Approche : Ici, chaque objet peut être inclus plusieurs fois. La relation de récurrence est dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + val[i]) pour j ≥ volume de l'objet. L'optimisation parcourt j de manière croissante.
Code Complet (Version de Base)
#include <stdio.h>
int nombreObjets, capacite;
const int MAX_OBJ = 1010;
int volume[MAX_OBJ], valeur[MAX_OBJ];
int memo[MAX_OBJ][MAX_OBJ];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d %d", &nombreObjets, &capacite);
for (int i = 1; i <= nombreObjets; i++) {
scanf("%d %d", &volume[i], &valeur[i]);
}
for (int i = 1; i <= nombreObjets; i++) {
for (int j = 0; j <= capacite; j++) {
memo[i][j] = memo[i-1][j];
if (j >= volume[i]) {
memo[i][j] = maximum(memo[i][j], memo[i][j - volume[i]] + valeur[i]);
}
}
}
printf("%d\n", memo[nombreObjets][capacite]);
return 0;
}
Code Complet (Version Optimisée)
#include <stdio.h>
int nombreObjets, capacite;
const int MAX_OBJ = 1010;
int volume[MAX_OBJ], valeur[MAX_OBJ];
int memo[MAX_OBJ];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d %d", &nombreObjets, &capacite);
for (int i = 1; i <= nombreObjets; i++) {
scanf("%d %d", &volume[i], &valeur[i]);
}
for (int i = 1; i <= nombreObjets; i++) {
for (int j = volume[i]; j <= capacite; j++) {
memo[j] = maximum(memo[j], memo[j - volume[i]] + valeur[i]);
}
}
printf("%d\n", memo[capacite]);
return 0;
}
Sac à Dos Multiple
Approche : Chaque objet a une quantité limite. C'est une extension du sac à dos 0/1 avec une boucle supplémentaire pour les quantités. L'optimisation binaire découpe les quantités en puissances de deux pour réduire la complexité.
Code Complet (Version Optimisée Binaire)
#include <stdio.h>
int capacite;
const int MAX_OBJ = 25000, MAX_CAP = 2010;
int volume[MAX_OBJ], valeur[MAX_OBJ];
int memo[MAX_CAP];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
int nombreObjets;
scanf("%d %d", &nombreObjets, &capacite);
int compteur = 0;
for (int i = 0; i < nombreObjets; i++) {
int vol, val, quant;
scanf("%d %d %d", &vol, &val, &quant);
int k = 1;
while (k <= quant) {
compteur++;
volume[compteur] = vol * k;
valeur[compteur] = val * k;
quant -= k;
k *= 2;
}
if (quant > 0) {
compteur++;
volume[compteur] = vol * quant;
valeur[compteur] = val * quant;
}
}
for (int i = 1; i <= compteur; i++) {
for (int j = capacite; j >= volume[i]; j--) {
memo[j] = maximum(memo[j], memo[j - volume[i]] + valeur[i]);
}
}
printf("%d\n", memo[capacite]);
return 0;
}
Sac à Dos par Groupes
Approche : Il y a des groupes d'objets, et on peut en choisir un par groupe. La transition parcourt les groupes et les objets à l'intérieur.
Code Complet
#include <stdio.h>
int nombreGroupes, capacite;
const int MAX_GRP = 110;
int tailles[MAX_GRP];
int volume[MAX_GRP][MAX_GRP], valeur[MAX_GRP][MAX_GRP];
int memo[MAX_GRP];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d %d", &nombreGroupes, &capacite);
for (int i = 1; i <= nombreGroupes; i++) {
scanf("%d", &tailles[i]);
for (int j = 0; j < tailles[i]; j++) {
scanf("%d %d", &volume[i][j], &valeur[i][j]);
}
}
for (int i = 1; i <= nombreGroupes; i++) {
for (int j = capacite; j >= 0; j--) {
for (int k = 0; k < tailles[i]; k++) {
if (j >= volume[i][k]) {
memo[j] = maximum(memo[j], memo[j - volume[i][k]] + valeur[i][k]);
}
}
}
}
printf("%d\n", memo[capacite]);
return 0;
}
Programmation Dynamique Linéaire
Triangle Numérique
Un exemple classique de programmation dynamique linéaire où on calcule le chemin de somme minimale ou maximale.
Sous-séquence Croissante Maximale
Approche de Base : Pour chaque position i, dp[i] est la longueur maximale de la sous-séquence se terminant à i. On compare avec tous les j < i tels que a[j] < a[i].
Apprcohe Optimisée avec Recherche Binaire : On maintient un tableau fin où fin[len] est la plus petite valeur de fin pour une sous-séquence de longueur len. Pour chaque élément, on cherche par dichotomie où l'insérer.
Code Complet (Version de Base)
#include <stdio.h>
int taille;
const int MAX_TAILLE = 1010;
int sequence[MAX_TAILLE], dp[MAX_TAILLE];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d", &taille);
for (int i = 1; i <= taille; i++) {
scanf("%d", &sequence[i]);
}
int resultat = 0;
for (int i = 1; i <= taille; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (sequence[j] < sequence[i]) {
dp[i] = maximum(dp[i], dp[j] + 1);
}
}
resultat = maximum(resultat, dp[i]);
}
printf("%d\n", resultat);
return 0;
}
Code Complet (Version Optimisée)
#include <stdio.h>
int taille;
const int MAX_TAILLE = 100010;
int sequence[MAX_TAILLE], fin[MAX_TAILLE];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d", &taille);
for (int i = 0; i < taille; i++) {
scanf("%d", &sequence[i]);
}
int longueur = 0;
fin[0] = -2e9;
for (int i = 0; i < taille; i++) {
int gauche = 0, droite = longueur;
while (gauche < droite) {
int milieu = (gauche + droite + 1) / 2;
if (fin[milieu] < sequence[i]) {
gauche = milieu;
} else {
droite = milieu - 1;
}
}
longueur = maximum(longueur, droite + 1);
fin[droite + 1] = sequence[i];
}
printf("%d\n", longueur);
return 0;
}
Sous-séquence Commune Maximale
Approche : dp[i][j] représente la longueur maximale de la sous-séquence commune entre les i premiers éléments de la première séquence et les j premiers de la seconde. Les transitions considèrent les cas où les éléments sont égaux ou non.
Code Complet
#include <stdio.h>
#include <string.h>
int longueur1, longueur2;
const int MAX_LEN = 1010;
char seq1[MAX_LEN], seq2[MAX_LEN];
int memo[MAX_LEN][MAX_LEN];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
scanf("%d %d", &longueur1, &longueur2);
scanf("%s %s", seq1 + 1, seq2 + 1);
for (int i = 1; i <= longueur1; i++) {
for (int j = 1; j <= longueur2; j++) {
memo[i][j] = maximum(memo[i-1][j], memo[i][j-1]);
if (seq1[i] == seq2[j]) {
memo[i][j] = maximum(memo[i][j], memo[i-1][j-1] + 1);
}
}
}
printf("%d\n", memo[longueur1][longueur2]);
return 0;
}
Distance d'Édition Minimale
Approche : dp[i][j] est le coût minimal pour transformer les i premiers caractères de A en les j premiers de B. Les opérations possibles sont insertion, suppression et modification.
Code Complet
#include <stdio.h>
#include <string.h>
const int MAX_LEN = 1010;
int longueurA, longueurB;
char chaineA[MAX_LEN], chaineB[MAX_LEN];
int memo[MAX_LEN][MAX_LEN];
int minimum(int a, int b) {
return (a < b) ? a : b;
}
int main() {
scanf("%d %s", &longueurA, chaineA + 1);
scanf("%d %s", &longueurB, chaineB + 1);
for (int i = 0; i <= longueurA; i++) {
memo[i][0] = i;
}
for (int j = 0; j <= longueurB; j++) {
memo[0][j] = j;
}
for (int i = 1; i <= longueurA; i++) {
for (int j = 1; j <= longueurB; j++) {
memo[i][j] = minimum(memo[i-1][j] + 1, memo[i][j-1] + 1);
if (chaineA[i] == chaineB[j]) {
memo[i][j] = minimum(memo[i][j], memo[i-1][j-1]);
} else {
memo[i][j] = minimum(memo[i][j], memo[i-1][j-1] + 1);
}
}
}
printf("%d\n", memo[longueurA][longueurB]);
return 0;
}
Algorithmes de Base
Tri Rapide
Approche : L'algorithme de tri rapide utilise la stratégie diviser pour régner. On choisit un pivot, on partitionne le tableau autour de ce pivot, puis on trie récursivement les sous-tableaux.
Code Complet (Version avec While)
#include <stdio.h>
const int MAX_N = 100010;
int tableau[MAX_N];
void triRapide(int tableau[], int gauche, int droite) {
if (gauche >= droite) return;
int pivot = tableau[(gauche + droite) / 2];
int i = gauche, j = droite;
while (i <= j) {
while (tableau[i] < pivot) i++;
while (tableau[j] > pivot) j--;
if (i <= j) {
int temp = tableau[i];
tableau[i] = tableau[j];
tableau[j] = temp;
i++;
j--;
}
}
triRapide(tableau, gauche, j);
triRapide(tableau, i, droite);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &tableau[i]);
}
triRapide(tableau, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", tableau[i]);
}
printf("\n");
return 0;
}
Tri par Fusion
Approche : Le tri par fusion divise le tableau en deux moitiés, trie récursivement chaque moitié, puis fusionne les deux moitiés triées. La fusion utilise un tableau temporaire pour combiner les éléments.
Code Complet
#include <stdio.h>
const int MAX_N = 100010;
int tableau[MAX_N], temp[MAX_N];
void triFusion(int tableau[], int gauche, int droite) {
if (gauche >= droite) return;
int milieu = (gauche + droite) / 2;
triFusion(tableau, gauche, milieu);
triFusion(tableau, milieu + 1, droite);
int i = gauche, j = milieu + 1, k = 0;
while (i <= milieu && j <= droite) {
if (tableau[i] <= tableau[j]) {
temp[k++] = tableau[i++];
} else {
temp[k++] = tableau[j++];
}
}
while (i <= milieu) temp[k++] = tableau[i++];
while (j <= droite) temp[k++] = tableau[j++];
for (i = gauche, k = 0; i <= droite; i++, k++) {
tableau[i] = temp[k];
}
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &tableau[i]);
}
triFusion(tableau, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", tableau[i]);
}
return 0;
}
Recherche Binaire
Approche : Pour un tableau trié, la recherche binaire trouve la position d'un élément en réduisant itérativement l'intervalle de recherche. On distingue la recherche de la borne inférieure et supérieure.
Code Complet (Entier)
#include <stdio.h>
const int MAX_N = 100010;
int tableau[MAX_N];
int main() {
int n, requetes;
scanf("%d %d", &n, &requetes);
for (int i = 0; i < n; i++) {
scanf("%d", &tableau[i]);
}
while (requetes--) {
int cible;
scanf("%d", &cible);
int gauche = 0, droite = n - 1;
while (gauche < droite) {
int milieu = (gauche + droite) / 2;
if (tableau[milieu] >= cible) {
droite = milieu;
} else {
gauche = milieu + 1;
}
}
if (tableau[gauche] != cible) {
printf("-1 -1\n");
} else {
printf("%d ", gauche);
droite = n - 1;
while (gauche < droite) {
int milieu = (gauche + droite + 1) / 2;
if (tableau[milieu] <= cible) {
gauche = milieu;
} else {
droite = milieu - 1;
}
}
printf("%d\n", gauche);
}
}
return 0;
}
Sommes Préfixes
Approche : Pour un tableau a[], le tableau de sommes préfixes s[] est défini par s[i] = s[i-1] + a[i]. La somme d'un sous-tableau de l à r est s[r] - s[l-1]. Pour les tableaux 2D, on utilise une extension similaire.
Code Complet (1D)
#include <stdio.h>
const int MAX_N = 100010;
int tableau[MAX_N], prefixe[MAX_N];
int main() {
int n, requetes;
scanf("%d %d", &n, &requetes);
for (int i = 1; i <= n; i++) {
scanf("%d", &tableau[i]);
prefixe[i] = prefixe[i-1] + tableau[i];
}
while (requetes--) {
int l, r;
scanf("%d %d", &l, &r);
printf("%d\n", prefixe[r] - prefixe[l-1]);
}
return 0;
}
Tableaux de Différence
Approche : Le tableau de différence b[] est tel que a[] est la somme préfixe de b[]. Pour ajouter une valeur c à un intervalle [l, r], on met à jour b[l] += c et b[r+1] -= c. En 2D, on étend cette idée.
Code Complet (1D)
#include <stdio.h>
const int MAX_N = 100010;
int tableau[MAX_N], difference[MAX_N];
void inserer(int l, int r, int c) {
difference[l] += c;
difference[r + 1] -= c;
}
int main() {
int n, requetes;
scanf("%d %d", &n, &requetes);
for (int i = 1; i <= n; i++) {
scanf("%d", &tableau[i]);
inserer(i, i, tableau[i]);
}
while (requetes--) {
int l, r, c;
scanf("%d %d %d", &l, &r, &c);
inserer(l, r, c);
}
for (int i = 1; i <= n; i++) {
difference[i] += difference[i-1];
printf("%d ", difference[i]);
}
return 0;
}
Pointeurs Doubles
Approche : L'algorithme à deux pointeurs utilise deux indices qui parcourent le tableau de manière coordonnée, souvent pour résoudre des problèmes de sous-tableaux ou de séquences.
Code Exemple (Longueur Maximale de Sous-séquence sans Répétition)
#include <stdio.h>
const int MAX_N = 100010;
int sequence[MAX_N], frequence[MAX_N];
int maximum(int a, int b) {
return (a > b) ? a : b;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &sequence[i]);
}
int resultat = 0;
int j = 0;
for (int i = 0; i < n; i++) {
frequence[sequence[i]]++;
while (frequence[sequence[i]] > 1) {
frequence[sequence[j]]--;
j++;
}
resultat = maximum(resultat, i - j + 1);
}
printf("%d\n", resultat);
return 0;
}
Opérations Bit à Bit
Concepts : Les opérations bit à bit incluent le décalage pour extraire des bits spécifiques et la fonction lowbit pour obtenir le bit le plus bas à 1.
Code Complet (Compter les Bits à 1)
#include <stdio.h>
int lowbit(int x) {
return x & -x;
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
int x;
scanf("%d", &x);
int compteur = 0;
while (x) {
x -= lowbit(x);
compteur++;
}
printf("%d ", compteur);
}
return 0;
}
Structures de Données
Liste Chaînée Simple
Implémentation : Utilisation de tableaux pour simuler une liste chaînée, avec un pointeur de tête et des opérations d'insertion et de suppression.
Code Complet
#include <stdio.h>
const int MAX_N = 100010;
int valeur[MAX_N], suivant[MAX_N];
int tete, compteur;
void initialiser() {
compteur = 0;
tete = -1;
}
void ajouterEnTete(int x) {
valeur[compteur] = x;
suivant[compteur] = tete;
tete = compteur++;
}
void supprimer(int k) {
suivant[k - 1] = suivant[suivant[k - 1]];
}
void insererApres(int k, int x) {
valeur[compteur] = x;
suivant[compteur] = suivant[k - 1];
suivant[k - 1] = compteur++;
}
int main() {
initialiser();
int m;
scanf("%d", &m);
while (m--) {
char op;
int x, k;
scanf(" %c", &op);
if (op == 'H') {
scanf("%d", &x);
ajouterEnTete(x);
} else if (op == 'D') {
scanf("%d", &x);
if (x == 0) {
tete = suivant[tete];
} else {
supprimer(x);
}
} else {
scanf("%d %d", &k, &x);
insererApres(k, x);
}
}
for (int i = tete; i != -1; i = suivant[i]) {
printf("%d ", valeur[i]);
}
return 0;
}
Liste Chaînée Double
Implémentation : Utilisaiton de tableaux pour les pointeurs gauche et droit, avec des nœuds sentinelle pour simplifier les opérations.
Code Complet
#include <stdio.h>
const int MAX_N = 100010;
int valeur[MAX_N], gauche[MAX_N], droite[MAX_N];
int compteur;
void initialiser() {
compteur = 2;
droite[0] = 1;
gauche[1] = 0;
}
void insererDroite(int k, int x) {
valeur[compteur] = x;
droite[compteur] = droite[k];
gauche[compteur] = k;
gauche[droite[k]] = compteur;
droite[k] = compteur++;
}
void supprimer(int k) {
droite[gauche[k]] = droite[k];
gauche[droite[k]] = gauche[k];
}
int main() {
initialiser();
int m;
scanf("%d", &m);
while (m--) {
char op;
int x, k;
scanf(" %c", &op);
if (op == 'L') {
scanf("%d", &x);
insererDroite(0, x);
} else if (op == 'R') {
scanf("%d", &x);
insererDroite(gauche[1], x);
} else if (op == 'D') {
scanf("%d", &x);
supprimer(x + 1);
} else {
char dir;
scanf(" %c", &dir);
scanf("%d %d", &k, &x);
if (dir == 'L') {
insererDroite(gauche[k + 1], x);
} else {
insererDroite(k + 1, x);
}
}
}
for (int i = droite[0]; i != 1; i = droite[i]) {
printf("%d ", valeur[i]);
}
return 0;
}
Piles et Files
Piles : Structure LIFO avec des opérations push et pop. Files : Structure FIFO avec des opérations enqueue et dequeue.
Code Exemple (Évaluation d'Expressions avec Piles)
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX_LEN 100010
char expression[MAX_LEN];
int pileValeurs[MAX_LEN], sommetVal = -1;
char pileOperateurs[MAX_LEN], sommetOp = -1;
void evaluer() {
int b = pileValeurs[sommetVal--];
int a = pileValeurs[sommetVal--];
char op = pileOperateurs[sommetOp--];
int resultat;
if (op == '+') resultat = a + b;
else if (op == '-') resultat = a - b;
else if (op == '*') resultat = a * b;
else resultat = a / b;
pileValeurs[++sommetVal] = resultat;
}
int main() {
scanf("%s", expression);
for (int i = 0; expression[i]; i++) {
char c = expression[i];
if (isdigit(c)) {
int nombre = 0;
while (isdigit(expression[i])) {
nombre = nombre * 10 + (expression[i] - '0');
i++;
}
i--;
pileValeurs[++sommetVal] = nombre;
} else if (c == '(') {
pileOperateurs[++sommetOp] = c;
} else if (c == ')') {
while (pileOperateurs[sommetOp] != '(') {
evaluer();
}
sommetOp--;
} else {
while (sommetOp >= 0 && pileOperateurs[sommetOp] != '(' &&
(c == '*' || c == '/') && (pileOperateurs[sommetOp] == '+' || pileOperateurs[sommetOp] == '-')) {
evaluer();
}
pileOperateurs[++sommetOp] = c;
}
}
while (sommetOp >= 0) {
evaluer();
}
printf("%d\n", pileValeurs[sommetVal]);
return 0;
}
Pile Monotone
Approche : Une pile monotone maintient une séquence d'éléments dans un ordre croissant ou décriossant pour résoudre des problèmes comme le plus grand élément précédent.
Code Complet
#include <stdio.h>
const int MAX_N = 100010;
int pile[MAX_N], sommet = -1;
int main() {
int n;
scanf("%d", &n);
while (n--) {
int x;
scanf("%d", &x);
while (sommet >= 0 && pile[sommet] >= x) {
sommet--;
}
if (sommet >= 0) {
printf("%d ", pile[sommet]);
} else {
printf("-1 ");
}
pile[++sommet] = x;
}
return 0;
}
File Monotone
Approche : Une file monotone est utilisée pour des problèmes de fenêtre glissante, maintenant les éléments dans un ordre spécifique pour obtenir rapidement le minimum ou maximum local.
Code Complet (Minimum dans Fenêtre Glissante)
#include <stdio.h>
const int MAX_N = 1000010;
int sequence[MAX_N], file[MAX_N];
int main() {
int n, k;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", &sequence[i]);
}
int tete = 0, queue = -1;
for (int i = 0; i < n; i++) {
if (tete <= queue && file[tete] < i - k + 1) {
tete++;
}
while (tete <= queue && sequence[file[queue]] >= sequence[i]) {
queue--;
}
file[++queue] = i;
if (i >= k - 1) {
printf("%d ", sequence[file[tete]]);
}
}
printf("\n");
tete = 0, queue = -1;
for (int i = 0; i < n; i++) {
if (tete <= queue && file[tete] <= i - k) {
tete++;
}
while (tete <= queue && sequence[file[queue]] <= sequence[i]) {
queue--;
}
file[++queue] = i;
if (i >= k - 1) {
printf("%d ", sequence[file[tete]]);
}
}
return 0;
}
Algorithme KMP
Approche : L'algorithme KMP recherche un motif dans un texte en utilisant un tableau de préfixes pour éviter les comparaisons redondantes.
Code Complet
#include <stdio.h>
const int MAX_MOTIF = 100010, MAX_TEXTE = 1000010;
char motif[MAX_MOTIF], texte[MAX_TEXTE];
int next[MAX_MOTIF];
int main() {
int n, m;
scanf("%d %s", &n, motif + 1);
scanf("%d %s", &m, texte + 1);
for (int i = 2, j = 0; i <= n; i++) {
while (j > 0 && motif[i] != motif[j + 1]) {
j = next[j];
}
if (motif[i] == motif[j + 1]) {
j++;
}
next[i] = j;
}
for (int i = 1, j = 0; i <= m; i++) {
while (j > 0 && texte[i] != motif[j + 1]) {
j = next[j];
}
if (texte[i] == motif[j + 1]) {
j++;
}
if (j == n) {
printf("%d ", i - n);
j = next[j];
}
}
return 0;
}
Arbre Trie
Approche : Un trie est un arbre de préfixes pour stocker des chaînes de caractères, permettant des insertions et des recherches efficaces.
Code Complet (Insertion et Recherche)
#include <stdio.h>
const int MAX_N = 100010;
int enfant[MAX_N][26], compteur[MAX_N], idx;
void inserer(char *mot) {
int noeud = 0;
for (int i = 0; mot[i]; i++) {
int c = mot[i] - 'a';
if (!enfant[noeud][c]) {
enfant[noeud][c] = ++idx;
}
noeud = enfant[noeud][c];
}
compteur[noeud]++;
}
int rechercher(char *mot) {
int noeud = 0;
for (int i = 0; mot[i]; i++) {
int c = mot[i] - 'a';
if (!enfant[noeud][c]) {
return 0;
}
noeud = enfant[noeud][c];
}
return compteur[noeud];
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
char op[2], mot[100];
scanf("%s %s", op, mot);
if (op[0] == 'I') {
inserer(mot);
} else {
printf("%d\n", rechercher(mot));
}
}
return 0;
}
Union-Find (Structure d'Ensembles Disjoints)
Approche : L'union-find gère une collection d'ensembles disjoints avec des opérations d'union et de recherche de racine, utilisant la compression de chemin pour l'efficacité.
Code Complet
#include <stdio.h>
const int MAX_N = 100010;
int parent[MAX_N];
int trouver(int x) {
if (parent[x] != x) {
parent[x] = trouver(parent[x]);
}
return parent[x];
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
while (m--) {
char op;
int a, b;
scanf(" %c %d %d", &op, &a, &b);
if (op == 'M') {
parent[trouver(a)] = trouver(b);
} else {
if (trouver(a) == trouver(b)) {
printf("Yes\n");
} else {
printf("No\n");
}
}
}
return 0;
}
Tas (Heap)
Approche : Un tas est une structure de données arborescente pour maintenir un minimum ou maximum, avec des opérations d'insertion et de suppression en temps logarithmique.
Code Complet (Tas Minimum)
#include <stdio.h>
const int MAX_N = 100010;
int tas[MAX_N], taille;
void descendre(int x) {
int plusPetit = x;
if (2 * x <= taille && tas[2 * x] < tas[plusPetit]) {
plusPetit = 2 * x;
}
if (2 * x + 1 <= taille && tas[2 * x + 1] < tas[plusPetit]) {
plusPetit = 2 * x + 1;
}
if (plusPetit != x) {
int temp = tas[x];
tas[x] = tas[plusPetit];
tas[plusPetit] = temp;
descendre(plusPetit);
}
}
void monter(int x) {
while (x > 1 && tas[x / 2] > tas[x]) {
int temp = tas[x];
tas[x] = tas[x / 2];
tas[x / 2] = temp;
x /= 2;
}
}
void inserer(int x) {
tas[++taille] = x;
monter(taille);
}
int supprimerMinimum() {
int min = tas[1];
tas[1] = tas[taille--];
descendre(1);
return min;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
taille = n;
for (int i = 1; i <= n; i++) {
scanf("%d", &tas[i]);
}
for (int i = n / 2; i >= 1; i--) {
descendre(i);
}
while (m--) {
printf("%d ", supprimerMinimum());
}
return 0;
}
Table de Hachage
Approche : Une table de hachage mappe des clés à des valeurs via une fonction de hachage, avec des méthodes de résolution de collisions comme le chaînage ou l'adressage ouvert.
Code Complet (Chaînage)
#include <stdio.h>
#include <string.h>
const int MAX_N = 100003;
int tete[MAX_N], valeur[MAX_N], suivant[MAX_N], compteur;
void inserer(int x) {
int h = (x % MAX_N + MAX_N) % MAX_N;
valeur[compteur] = x;
suivant[compteur] = tete[h];
tete[h] = compteur++;
}
int rechercher(int x) {
int h = (x % MAX_N + MAX_N) % MAX_N;
for (int i = tete[h]; i != -1; i = suivant[i]) {
if (valeur[i] == x) {
return 1;
}
}
return 0;
}
int main() {
int n;
scanf("%d", &n);
memset(tete, -1, sizeof(tete));
while (n--) {
char op;
int x;
scanf(" %c %d", &op, &x);
if (op == 'I') {
inserer(x);
} else {
if (rechercher(x)) {
printf("Yes\n");
} else {
printf("No\n");
}
}
}
return 0;
}
Hachage de Chaînes
Approche : Le hachage de chaînes utilise des hachages préfixes pour comparer rapidement des sous-chaînes en calculant des valeurs de hachage modulo un grand nombre premier.
Code Complet
#include <stdio.h>
#include <string.h>
const int MAX_N = 100010;
typedef unsigned long long ULL;
ULL hashPrefix[MAX_N], puissance[MAX_N];
char chaine[MAX_N];
int base = 131;
ULL obtenirHash(int l, int r) {
return hashPrefix[r] - hashPrefix[l - 1] * puissance[r - l + 1];
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
scanf("%s", chaine + 1);
puissance[0] = 1;
for (int i = 1; i <= n; i++) {
puissance[i] = puissance[i - 1] * base;
hashPrefix[i] = hashPrefix[i - 1] * base + chaine[i];
}
while (m--) {
int l1, r1, l2, r2;
scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
if (obtenirHash(l1, r1) == obtenirHash(l2, r2)) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
Recherche et Théorie des Graphes
Recherche en Profondeur (DFS)
Approche : Le DFS explore un graphe aussi profondément que possible avant de revenir en arrière, souvent implémenté de manière récursive avec une pile.
Code Complet (Problème des N-Reines)
#include <stdio.h>
int n;
int plateau[20][20];
int colonnes[20], diagonale1[40], diagonale2[40];
void dfs(int ligne) {
if (ligne == n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%c", plateau[i][j] ? 'Q' : '.');
}
printf("\n");
}
printf("\n");
return;
}
for (int col = 0; col < n; col++) {
if (!colonnes[col] && !diagonale1[ligne + col] && !diagonale2[ligne - col + n]) {
plateau[ligne][col] = 1;
colonnes[col] = diagonale1[ligne + col] = diagonale2[ligne - col + n] = 1;
dfs(ligne + 1);
colonnes[col] = diagonale1[ligne + col] = diagonale2[ligne - col + n] = 0;
plateau[ligne][col] = 0;
}
}
}
int main() {
scanf("%d", &n);
dfs(0);
return 0;
}
Recherche en Largeur (BFS)
Approche : Le BFS explore un graphe niveau par niveau, utilisant une file pour traiter les nœuds dans l'ordre de leur découverte, idéal pour les plus courts chemins.
Code Complet (Plus Court Chemin dans une Grille)
#include <stdio.h>
#include <string.h>
const int MAX_N = 110;
int grille[MAX_N][MAX_N], distance[MAX_N][MAX_N];
int fileX[MAX_N * MAX_N], fileY[MAX_N * MAX_N];
int bfs(int n, int m) {
int tete = 0, queue = 0;
fileX[queue] = 0;
fileY[queue] = 0;
distance[0][0] = 0;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
while (tete <= queue) {
int x = fileX[tete];
int y = fileY[tete];
tete++;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !grille[nx][ny] && distance[nx][ny] == -1) {
distance[nx][ny] = distance[x][y] + 1;
queue++;
fileX[queue] = nx;
fileY[queue] = ny;
}
}
}
return distance[n-1][m-1];
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &grille[i][j]);
}
}
memset(distance, -1, sizeof(distance));
printf("%d\n", bfs(n, m));
return 0;
}
Stockage de Graphes
Matrice d'Adjacence : Convient pour les graphes denses. Liste d'Adjacence : Plus efficace pour les graphes creux, implémentée avec des tableaux chaînés.
Tri Topologique
Approche : Pour un graphe dirigé acyclique (DAG), le tri topologique ordonne les nœuds de sorte que pour chaque arête dirigée de u à v, u vient avant v.
Code Complet
#include <stdio.h>
#include <string.h>
const int MAX_N = 100010;
int tete[MAX_N], suivant[MAX_N], destination[MAX_N], compteur;
int degreEntrant[MAX_N], file[MAX_N], resultat[MAX_N];
void ajouterArete(int u, int v) {
destination[compteur] = v;
suivant[compteur] = tete[u];
tete[u] = compteur++;
}
int triTopologique(int n) {
int teteFile = 0, queueFile = -1;
for (int i = 1; i <= n; i++) {
if (degreEntrant[i] == 0) {
file[++queueFile] = i;
}
}
int index = 0;
while (teteFile <= queueFile) {
int u = file[teteFile++];
resultat[index++] = u;
for (int i = tete[u]; i != -1; i = suivant[i]) {
int v = destination[i];
degreEntrant[v]--;
if (degreEntrant[v] == 0) {
file[++queueFile] = v;
}
}
}
return index == n;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
memset(tete, -1, sizeof(tete));
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
ajouterArete(u, v);
degreEntrant[v]++;
}
if (triTopologique(n)) {
for (int i = 0; i < n; i++) {
printf("%d ", resultat[i]);
}
} else {
printf("-1");
}
return 0;
}