Problèmes algorithmiques

Tri d'une collection

Bubble sort / sinking sort

Fait remonter les éléments les plus grands à la fin du tableau jusqu'à ce que le tableau soit trié.
Complexité en temps de O(n²)

// à chaque passage le plus grand élément du tableau sera remonté à droite // on ne traite donc plus les éléments de droite déjà triés for (int i = A.Length - 1; i >= 1; i--) { bool sorted = true; // pour chaque élément restant à trier du tableau for (int j = 0; j < i; j++) { // si l'élément courant est plus grand que l'élément de droite, on inverse les 2 éléments if (A[j] > A[j + 1]) { int temp = A[j + 1]; A[j + 1] = A[j]; A[j] = temp; sorted = false; } } // si on a procédé à aucune inversion c'est que ce qui reste à analyser du tableau est déjà trié, on s'arrête donc là if (sorted) { break; } }

Insertion sort

Complexité en temps O(n²), pour les tableaux triés ou presque triés la complexité en temps passe à O(n)

// pour chaque élément du tableau for (int i = 1; i < A.Length; i++) { int j = i - 1; // on compare avec l'élément précédent // au besoin on déplace le plus petit élément vers la gauche de sorte que les éléments à gauche soit triés while (j >= 0 && A[j] > A[j + 1]) { int temp = A[j + 1]; A[j + 1] = A[j]; A[j] = temp; j--; } }

Recherche dans une collection triée

L'idée est de découper récursivement le tableau en deux jusqu'à trouver la valeur.

// integers in array are arranged in ascending order private static int SearchIndexOf(int[] array, int x, int leftIndex, int rightIndex) { if (leftIndex > rightIndex) return -1; var middleIndex = (leftIndex + rightIndex) / 2; if (array[middleIndex] == x) return middleIndex; else if (array[middleIndex] >= x) return SearchIndexOf(array, x, leftIndex, middleIndex - 1); else return SearchIndexOf(array, x, middleIndex + 1, rightIndex); }

Rechercher la plus petite différence entre 2 entiers dans un tableau

int[] numbers = { 1, 6, 4, 8, 2 }; int res = FindSmallestInterval(numbers); Console.WriteLine(res); static int FindSmallestInterval(int[] numbers) { var minDiff = int.MaxValue; var sortedNumbers = numbers.Order().ToArray(); for (var i = 0; i < numbers.Length - 1; i++) { var diff = sortedNumbers[i + 1] - sortedNumbers[i]; if (diff < minDiff) minDiff = diff; } return minDiff; }

Nombres premiers

Compter le nombre de diviseurs d'un nombre entier N

L'approche la plus basique consiste à parcourir les nombres de 1 à N pour tester s'ils sont bien des diviseurs de N. Cette solution a une complexité en temps de O(N).
Sachant que si A est un diviseur de N, alors N/A est aussi un diviseur de N.

N=30, A=5 → N/A = 6 qui est un diviseur de 30  (30/6 = 5)
6 est le diviseur symétrique de 5 pour le nombre 30

Un de ces 2 diviseurs symétriques est inférieur à √N, on peut donc réduire la complexité en temps à O(√N).

int i; int numberOfDivisors = 0; for (i = 1; Math.BigMul(i, i) < N; i++) { if (N % i == 0) { // le diviseur et son symétrique numberOfDivisors += 2; } } // si (i == √N) il y a un diviseur qui n'a pas de symétrique. // Ex: N=4, on a 1 et son symétrique 4, mais 2 n'a pas de symétrique if (Math.BigMul(i, i) == N) { numberOfDivisors++; } return numberOfDivisors;

Tester si un entier N est premier

Un entier est premier s'il est divisible seulement par lui-même et par 1.
Ici aussi on réduit la complexité en temps à O(√N).

// on commence à 2, car tous les entiers sont divisible par 1 for (int i = 2; Math.BigMul(i, i) <= N; i++) { if (N % i == 0) { return false; } } return true;

Lister les N premiers nombres premiers

L'approche basique consiste à tester si les entiers de 2 à N sont premier. La complexité en temps est de O(N*√N).
En utilisant le crible d'Ératosthène on réduit la complexité O(log(log(N)))

bool[] sieve = new bool[N + 1]; // tout le tableau à true sauf les éléments 0 et 1, car ils ne sont jamais premiers for (int i = 2; i < N + 1; i++) { sieve[i] = true; } // met à false les multiples de j // par exemple: pour 2 met à false les multiles de 2 (4,6,8,...) // puis pour 3 met à false les multiles de 3 restants (9,12,...) // puis pour 4, il a déjà été mis à false par 2 int j = 2; while (Math.BigMul(j, j) <= N) { if (sieve[j]) { long k = Math.BigMul(j, j); while (k <= N) { sieve[k] = false; k += j; } } j++; } // on extrait les nombres entiers var primeNumbers = new List<int>(); for (int i = 0; i < sieve.Length; i++) { if (sieve[i]) { primeNumbers.Add(i); } } return primeNumbers;

Plus grande somme d'éléments contiguës dans un tableau

On cherche la plus grande somme qu’on puisse avoir en additionnant des éléments consécutifs d'un tableau.
Résolution à l'aide de l'algorithme de Kadane.

// tableau A // [1, 2, 3, 4] → somme des éléments 0 à 3 → 10 // [5, -9, 2, -1] → somme des éléments 2 à 3 → 1 int maxEndingHere = 0; int maxSoFar = 0; int maxElement = int.MinValue; for (int i = 0; i < A.Length; i++) { maxEndingHere = Math.Max(0, maxEndingHere + A[i]); maxSoFar = Math.Max(maxSoFar, maxEndingHere); maxElement = Math.Max(maxElement, A[i]); } // si tous les éléments du tableau sont négatif // la somme max est égale à 0: somme d'un tableau vide if (maxSoFar == 0) { // ici on souhaite plutôt avoir le plus grand nombre négatif comme solution maxSoFar = maxElement; } return maxSoFar;

L'algorithme de Kadane suppose que si le tableau ne contient que des éléments négatifs, alors la plus grande somme correspond à 0: somme d'un sous-tableau vide.

Plus grande sous-matrice carrée

On parcourt la matrice, on change la valeur chaque item par Min(top, left, top-left) + 1

{ 1 1 }  { 1 1 1 }
{ 1 2 }  { 1 2 2 }
         { 1 2 3 }

La plus grande valeur de la nouvelle matrice donne la taille de la plus grande sous-matrice carrée.

var matrix = new int[5, 5] { { 1, 1, 0, 1, 0 }, { 1, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1 }, { 0, 0, 1, 1, 1 }, { 1, 1, 0, 1, 0 }, }; int size = FindLargestSquare(matrix); Console.WriteLine(size); static void PrintMatrix (int[,] matrix) { int rowLength = matrix.GetLength(0); int colLength = matrix.GetLength(1); for (int row = 0; row < rowLength; row++) { for (int column = 0; column < colLength; column++) { Console.Write($"{matrix[row, column]} "); } Console.WriteLine(); } } static int FindLargestSquare(int[,] matrix) { if (matrix is null || matrix.Length == 0) return 0; int rowLength = matrix.GetLength(0); int colLength = matrix.GetLength(1); var newMatrix = new int[rowLength, colLength]; Array.Copy(matrix, 0, newMatrix, 0, matrix.Length); for (var c = 1; c < colLength; c++) { for (var r = 1; r < rowLength; r++) { if (matrix[r, c] == 1) { newMatrix[r, c] = 1 + Min( newMatrix[r, c - 1], newMatrix[r - 1, c], newMatrix[r - 1, c - 1]); } } } return newMatrix.Cast<int>().Max(); } static int Min(int val1, int val2, int val3) => Math.Min(val1, Math.Min(val2, val3));

Leader

Un élément d'un tableau est dit leader s'il est présent dans plus de la moitié des éléments du tableau.
Astuce: si on supprime 2 éléments différents du tableau, on supprime au plus un éléments leader.
Le leader reste donc leader du sous-tableau.

A = [4, 6, 6]
s = [4] → s = [4, 6] → 4 ≠ 6, on les supprime → s = [] → s = [6]

// on empile un à un les éléments du tableau var s = new Stack<int>(); for (int i = 0; i < A.Length; i++) { if (s.Count == 0) { s.Push(A[i]); } else { // si l'élément à empiler est différent de celui du sommet de la pile, on les supprime if (s.Peek() != A[i]) { s.Pop(); } else { s.Push(A[i]); } } } // si la pile est vide, c'est qu'il n'y a pas de leader if (s.Count == 0) { return -1; } // si la pile contient seulement 1 élément, il faut s'assurer qu'il est bien leader // car ce pourrait être le dernier éléments d'un tableau de taille impair une fois qu'on a supprimer les paires différents else if (s.Count == 1) { int candidate = s.Peek(); int count = 0; for (int i = 0; i < A.Length; i++) { if (A[i] == candidate) { count++; if (count > A.Length / 2) { return candidate; } } } return -1; } // si la pile contient plusieurs éléments, ce sont tous les même et c'est le leader else { return s.Peek(); }

Inverser les éléments d'un tableau A

On parcourt seulement la première moitié du tableau dont on échange les éléments avec la seconde moitié.

for (int i = 0; i < A.Length / 2; i++) { var temp = A[i]; A[i] = A[A.Length - 1 - i]; A[A.Length - 1 - i] = temp; }

Trouver les cycles dans un graphe orienté

public void FindCycle(int vertex) { // enregistrer le parcourt pour pouvoir afficher les cycles _path.Push(vertex); // enregistrer les sommets visités afin de pouvoir détecter les cycles _visited[vertex] = true; // pour tous les sommets adjacents: reliés au sommet courant par une arête sortante foreach (var adjacentVertex in _graph.OutEdges(vertex).Select(e => e.Target)) { // si ce sommet adjacent a déjà été parcouru, nous avons trouvé un cycle if (_visited[adjacentVertex]) { ... } // sinon on continue à parcourir le graphe à partir du sommet adjacent else { FindCycle(adjacentVertex); } } // après avoir atteint un sommet final (sans arêtes sortantes) // on rebrousse chemin: on marque le sommet courant comme non-parcouru et on l'enlève du parcourt _path.Pop(); _visited[vertex] = false; }

Lexique sur les graphes