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 :

Aide pour un exercice sur un algorithme "glouton"


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Novembre 2018
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Vaucluse (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2018
    Messages : 1
    Points : 1
    Points
    1
    Par défaut Aide pour un exercice sur un algorithme "glouton"
    Bonjour, je suis étudiant à l'université et j'ai un exercice à réaliser que je ne comprends absolument pas... Pourriez-vous m'aider ? Voici l'énoncé, la moindre explication, aide serait la bienvenue !

    Soit n le nombre de pièces distinctes et soit P, un tableau, dont les indices vont de 1 à n contenant la valeur des n pièces. On suppose ici que nous disposons d'un nombre illimité de chaque type de pièce. Soit L le montant dont on veut obtenir la monnaie. Dans ce problème, les valeurs des pièces sont strictement positives. Le montant à remettre est un nombre entier non négatif. On assume que le tableau P est en ordre croissant.
    Nous allons utiliser une matrice C de n lignes numérotées de 1 à n et L + 1 colonnes numérotées de 0 à L où C[i,j] contient le nombre minimal de pièces pour rendre la monnaie d'un montant j si l'on se limite seulement qu'aux pièces de valeurs P1,P2, ... , Pi. Si la monnaie ne peut être rendue, C[i,j] sera égal à l'infini.

    Les questions sont les suivantes :
    - Donner une équation de récurrence pour C[i,j]. N'oubliez pas les cas de base. Aide : Complétez ce qui suit.

    C[i,j] = ... si j = 0, ... si i = 1 et ... , ... si i = 1 et ..., ... si j < Pi, ... sinon.

    - Décrivez en pseudo-code un algorithme de programmation dynamique pour calculer tous les éléments de la dernière ligne du tableau C, c’est-à-dire les C[n,j] pour 0 ≤ j ≤ L. Votre algorithme ne doit utiliser qu’un seul tableau à une dimension de longueur L + 1 et non pas un tableau à deux dimensions comme le tableau C.

    - Donnez la complexité de votre algorithme en fonction de n et de L.

    - Décrivez en pseudo-code un algorithme glouton capable de faire la monnaie en un nombre minimal de pièces une fois les C[n,j] calculés, pour un montant quelconque M ≤ L. Votre algorithme recevra donc en entrée la dernière ligne de la matrice C, le tableau P ainsi que le montant M. Votre algorithme donne-t-il toujours la solution optimale ?

    - Donnez la complexité de l’algorithme trouvé en (d) en fonction de n.


    Merci d'avance pour toute réponse qui puisse m'aider à résoudre cet exercice !

  2. #2
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Bonjour

    Qu'as-tu fait ?
    Personne ne fera ton travail à ta place.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Points : 1 453
    Points
    1 453
    Par défaut
    Que c'est beau !
    Arriver à produire un énoncé aussi abscons pour une opération aussi simple que rendre la monnaie ...
    Un problème général de l'enseignement en France ?
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  4. #4
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Citation Envoyé par Nebulix Voir le message
    une opération aussi simple que rendre la monnaie ...
    Es-tu ironique ?
    Rendre la monnaie est un problème mathématique classique : le problème du sac à dos.
    Ce dernier est suffisamment insoluble pour servir de pilier en cryptographie.


    A la boulangerie, il n'est facile de payer (ou rendre la monnaie) que parce que la suite est hypergéométrique. 1 2 5 10 20 50 100 200 500 ...
    Mais si les pièces valaient 17, 23 et 43 centimes, il serait difficile, voire insoluble, de payer une baguette 1.10€.
    1.09€ si tu veux, mais pas 1.10€.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  5. #5
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Points : 1 453
    Points
    1 453
    Par défaut
    Les valeurs des pièces sont faites pour qu'on puisse rendre la monnaie. Il m'a semblé que l'énoncé se plaçait dans ce contexte. Le problème du sac à dos est différent puisque les "pièces" ont des valeurs moins bien ajustées, que leur nombre est limité , etc. Mais il peut s'exprimer simplement. Ce qui n'empêche pas qu'il soit très difficile à résoudre.
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  6. #6
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 409
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 409
    Points : 5 799
    Points
    5 799
    Par défaut
    salut

    rien ne sert de se battre cet exercice est un classique ... je l'ai développé en première
    il a rien de compliqué, ce n'est pas le problème du sac a dos, il n'y a pas de contrainte de nombre ni d'espace

    le truc c'est de juste de déduire du montant la valeur maximal des pièces en notre possession jusqu’à ce que le montant atteigne zéro
    rien de bien compliqué

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    Montant = x 
    Mrendu  = 0 ;
    Impossible = Faux
    TansQue (Montant >= 0) and (Impossible = Faux) Faire 
        Cherchevaleur(TabMonnaie,Montant,Mrendu,Impossible);
        Montant := Montant- Mrendu;
    Fin TansQue;
    je laisse le soin de définir cherchevaleur ... mais une petite recherche dichotomique me parait s'imposer

    bien a vous les contributeurs ^^
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  7. #7
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Points : 1 453
    Points
    1 453
    Par défaut
    En utilisant les opérateurs de division entière DIV et MOD ...
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

Discussions similaires

  1. aide pour un exercice sur les tableaux
    Par mimiif dans le forum Caml
    Réponses: 9
    Dernier message: 30/05/2008, 16h49
  2. Aide pour un exercice sur sql
    Par stèfv96 dans le forum Langage SQL
    Réponses: 7
    Dernier message: 10/01/2008, 18h14
  3. Besoin d'aide pour un exercice sur les registres
    Par zakuza dans le forum Assembleur
    Réponses: 5
    Dernier message: 14/04/2006, 15h23

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