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ï

[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ï

[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.