Définir un algorithme adapté
Exercices corrigés

"Rechercher un élément dans un tableau trié de n entiers. Le tableau est trié par ordre croissant. Trouver la position de l'élément recherché ou indiquer qu'il n'est pas présent."

• Données : Tableau trié d'entiers et élément à rechercher
• Objectif : Trouver l'indice de l'élément ou -1 si absent
• Contrainte : Tableau trié (information cruciale)

def recherche_dichotomique(tableau, element):
    gauche = 0
    droite = len(tableau) - 1
    
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        
        if tableau[milieu] == element:
            return milieu  # Élément trouvé
        elif tableau[milieu] < element:
            gauche = milieu + 1  # Chercher à droite
        else:
            droite = milieu - 1  # Chercher à gauche
    
    return -1  # Élément non trouvé

# Exemple d'utilisation
tab_trie = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
resultat = recherche_dichotomique(tab_trie, 7)
print(f"L'élément 7 est à l'indice: {resultat}")

• Le tableau est trié, ce qui permet d'utiliser la recherche dichotomique
• Complexité O(log n) vs O(n) pour la recherche linéaire
• Plus efficace pour de grands tableaux
• Algorithme optimal pour ce type de problème

"Trier un tableau d'entiers par ordre croissant. La taille du tableau varie de quelques dizaines à plusieurs millions d'éléments. La mémoire est limitée mais suffisante pour un tri en place."

• Données : Tableau d'entiers de taille variable
• Objectif : Ordonner les éléments du tableau
• Contraintes : Mémoire limitée, taille variable

def tri_rapide(tableau):
    if len(tableau) <= 1:
        return tableau
    
    pivot = tableau[len(tableau) // 2]
    gauche = [x for x in tableau if x < pivot]
    milieu = [x for x in tableau if x == pivot]
    droite = [x for x in tableau if x > pivot]
    
    return tri_rapide(gauche) + milieu + tri_rapide(droite)

# Version en place pour économiser la mémoire
def tri_rapide_en_place(tableau, debut=0, fin=None):
    if fin is None:
        fin = len(tableau) - 1
    
    if debut < fin:
        pivot_index = partition(tableau, debut, fin)
        tri_rapide_en_place(tableau, debut, pivot_index - 1)
        tri_rapide_en_place(tableau, pivot_index + 1, fin)

def partition(tableau, debut, fin):
    pivot = tableau[fin]
    i = debut - 1
    
    for j in range(debut, fin):
        if tableau[j] <= pivot:
            i += 1
            tableau[i], tableau[j] = tableau[j], tableau[i]
    
    tableau[i + 1], tableau[fin] = tableau[fin], tableau[i + 1]
    return i + 1

• Complexité moyenne O(n log n) - très efficace
• Tri en place possible - économie de mémoire
• Bien adapté aux grandes tailles de données
• Implémentation optimisée disponible dans les bibliothèques

"Parcourir un arbre binaire pour afficher les valeurs de tous les nœuds. L'ordre d'affichage dépend de l'application : préfixe pour une copie de l'arbre, infixé pour un affichage trié dans un ABR, postfixe pour le calcul d'expressions."

• Données : Arbre binaire avec nœuds contenant des valeurs
• Objectif : Visiter tous les nœuds dans un ordre spécifique
• Contraintes : Différents ordres de parcours selon le besoin

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

def parcours_prefixe(racine):
    if racine:
        print(racine.valeur)           # Traiter la racine
        parcours_prefixe(racine.gauche)  # Parcourir le sous-arbre gauche
        parcours_prefixe(racine.droite)  # Parcourir le sous-arbre droit

def parcours_infixe(racine):
    if racine:
        parcours_infixe(racine.gauche)   # Parcourir le sous-arbre gauche
        print(racine.valeur)             # Traiter la racine
        parcours_infixe(racine.droite)   # Parcourir le sous-arbre droit

def parcours_postfixe(racine):
    if racine:
        parcours_postfixe(racine.gauche) # Parcourir le sous-arbre gauche
        parcours_postfixe(racine.droite) # Parcourir le sous-arbre droit
        print(racine.valeur)             # Traiter la racine

# Exemple d'utilisation
# Construction d'un arbre binaire
racine = Noeud(1)
racine.gauche = Noeud(2)
racine.droite = Noeud(3)
racine.gauche.gauche = Noeud(4)
racine.gauche.droite = Noeud(5)

print("Parcours préfixe:")
parcours_prefixe(racine)  # Affiche: 1 2 4 5 3

• Pour un ABR, le parcours infixé donne les éléments triés
• Pour une copie de l'arbre, le parcours préfixé est approprié
• Pour le calcul d'expressions arithmétiques, le postfixe est utilisé
• Complexité: O(n) pour tous les parcours (visite de chaque nœud une fois)

"Trouver le chemin le plus court entre deux sommets dans un graphe pondéré. Les poids des arêtes représentent des distances, des coûts ou des durées. Le graphe peut contenir des poids négatifs mais pas de cycles négatifs."

• Données : Graphe pondéré avec sommets et arêtes pondérées
• Objectif : Trouver le chemin de poids minimal entre deux sommets
• Contraintes : Poids éventuellement négatifs, pas de cycles négatifs

import heapq

def dijkstra(graphe, depart, arrivee):
    # Initialisation
    distances = {sommet: float('infinity') for sommet in graphe}
    distances[depart] = 0
    precedent = {}
    pq = [(0, depart)]
    
    while pq:
        distance_actuelle, sommet_actuel = heapq.heappop(pq)
        
        if sommet_actuel == arrivee:
            break
            
        if distance_actuelle > distances[sommet_actuel]:
            continue
            
        for voisin, poids in graphe[sommet_actuel].items():
            distance = distances[sommet_actuel] + poids
            
            if distance < distances[voisin]:
                distances[voisin] = distance
                precedent[voisin] = sommet_actuel
                heapq.heappush(pq, (distance, voisin))
    
    # Reconstruction du chemin
    chemin = []
    sommet = arrivee
    while sommet is not None:
        chemin.append(sommet)
        sommet = precedent.get(sommet)
    chemin.reverse()
    
    return distances[arrivee], chemin

# Exemple d'utilisation
graphe = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 1, 'D': 5},
    'C': {'D': 8, 'E': 10},
    'D': {'E': 2},
    'E': {}
}

