Décomposition d'un problème en sous-problèmes

 Posté le January 29, 2023  |  1 minutes  |  57 mots  |  David Latreyte

Principe

  • On décompose le problème en sous-problèmes plus simples.
  • On résout les sous-problèmes.
  • On combine les sous-problèmes de façon à construire la solution du problème initial.

Indépendance des sous-problèmes

  • Si les sous-problèmes sont indépendants les uns des autres : « Diviser pour règner ».
  • Si les sous-problèmes dépendent les uns des autres : « Programmation dynamique ».
Diviser pour régner  Programmation dynamique 

Problème du rendu de monnaie

 Posté le February 28, 2021  |  12 minutes  |  2398 mots  |  David Latreyte

Énoncé du problème Un commerçant cherche à rendre la monnaie à ses clients de façon optimale, c’est-à-dire avec le nombre minimal de pièces et de billets. Dans ce problème, On suppose que les clients ne donnent que des sommes entières en euros (pas de centimes pour simplifier) ; Les valeurs des pièces et billets à disposition sont : 1, 2, 5, 10, 20, 50, 100, 200 et 500. On suppose que l’on a autant d’exemplaires que nécessaire de chaque pièce et billet ; Dans la suite, afin de simplifier, on désigne par « pièces » à la fois les pièces et les billets. [Voir plus]
Programmation dynamique 

Autour de la suite de Fibonacci

 Posté le February 25, 2021  |  13 minutes  |  2563 mots  |  David Latreyte

Rappel : récursivité terminale La définition de la fonction factorielle est $$ n! = \begin{cases} 1 & \text{if } n = 0 \cr n \times (n-1)! & \text{sinon} \end{cases} $$ Définir la fonction fact_env qui calcule la factorielle d’un entier naturel $n$, sans oublier le jeu de tests. La spécification de la fonction est : 1 2 3 4 5 6 def fact_env(n: int) -> int: """ Retourne la factorielle de n. [Voir plus]
Récursivité  Récursivité terminale  Récursivité enveloppée  Programmation dynamique  Mémoïsation