Faisant partie des algorithmes de la théorie des graphes, l’algorithme de Kruskal permet de rechercher un arbre recouvrant de poids minimum.

Une application pratique de l’algorithme de Kruskal consiste à relier tous les ordinateurs d’un même réseau local avec une longueur optimale de fibre optique.

Dans ce billet, vous trouverez une implémentation Java de cet algorithme. Il m’aura permis de résoudre le problème Fibre Optique donné en finale du concours du Meilleur Dev de France 2017.
Continuer la lecture →

Dans ce billet, j’ai eu l’envie de vous partager mon implémentation Java du très célèbre problème du rendu de monnaie dont voici l’énoncé : étant donné un système de monnaie, comment rendre de façon optimale une somme donnée, c’est-à-dire avec le nombre minimal de pièces et de billets ?
Par exemple, dans le système monétaire de l’Euro, la manière la plus optimale de rendre 6 euros consiste à rendre un billet de 5 € et une pièce de 1 €, même si d’autres combinaisons existent (ex : 3 x 2 € ou 6 x 1 €).

Dans le cas d’un système monétaire non canonique, utiliser un algorithme glouton ne donnera pas nécessairement un résultat optimal. Il est nécessaire de passer par la méthode algorithmique dite de programmation dynamique. Continuer la lecture →