algorithmique 20 programmation dynamique

« Algorithmique - 20 : Programmation Dynamique – Partie 2 Mise en applications 4.

Quelques mises en activité supplémentaires Exercice 9 : Voici une pyramide de nombres.

En partant du sommet, et en se dirigeant vers le bas à chaque étape, on doit réussir à maximiser le total des nombres traversés.

Sur l'illustration ci-contre, ce maximum est 23 (le chemin est indiqué en rouge). Le but de cet exercice est de chercher la meilleure méthode pour trouver un tel chemin. 1) Choix d'une structure de données pour représenter cette pyramide de nombres Nous allons utiliser la liste suivante pour représenter la pyramide ci-dessus : pyramide = [[3], [7,4], [2,4,6], [8,5,9,3]] question 1 : Ecrire le code Python d'une fonction genere_pyramide(h) qui génère une pyramide de hauteur h d'entiers aléatoires compris entre 1 et 9. La hauteur d'une pyramide est le nombre de ces étages.

Dans l'exemple ci-dessus, la pyramide a pour hauteur 4. question 2 : Ecrire le code Python d'une fonction affiche_pyramide(pyramide) qui affiche en mode texte la pyramide pyramide comme les pyramides sont affichées dans ce support. 2.

Première méthode : en étudiant tous les chemins possibles En se basant sur le raisonnement récursif suivant : → Si hauteur(pyramide) = 1 alors max(pyramide) = élément unique de la pyramide → Sinon max(pyramide) = élément sommet de la pyramide + max(sous_pyramide_gauche, sous_pyramide_droite) question 3 : Ecrire le code Python d'une fonction sous_pyramide_gauche(pyramide) qui récupère la sous pyramide gauche de la pyramide nommée pyramide (on pourra générer le tableau qui modélise la pyramide en compréhension).

Faire de même pour une fonction sous_pyramide_droite(pyramide) qui récupère la sous pyramide droite de la pyramide nommée pyramide. question 4 : Proposer le code Python d'une fonction Python récursive nommée recherche_max_naif(pyramide) qui recherche et retourne la valeur du chemin maximal. question 5 : Testez votre code avec la première pyramide et vérifiez que.... »