Discussion :

[bgre25]

Bonjour,
je commence en algo et j'ai un exercice que je n'arrive pas à réaliser.
"On souhaite realiser un algo qui à partir d'un montant saisie affiche la décomposition de ce montant en billets de 100, 50, 10 euros et en pieces de 2 et 1 euros".
J'ai déterminer les variables qui sont somme:reel
b100 B50 B10 B2 et B1:reel

Merci de m'aider

[Jedai]

Et on te demande d'afficher toutes les combinaisons possibles ? Une seule ? La "meilleure" (selon quel critère ?) ? On a précisé quel type d'algo tu devais utiliser ? glouton, dynamique, autre ?

--
Jedaï

[pseudocode]

Et on te demande d'afficher toutes les combinaisons possibles ? Une seule ? La "meilleure" (selon quel critère ?) ? On a précisé quel type d'algo tu devais utiliser ? glouton, dynamique, autre ?

--
Jedaï

A la vue de énoncé, il y a de grandes chances que le but soit d'implémenter l'algorithme glouton.

[PRomu@ld]

glouton, dynamique,

En fait, restons raisonnables, l'algorithme naïf suffira. N'oublions pas qu'il débute en algorithmique . Pas besoin de se perdre dans les noms compliqués (bien que l'algorithme naïf est glouton )

Ce qu'il faut faire, c'est utiliser massivement (enfin tout est relatif), la division euclidienne et le modulo. Avec ceci tu devrais pouvoir te débrouiller.

L'algorithme naïf est simple, appelons x la somme que tu veux redistribuer. Commences par déterminer le nombre n de billets de 100 dans x. Une fois ceci déterminé, enleve ces n billets à x, tu obtiens un reste r ( inférieur à 100 donc), il faut maintenant déterminer le nombre de billets de 50 dans r et ainsi de suite ...

[pseudocode]

En fait, restons raisonnables, l'algorithme naïf suffira. N'oublions pas qu'il débute en algorithmique . Pas besoin de se perdre dans les noms compliqués (bien que l'algorithme naïf est glouton )

C'est officiel le nom d' "algorithme naïf" ?

Je pensais justement que le nom de cet algo etait "glouton" (ou greedy en anglais).

[Jedai]

C'est officiel le nom d' "algorithme naïf" ?

Je pensais justement que le nom de cet algo etait "glouton" (ou greedy en anglais).

Quel naïveté !

Algorithme "naïf" désigne toujours l'algorithme "le plus simple" pour résoudre un problème (n'étant pas en mathématique, nous nous abstiendrons de définir ce "plus simple"...). Dans notre cas il s'agit de l'algorithme glouton, mais dans d'autres, l'algorithme naïf n'a rien de glouton (par exemple l'algorithme naïf pour déterminer la primalité d'un nombre).

--
Jedaï

[sidahmed]

Et on te demande d'afficher toutes les combinaisons possibles ? Une seule ? La "meilleure" (selon quel critère ?) ? On a précisé quel type d'algo tu devais utiliser ? glouton, dynamique, autre ?

--
Jedaï

C'est pas dans ce type d'algorithmes qu'on parle de glouton (greedy), c'est par exemple dans le cas de l'algorithme de DIJKSTRA pour la recherche du plus court chemin qui utilise une stratégie gloutone lorsqu'il choisit le sommet le moins coûteux à chaque étape !

[Jedai]

C'est pas dans ce type d'algorithmes qu'on parle de glouton (greedy), c'est par exemple dans le cas de l'algorithme de DIJKSTRA pour la recherche du plus court chemin qui utilise une stratégie gloutone lorsqu'il choisit le sommet le moins coûteux à chaque étape !

Bien sûr, bien sûr... Néanmoins l'algorithme que tu as donné est l'algorithme glouton (il choisit toujours de dépenser le maximum du plus gros billet possible), c'est son nom officiel, comment m'expliques-tu ce paradoxe ?

--
Jedaï

[pseudocode]

C'est pas dans ce type d'algorithmes qu'on parle de glouton (greedy)

??

On parle d'algorithme glouton à chaque fois qu'on cherche a approcher la solution globale par la suite des meilleures solutions locales.

Et c'est bien le cas ici. Si tu dois approcher "500" avec "100, 50, 10, 2 et 1 euros", la première "meilleure" solution locale est 100. Et ansi de suite.

[sidahmed]

Bien sûr, bien sûr... Néanmoins l'algorithme que tu as donné est l'algorithme glouton (il choisit toujours de dépenser le maximum du plus gros billet possible), c'est son nom officiel, comment m'expliques-tu ce paradoxe ?

--
Jedaï

En d'autres termes, vu que l'auteur du message est un novice en algorithmique, ça ne vaut pas le coup de parler d'algorithme glouton, c'est pas le niveau ni le sujet de ce post !

[Jedai]

En d'autres termes, vu que l'auteur du message est un novice en algorithmique, ça ne vaut pas le coup de parler d'algorithme glouton, c'est pas le niveau ni le sujet de ce post !

Ah bon, donc il y a bien un algorithme glouton...
De toute façon si je demandais ça c'est parce qu'on pouvait lui avoir fourni des indications dans l'énoncé, ou à part. Il pourrait également être en train de suivre un cours d'algorithmique et être dans la section "Algorithme glouton" ou "Programmation dynamique", ce qui fournit certaines indications sur la réponse attendue. Même un novice en algorithmique peut connaître ces termes, ça fait partie des notions qu'on apprend en premier quand on fait de l'algorithmique.

--
Jedaï

[sbadecoder]

Un petit détail, si tu ne comptes pas utiliser une somme avec des centimes, tu peux te contenter de définir tes variables en integer ou cardinal plutot que real...

[Zavonen]

J'en remet une louche par rapport au post précédent. A propos des centimes et pour ce genre de problèmes ne JAMAIS utiliser de flottants! Toujours travailler, pour les traitements, avec l'unité la plus petite et avec des entiers éventuellement longs, quitte à remettre des virgules pour les entrées sorties.
La raison:
1.20 +0.30+0.50 a toutes les chances de ne pas faire 2 ...
En outre, le problème est 'naturellement' récursif.
Le truc devient un peu plus intéressant quand le stock de chaque unité est limité (problème du distributeur) et qu'il faut donner 2+2+1 parce qu'on n'a plus de 5...

[Hephaistos007]

Un algo dit "glouton", signifie simplement que certains résultats ne seront plus remis en question (un glouton est quelqu'un qui avale et ne peut pas revenir en arrière, c'est-à-dire ne peut pas remettre en cause ce qu'il vient de faire).

[esco123]

l'algorithme glouton est très intéressant pour résoudre un certains nombre de programme cependant j'ai un problème pour ce qui est d'obtenir toutes les combinaisons possibles...
par exemple nous avons 400e et les billets et pièces de 200 100 50 20 10, et je n'arrive pas a obtenir toutes les combinaisons...