Cette page propose plusieurs exercices corrigés sur les algorithmes, plus particulièrement comprendre la différence entre le paradigme Divide & Conquer (Diviser pour régner) et la programmation dynamique. Les spécificités de la recherche de chemin (plus court chemin), problème de planification, problème de flot maximum et plus généralement la théorie des graphes est traitée à part.
Exercice 1
L’algorithme de force brute est trivial : une boucle.
A chaque niveau l, l’arbre binaire complet est composé de 2^(l-1) feuille. Donc le total des sommets est 2^l -1. Soit l le niveau de l’arbre, donc l=sup(log_2 (n)).
Exercice 2
Supposons que votre tableau d’entrée s’appelle A. Ce que vous devez faire est de former un autre tableau, disons B, dont chaque valeur i est calculée en utilisant la formule récursive, max(A[i], B[i-1]+A[i ])
Ce que vous faites effectivement, c’est que vous choisissez d’étendre la fenêtre précédente ou d’en démarrer une nouvelle. Vous pouvez le faire puisque vous n’êtes censé sélectionner que des éléments continus dans le cadre de vos sous-ensembles.
5, -6, 7, 12, -3, 0, -11, -6
La réponse serait 19 (du sous-tableau {7,12} )
Exercice 3
Utilisez la sous-chaîne commune la plus longue pour : BDCABA et ABCBDAB. L’algorithme est décrit comme suit:
Exercice 4
Adaptez la sous-chaîne commune la plus longue à la sous-séquence commune la plus longue : BDCABA et ABCBDAB. Le problème de la plus longue sous-séquence commune (LCS) consiste à trouver la plus longue sous-séquence commune à toutes les séquences d’un ensemble de séquences (souvent seulement deux séquences).
Cela diffère des problèmes de recherche de sous-chaînes communes : contrairement aux sous-chaînes, les sous-séquences ne sont pas obligées d’occuper des positions consécutives dans les séquences d’origine.
Exercice 5
La distance de Levenshtein est une métrique de chaîne permettant de mesurer la différence entre deux séquences. De manière informelle, la distance de Levenshtein entre deux mots est le nombre minimum de modifications d’un seul caractère (c’est-à-dire des insertions, des suppressions ou des substitutions) nécessaires pour changer un mot en l’autre. Proposer un programme dynamique pour résoudre ce problème. Essai avec MEILENSTEIN et LEVENSHTEIN.
Exercice 6
Alice et Bob jouent à tour de rôle à un jeu, Alice commençant en premier.
Initialement, il y a un nombre n au tableau. Au tour de chaque joueur, ce joueur effectue un coup consistant en :
Choisir n’importe quel x avec 0 < x < n et n % x == 0.
Remplacer le nombre n au tableau par n – x.
De plus, si un joueur ne peut pas bouger, il perd la partie.
Renvoyer vrai si et seulement si Alice gagne la partie, en supposant que les deux joueurs jouent de manière optimale.
Exemple 1:
Entrée : n = 2
Sortie : vrai
Explication : Alice choisit 1 et Bob n’a plus de coups.
Exemple 2 :
Entrée : n = 3
Sortie : faux
Explication : Alice choisit 1, Bob choisit 1 et Alice n’a plus de coups.
Pour répondre à ce problème, nous allons construire un tableau de solution. dp[i] indique le résultat du jeu pour le nombre donné i et pour le joueur qui a commencé la partie. Alice essaiera tous les facteurs et choisira celui qui donne à son adversaire une valeur perdante.
Il est aussi possible de résoudre ce problème de manière récursive plus classique, appelé Top-Down.
Et pour un côté plus pratique nous allons ajouter une mémoïsation.
Exercice 7
On vous donne un coût de tableau d’entiers où coût[i] est le coût de la ième marche d’un escalier. Une fois que vous avez payé le coût, vous pouvez monter une ou deux marches.
Vous pouvez soit démarrer à partir de l’étape avec l’indice 0, soit à partir de l’étape avec l’indice 1.
Renvoyez le coût minimum pour atteindre le sommet de l’étage.
Exemple 1:
Entrée : coût = [10,15,20]
Sortie : 15
Explication : Vous commencerez à l’index 1.
– Payez 15 et montez deux marches pour atteindre le sommet.
Le coût total est de 15.
Exemple 2 :
Entrée : coût = [1,100,1,1,1,100,1,1,100,1]
Sortie : 6
Explication : Vous commencerez à l’index 0.
– Payez 1 et montez deux marches pour atteindre l’indice 2.
– Payez 1 et montez deux marches pour atteindre l’indice 4.
– Payez 1 et montez deux marches pour atteindre l’indice 6.
– Payez 1 et montez d’une marche pour atteindre l’indice 7.
– Payez 1 et montez deux marches pour atteindre l’indice 9.
– Payez 1 et montez une marche pour atteindre le sommet.
Le coût total est de 6.
Pour un premier jet, nous allons résoudre ce problème en récursif. Pour cela nous gardons en mémoire le plus petit coût en considérant que l’on fasse marche arrière d’une marche et de deux marches. Et ainsi de suite jusqu’à avoir le coût de la première ou deuxième marche.
mincost(0) = cost[0]mincost(1) = cost[1]
mincost(i) = cost[i]+min(mincost(i-1), mincost(i-2))
Ce qui donne le code suivant :
Dans un second temps, nous allons rester en approche top-down et ajouter un système de mémoïsation. Ainsi, un minCost déjà trouver ne sera pas recalculer par la suite.
Enfin, nous allons prendre le problème en bottom-up pour faire de la programmation dynamique;
Exercice 8
Alice et Bob jouent à un jeu avec des tas de pierres. Il y a un nombre pair de piles disposées dans une rangée, et chaque pile a un nombre entier positif de piles de pierres[i].
L’objectif du jeu est de terminer avec le plus de pierres. Le nombre total de pierres sur toutes les piles est impair, il n’y a donc pas d’égalité.
Alice et Bob se relaient, Alice commençant en premier. A chaque tour, un joueur prend toute la pile de pierres soit depuis le début soit depuis la fin de la rangée. Cela continue jusqu’à ce qu’il n’y ait plus de piles, à quel point la personne avec le plus de pierres gagne.
En supposant qu’Alice et Bob jouent de manière optimale, renvoyez true si Alice gagne la partie, ou false si Bob gagne.
Entrée : pierres = [5,3,4,5]
Sortie : vrai
Alice commence en premier et ne peut prendre que les 5 premiers ou les 5 derniers.
Disons qu’elle prend les 5 premiers, de sorte que la ligne devient [3, 4, 5].
Si Bob prend 3, alors le tableau est [4, 5], et Alice prend 5 pour gagner avec 10 points.
Si Bob prend les 5 derniers, alors le tableau est [3, 4], et Alice prend 4 pour gagner avec 9 points.
Cela a démontré que prendre les 5 premiers était un coup gagnant pour Alice, nous retournons donc vrai.
Commençons par une approche top-down avec mémoïsation.
- Veuillez noter que les deux joueurs jouent de manière optimale, nous jouons donc de manière optimale, peu importe qui est Alice, qui est Bob.
- Soit dp(left, right) return [firstScore, secondScore] où firstScore est le score maximum lorsque le joueur1 joue en premier, secondScore est le score maximum lorsque le joueur2 joue en second, il ramasse des pierres en piles[left]…piles[right ].
- Pour les pierres en tas[left]…piles[right], il y a 2 choix pour le joueur1 à choisir :
- Choisissez à gauche : pickLeft = dp(gauche + 1, droite).
- Le score du joueur1 = piles[left] + le score du deuxième choix de pickLeft, donc firstScore = piles[left] + pickLeft[1]
- Le score du joueur2 = score du premier choix de pickLeft, donc secondScore = pickLeft[0]
- Choisir à droite : pickRight = dp(gauche, droite – 1).
- Le score du joueur1 = piles[right] + le deuxième score de pickRight, donc firstScore = piles[right] + pickRight[1]
- Le score du joueur2 = score du premier choix de pickRight, donc secondScore = pickRight[0].
- Choisissez à gauche : pickLeft = dp(gauche + 1, droite).
- Nous devons obtenir le score maximum lorsque le joueur 1 joue en premier parmi plus de 2 choix.
- Enfin, dp(0, len(piles) – 1) return [firstScore, secondScore], où alexScore = firstScore puisque Alice joue en premier, leeScore = secondScore puisque Bob joue en second.
Maintenant on va faire un algorithme en bottom-up en gardant la mémoïsation. Ainsi l’algorithme sera en programmation dynamique.
Exercice 9
Il y a n soldats debout en ligne. Chaque soldat se voit attribuer une valeur de classement unique.
Vous devez former une équipe de 3 soldats parmi eux selon les règles suivantes :
Choisissez 3 soldats avec l’indice (i, j, k) avec le classement (classement[i], classement[j], classement[k]).
Une équipe est valide si : (rating[i] < rating[j] < rating[k]) ou (rating[i] > rating[j] > rating[k]) où (0 <= i < j < k < n).
Renvoyez le nombre d’équipes que vous pouvez former compte tenu des conditions. (les soldats peuvent faire partie de plusieurs équipes).
Exemple 1:
Entrée : note = [2,5,3,4,1]
Sortie : 3
Explication : On peut former trois équipes compte tenu des conditions. (2,3,4), (5,4,1), (5,3,1).
Exemple 2 :
Entrée : note = [2,1,3]
Sortie : 0
Explication : Nous ne pouvons former aucune équipe compte tenu des conditions.
Il est facile de faire un algorithme glouton. Ce dernier est en O(n^3) donc on va essayer d’améliorer la complexité avec de la programmation dynamique.
Voici l’idée principale dans la version programmation dynamique :
Premièrement, nous calculons ce cas note[i] > note[j] > note[k] étant donné que i > j > k. Ensuite, calculez le cas note[i] < note[j] < note[k].
Définir dp[i] : combien d’éléments dans la notation de 0 à i-1 sont inférieurs à la notation[i].
Pour chaque fois que nous avons trouvé note[i] > note[j], nous accumulons dp[j]. Ici, dp[j] signifie combien de notes[k] existent de 0 à j-1. C’est-à-dire, combien de cas satisfont la note[i] > la note[j] > la note[k].
Exercice 10
On vous donne un tableau de prix où prix[i] est le prix d’une action donnée le ième jour, et des frais entiers représentant des frais de transaction.
Trouvez le profit maximum que vous pouvez réaliser. Vous pouvez effectuer autant de transactions que vous le souhaitez, mais vous devez payer les frais de transaction pour chaque transaction.
Remarque : Vous ne pouvez pas vous engager dans plusieurs transactions simultanément (c’est-à-dire que vous devez vendre l’action avant d’acheter à nouveau).
Entrée : prix = [1,3,2,8,4,9], frais = 2
Sortie : 8
Explication : Le profit maximal peut être atteint en :
– Acheter à des prix [0] = 1
– Vendre à des prix[3] = 8
– Acheter à des prix [4] = 4
– Vendre à des prix[5] = 9
Le bénéfice total est ((8 – 1) – 2) + ((9 – 4) – 2) = 8.
Commençons dans un premier temps avec l’approche top-down.
- Soit dp(i, canBuy) le profit maximum que nous pouvons tirer des prix[i..n-1] avec le drapeau canBuy == True signifie que nous pouvons acheter le ième jour.
- Pour le ième jour nous avons 2 options :
- Ignorez-le : profit = dp(i+1)
- Achetez-le ou vendez-le
- Si achat : profit = dp(i+1) – prix[i]
- Si vente : profit = dp(i+1) + prix[i] – commission
On va convertir en une approche bottom-up pour faire de la programmation dynamique plus traditionnelle.
Soit dp[i][j] le profit maximum que nous pouvons tirer des prix[i..n-1] avec le drapeau j == 1 signifie que nous pouvons acheter le ième jour.
Puisque notre dp n’accède qu’à 2 états : l’état dp actuel dp, l’état dp précédent dpPrev. Nous pouvons optimiser à O(1) dans la complexité de l’espace.
Exercice 11
Vous avez prévu un voyage en train un an à l’avance. Les jours de l’année au cours desquels vous voyagerez sont donnés sous la forme d’un nombre entier de jours. Chaque jour est un entier compris entre 1 et 365.
Les billets de train sont vendus de trois manières différentes :
un pass 1 jour est vendu au prix de [0] dollars,
un laissez-passer de 7 jours est vendu pour des coûts [1] dollars, et
un laissez-passer de 30 jours est vendu pour des coûts [2] dollars.
Les laissez-passer permettent autant de jours de voyage consécutifs.
Par exemple, si nous obtenons un pass 7 jours le jour 2, nous pouvons voyager pendant 7 jours : 2, 3, 4, 5, 6, 7 et 8.
Renvoyez le nombre minimum de dollars dont vous avez besoin pour voyager chaque jour dans la liste de jours donnée.
Entrée : jours = [1,4,6,7,8,20], coûts = [2,7,15]
Sortie : 11
Par exemple, voici une façon d’acheter des laissez-passer qui vous permet de voyager selon votre plan de voyage :
Le jour 1, vous avez acheté un pass 1 jour pour un coût[0] = 2 $, qui couvrait le jour 1.
Le jour 3, vous avez acheté un pass de 7 jours pour un coût[1] = 7 $, qui couvrait les jours 3, 4, …, 9.
Le jour 20, vous avez acheté un pass d’un jour pour un coût[0] = 2 $, qui couvrait le jour 20.
Au total, vous avez dépensé 11 $ et couvert tous les jours de votre voyage.
Nous allons voir ici l’approche bottom-up car le raisonnement est très similaire au problème de sac-à-dos (knapsack) dans la construction de la solution.
dp[i] signifie jusqu’au ième jour le coût minimum des billets. La taille du tableau dp dépend du dernier jour de voyage, nous n’avons donc pas besoin d’une longueur de tableau de 365.
Nous avons besoin d’un tableau booléen pour marquer les jours de voyage, la raison en est que si ce n’est pas un jour de voyage, nous n’avons pas besoin de billet. Cependant, s’il s’agit d’un jour de voyage, nous envisageons trois scénarios (avec trois types de tickects) :
Si un ticket 1 jour le jour i, dp[i] = dp[i – 1] + coût[0]
Si un billet de 7 jours se termine le jour i, dp[i] = min(dp[i – 7], dp[i – 6] … dp[i – 1]) + coût[1]
Si un ticket de 30 jours se termine le jour i, dp[i] = min(dp[i – 30], dp[i – 29] … dp[i – 1]) + coût[2]
Mais puisque la valeur de dp array augmente, donc :
Pour un ticket 7 jours se terminant le jour i, dp[i] = dp[i – 7] + coût[1]
Pour un ticket 30 jours se terminant le jour i, dp[i] = dp[i – 30] + coût[2]
Exercice 12
On vous donne un tableau de valeurs entières où values[i] représente la valeur du ième site touristique. Deux sites touristiques i et j ont une distance j – i entre eux.
Le score d’une paire (i < j) de sites touristiques est valeurs[i] + valeurs[j] + i – j : la somme des valeurs des sites touristiques, moins la distance qui les sépare.
Renvoie le score maximum d’une paire de sites touristiques.
Entrée : valeurs = [8,1,5,2,6]
Sortie : 11
Nous avons i = 0, j = 2, valeurs[i] + valeurs[j] + i – j = 8 + 5 + 0 – 2 = 11
Supposons que nous choisissions le site [i,…j]. La partition peut être décomposée en 2 parties.
La première partie est le startGain que vous gagnez en commençant à un certain point i. Notez que startGain[i] = a[i] + i.
La deuxième partie est le endGain qui est le montant que vous gagnez en terminant à un certain point j. Notez que endGain[i] = a[j] – j.
Notez que endGain peut être négatif.
Le gain global pour [i,…j] n’est rien d’autre que startGain[i] + endGain[j]. (Cela peut être facilement vérifié par les définitions).
Nous devons maximiser le gain global.
Quelles sont les positions possibles pour commencer le voyage ? Il est clair que nous pouvons tout commencer sauf le dernier élément. Ainsi, le voyage optimal doit commencer à l’un de ces éléments.
Supposons que nous ne soyons autorisés à commencer un voyage qu’à i. Quel est le montant maximum que nous pouvons gagner dans ce cas ? Eh bien, puisque le startGain est fixe, nous devons maximiser le endGain. Nous pouvons le faire en nous arrêtant à un élément qui a le maximum endGain à condition qu’il apparaisse à droite de i.
Comme indiqué ci-dessus, pour chaque i, nous devons trouver le endGain maximal à sa droite.
maxEndRight[i] = max(maxEndRight[i+1], endGain[i+1]) = max(maxEndRight[i+1], a[i+1] – (i+1))
maxEndRight[i] représente le endGain le plus élevé que vous pouvez obtenir en vous arrêtant à n’importe quel point strictement à droite de i. Puisque par définition, nous connaissons déjà endGain[i+1] (le gain le plus élevé possible en terminant à n’importe quel point à droite de i+1), nous n’avons qu’à vérifier la possibilité de savoir si s’arrêter à i+1 serait bénéfique ou non. D’où la définition de DP.
Pour chaque i valide, overallGain[i] = startGain[i] + maxEndRight[i] = a[i] + i + maxEndRight[i]
Notez que maxEndRight[i] ne dépend que de maxEndRight[i+1]. Par conséquent, nous pouvons utiliser 2 variables pour suivre les valeurs précédentes.
Puisque nous avons besoin de la valeur de maxEndRight[i+1] pour calculer la valeur de maxEndRight[i], nous commençons donc les itérations à l’arrière.
Comme indiqué, les voyages ne peuvent pas commencer au dernier élément, donc la boucle for commence à i=n-2. Pour cette valeur, maxEndingRight est initialisé à endGain[lastIndex] car c’est le seul moyen possible de terminer le voyage.
FR 
EN 
RU 
ES