De très nombreux exercices sont présentés
- La récursivité intervient souvent.
- La programmation dynamique y est parfois présente (🥼).
- Il y a plusieurs niveaux de difficulté
- Application directe du cours et des méthodes.
- 💥 Nécessite une autre technique ou structure, comme un dictionnaire...
- 💥💥 Nécessite des techniques variées, comme des constructions de fonctions auxiliaires...
- 💥💥💥 Nécessite de réfléchir plus sérieusement...
- Une correction détaillée écrite avec soin est proposée ; ne pas hésiter à l'étudier !
- Il faut comprendre que l'écriture des tests de validation, partie cachée, est également un travail complexe.
- Bonne progression !
Contenus en bonus
- La présence de 🎁 indique un petit cadeau, sous forme de compléments de cours, accessible si vous résolvez correctement un exercice.
- La présence de 🥚 indique un exercice fécond, en plusieurs parties, accessibles progressivement en cas de succès aux premiers. Un joli cadeau se trouve à la fin ; un easter egg.
🥼 Programmation dynamique
Résoudre un problème avec un parcours de liste ou une simple récursivité est techniquement de la programmation dynamique. Techniquement. Mais, il ne faut pas abuser de ce qualificatif...
Nous qualifierons une démarche de programmation dynamique lorsqu'il faudra faire un effort intellectuel de reformulation du problème, avec par exemple la création d'une fonction auxiliaire non proposée qui, elle, permet par récursivité ou parcours de structure de résoudre le problème initial. La récursivité n'étant (jamais) obligatoire.
Le tag 🥼 programmation dynamique ne concernera ici que là où il y aura un effort de la part de l'apprenant de reformulation du problème ou de création auxiliaire.
Vous retrouverez, souvent en indice à dérouler, comment aborder un tel problème.
La bonne démarche intellectuelle est de se demander si la fonction cherchée suffit pour répondre à un problème un peu plus gros. Sinon, se demander quelle fonction auxiliaire légèrement différente, plus générale, est capable de progresser dans la structure étudiée. D'où la notion de programmation dynamique.
Il n'est pas nécessaire de passer par une fonction auxiliaire. Parfois, stocker une variable auxiliaire suffit...
« Comment progresser ? » est la question qui doit vous guider !
Programmation dynamique 🥼
Résoudre un problème par programmation dynamique, c'est reformuler, inventer un nouveau problème qui permet de progresser dans la structure et résoudre le problème initial.
Il y a différentes techniques associées, c'est souvent de calculer une caractéristique supplémentaire de la sous-structure qui permet de faire progresser la résolution du problème dans la structure globale (une liste, un arbre, un graphe, ...).
Cette définition est toute personnelle, fruit d'une longue expérience en la matière.
Arbres binaires
Les premiers exercices sur les structures arborescentes.
Il faut connaitre les bases de la programmation orientée objet (POO).