Les exercices sur l’alogorithme
le plus avancer
les exercices plus avancés et les plus complexes
Voici quelques exercices plus avancés et complexes sur les algorithmes, accompagnés de
leurs solutions.
Exercice 1 : Recherche binomiale dans un arbre binaire de recherche
Enoncé : Écrire un algorithme pour rechercher un élément dans un arbre binaire de recherche
(BST).
Solution :
python
class Node:
def __init__(self, key):
[Link] = None
[Link] = None
[Link] = key
def recherche_bst(root, key):
if root is None or [Link] == key:
return root
if [Link] < key:
return recherche_bst([Link], key)
return recherche_bst([Link], key)
# Exemple d'utilisation
root = Node(50)
[Link] = Node(30)
[Link] = Node(70)
[Link] = Node(20)
[Link] = Node(40)
[Link] = Node(60)
[Link] = Node(80)
key = 40
result = recherche_bst(root, key)
if result:
print("Clé trouvée :", [Link])
else:
print("Clé non trouvée")
Exercice 2 : Algorithme de Dijkstra pour les graphes
Enoncé : Écrire un algorithme pour trouver le chemin le plus court dans un graphe pondéré en
utilisant l'algorithme de Dijkstra.
Solution :
python
import heapq
def dijkstra(graph, start):
queue = []
[Link](queue, (0, start))
distances = {node: float('infinity') for node in graph}
distances[start] = 0
while queue:
current_distance, current_node = [Link](queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
[Link](queue, (distance, neighbor))
return distances
# Exemple d'utilisation
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
start_node = 'A'
distances = dijkstra(graph, start_node)
print("Distances depuis le noeud de départ :", distances)
Exercice 3 : Problème du sac à dos (Knapsack Problem)
Enoncé : Écrire un algorithme pour résoudre le problème du sac à dos en utilisant la
programmation dynamique.
Solution :
python
def knapsack(W, weights, values, n):
dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
dp[i][w] = 0
elif weights[i-1] <= w:
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-
1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]
# Exemple d'utilisation
values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
n = len(values)
print("La valeur maximale du sac à dos est :", knapsack(W, weights, values,
n))
Exercice 4 : Algorithme de tri rapide (Quicksort)
Enoncé : Écrire un algorithme pour trier un tableau en utilisant l'algorithme de tri rapide.
Solution :
python
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quicksort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quicksort(arr, low, pi - 1)
quicksort(arr, pi + 1, high)
# Exemple d'utilisation
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quicksort(arr, 0, n-1)
print("Tableau trié :", arr)
Exercice 5 : Algorithme de Floyd-Warshall pour les graphes
Enoncé : Écrire un algorithme pour trouver tous les chemins les plus courts entre tous les
couples de nœuds dans un graphe pondéré en utilisant l'algorithme de Floyd-Warshall.
Solution :
python
def floyd_warshall(graph):
dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
V = len(graph)
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# Exemple d'utilisation
graph = [
[0, 5, float('inf'), 10],
[float('inf'), 0, 3, float('inf')],
[float('inf'), float('inf'), 0, 1],
[float('inf'), float('inf'), float('inf'), 0]
]
distances = floyd_warshall(graph)
print("Les plus courtes distances entre chaque paire de nœuds :")
for row in distances:
print(row)
Ces exercices avancés couvrent des algorithmes et des concepts plus complexes qui sont
souvent utilisés dans des applications réelles et des compétitions de programmation.