IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme glouton et problème du rendu de monnaie


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    Juillet 2011
    Messages
    2
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2011
    Messages : 2
    Par défaut Algorithme glouton et problème du rendu de monnaie
    Bonjour à tous,
    J'ai une petit problème ...

    Je dispose de N pièces en nombre illimité, des pièces de valeur (a1 , a2 , . . . , an )

    Je veux construire un algorithme qui détermine si l'Algorithme de Glouton est optimal pour un ensemble de pièce donné.

    Merci de votre aide

  2. #2
    Inactif  
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    Janvier 2007
    Messages
    6 604
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 64
    Localisation : France

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : Janvier 2007
    Messages : 6 604
    Par défaut
    Amusant.

    Sans réfléchir à fond je dirai que l'algorithme glouton (c'est pas un nom propre : il n'a pas été inventé par un monsieur appelé Glouton ) doit être optimal si la différence de valeur entre deux pièces de rang N et N+1 est toujours inférieur à la différence entre celles de rang N+1 et N+2 (considérant les pièces rangées en ordre croissant de valeur).

    Mais je répond par intuition, ne m'étant pas penché sur la question.

    En tout cas, il me semble qu'il n'est pas optimal si cette condition n'est pas rempli.

    Et bien entendu, on suppose que tu considères que l'optimal est celui qui minimise le nombre de pièces pour une valeur globale donnée.

  3. #3
    Candidat au Club
    Profil pro
    Inscrit en
    Juillet 2011
    Messages
    2
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2011
    Messages : 2
    Par défaut
    Merci beaucoup ! Ça ma permis d’avancer mais ce n'est malheureusement pas l'unique condition

  4. #4
    Inactif  
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    Janvier 2007
    Messages
    6 604
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 64
    Localisation : France

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : Janvier 2007
    Messages : 6 604
    Par défaut
    Ne connaissant pas du tout la question, comme je l'ai écrit au dessus, j'ai fait une rapide recherche, et la solution sur l'"optimalité" de l'algorithme glouton dans le cadre du problème dit du "rendu de monnaie" est .... sur wikipédia.

    http://fr.wikipedia.org/wiki/Algorithme_glouton
    http://fr.wikipedia.org/wiki/Probl%C...ndu_de_monnaie

    Dans le deuxième lien, tu as tout ce qu'il te faut.

  5. #5
    Futur Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Janvier 2012
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : Janvier 2012
    Messages : 4
    Par défaut programmation dynamique : rendu de monnaie
    Salut tout le monde !!
    Bon j'ai un mini projet a realiser , sur le probleme de rendu de monnaie partie dynamique , j'ai fait l'lagorithme dynamique mais quand j'ai fait la traduction en C il ne marche pas , je vous prie de m'aider .
    L'algorithme consiste a rendre un couple composé d'une part par le minimum de pieces d'une façon optimale et d'une autre un tableau indiquant les pieces a rendre ! voilà l'algorithme et le C

    Algorithme dynamique :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
     
    Fonction  P(S,n)
    Début
    	Si n=0 alors
    		retourner +8 ;
    	Sinon Si n=1 et V[1]=1
    		retourner S ;
    	Sinon Si  S=0 alors
    		retourner 0 ;
    	Sinon
    		Pour i= 1 à n faire
    			Si S<V[i] alors
    				P(S,i)= P(S,i-1) ;
    				Nmin= P(S,i) ;
    			Sinon
    				P(S,i)= min(p(S,i-1) ;P(S-V[i]),i)+1) ;
    			Nmin= P(S,i) ;
    			Fin Si
    		Fin Pour
    	Fin Si
    	Fin Si
    	Fin Si
    	Retourner Nmin ;
    Fin 
     
    Fonction	R(V,P,S)  
    	K= 1 ;
    	Si V[X]*P(S-V[i],X)> S alors 
    		X= X-1 ;
    	Fin Si
    	Tant que (V[X]*P(S-V[i], X)<= S ) et ( k <= Nmin ) faire 
    		j ? P(S-V[i],X) ;
    		Répéter 
    			T[k] = V[X] ;
    			k = k+1 ;
    			j = j-1 ;
    		Jusqu’a : j=1
    		X = X-1 ;
    	Fin Tant que
    Fin

  6. #6
    Membre très actif
    Profil pro
    Inscrit en
    Février 2010
    Messages
    767
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2010
    Messages : 767
    Par défaut
    Ne cherche pas à faire l'algorithme optimal, c'est trop compliqué à faire.
    Tous les automates utilisent l'algorithme glouton, en commençant par rendre la pièce ou le billet maximal.

  7. #7
    Inactif  
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    Janvier 2007
    Messages
    6 604
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 64
    Localisation : France

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : Janvier 2007
    Messages : 6 604
    Par défaut
    Citation Envoyé par Jimmy_ Voir le message
    Tous les automates utilisent l'algorithme glouton, en commençant par rendre la pièce ou le billet maximal.
    L'algorithme glouton est l'algorithme optimal sur les systèmes monétaires canoniques.
    Or, depuis 72 ( ou 71 ou 73 ? bref, l'année de la réforme monétaire britannique), tous les systèmes monétaires occidentaux sont canoniques (pour les autres, je ne sais pas).

Discussions similaires

  1. Réponses: 4
    Dernier message: 03/02/2014, 09h55
  2. Problème de rendu 16 bits float + MSAA
    Par gybe dans le forum DirectX
    Réponses: 10
    Dernier message: 10/08/2006, 16h24
  3. [wxPython] problème de rendu
    Par tool69 dans le forum wxPython
    Réponses: 5
    Dernier message: 25/09/2005, 19h43
  4. [Lisp] Algorithme glouton
    Par TomCat1664 dans le forum Lisp
    Réponses: 2
    Dernier message: 04/01/2005, 12h19
  5. Problème de rendu 2D
    Par Freakazoid dans le forum DirectX
    Réponses: 6
    Dernier message: 04/08/2004, 21h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo