Problèmes algorithmiques
De Banane Atomic
Aller à la navigationAller à la recherche
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);
}
|
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
|
|
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;
if (matrix.Length > 100)
throw new ArgumentOutOfRangeException(nameof(matrix));
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)
{
// { 1 1 }
// { 1 x }
// x → 2
newMatrix[r, c] = 1 + Min(
newMatrix[r, c - 1],
newMatrix[r - 1, c],
newMatrix[r - 1, c - 1]);
}
}
}
PrintMatrix(newMatrix);
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;
}
|