cout, chemin = dijkstra(graphe, 'A', 'E')
print(f"Coût minimum: {cout}")
print(f"Chemin: {' -> '.join(chemin)}")

• Algorithme de Dijkstra optimal pour graphes à poids positifs
• Complexité O((V+E)log V) - très efficace
• Garantit le chemin optimal
• Utilisation d'une file de priorité pour optimiser la sélection

"Calculer la factorielle d'un nombre n (n!) avec une approche efficace. La factorielle est le produit de tous les entiers positifs inférieurs ou égaux à n. Des appels successifs avec des valeurs proches sont possibles."

• Données : Entier n positif
• Objectif : Calculer n! = n × (n-1) × ... × 2 × 1
• Contraintes : Plusieurs calculs peuvent être effectués, avec des valeurs proches

class MemoFactorielle:
    def __init__(self):
        self.memo = {0: 1, 1: 1}  # Valeurs de base
    
    def calculer(self, n):
        if n in self.memo:
            return self.memo[n]
        
        # Calcul itératif pour remplir les valeurs manquantes
        for i in range(len(self.memo), n + 1):
            self.memo[i] = i * self.memo[i - 1]
        
        return self.memo[n]
    
    def get_factorielles(self, debut, fin):
        """Retourne une liste de factorielles dans une plage"""
        resultats = []
        for i in range(debut, fin + 1):
            resultats.append(self.calculer(i))
        return resultats

# Version simple avec cache
def factorielle_dynamique(n, memo={}):
    if n in memo:
        return memo[n]
    
    if n <= 1:
        memo[n] = 1
        return 1
    
    memo[n] = n * factorielle_dynamique(n - 1, memo)
    return memo[n]

# Exemple d'utilisation
fact_calculator = MemoFactorielle()

print("Calcul de quelques factorielles:")
for i in [5, 6, 7, 10]:
    resultat = fact_calculator.calculer(i)
    print(f"{i}! = {resultat}")

# Calcul de la plage
factories = fact_calculator.get_factorielles(5, 8)
print(f"Factorielles de 5 à 8: {factories}")

• Approche naïve: O(n) pour chaque appel, recalcul complet
• Approche itérative: O(n) pour chaque appel, O(1) espace
• Programmation dynamique: O(n) pour le premier, O(1) pour les suivants
• Avantage de la PD: Réutilisation des calculs précédents