J'ai un problème dans mon projet informatique

MFQT216 - 12 mai 2024 à 10:07
jee pee Messages postés 39826 Date d'inscription mercredi 2 mai 2007 Statut Modérateur Dernière intervention 7 juin 2024 - 13 mai 2024 à 16:04

Mon projet est de réaliser un programme de rendu de monnaie à l'aide de la programmation dynamique et nous devons valider des compétences. Ma compétence est représenter l'organisation des données voici mon texte : 

D'abord il faut définir notre ensemble des pièces de monnaie disponibles. Ceci est important pour déterminé quelle(s) pieces(s) nous pouvons utiliser pour rendre une somme donnée.

Lorsqu'on initialise notre algorithme de programmation dynamique, nous utilisons cet ensemble qui sera sous forme de liste pour déterminer les options disponibles. Par exemple, si nous disposons de pièces de 1 euros, 2 euros, 5 euros et 10 euros nous utlisions donc la liste [1,2,5,10] pour savoir quelles pièces nous pouvons utiliser pour rendre une somme donnée.

Ensuite, on aura besoin *d'un tableau de programmation dynamique *: Le tableau de programmation dynamique est utilisé pour stocker les résultats intermédiaires de notre algorithme.

Chaque *indice* de ce tableau représente le nombre minimum de pièces nécéssaires pour rendre une certaine somme d'argent.

Par exemple : si nous avons un tableau "argent" alors argent[i] représente le nombre minimum de pièces nécéssaires pour rendre la somme 'i' comme dans le cas où on utliserai le systeme précédent cela donnerait : *[(0,0,0),(1,0,0),(2,0,0),(2,1,0)...]*

Ce qui est entre '*' est faux selon mon prof aidez moi à trouvez et corriger les erreurs svp

3 réponses

jee pee Messages postés 39826 Date d'inscription mercredi 2 mai 2007 Statut Modérateur Dernière intervention 7 juin 2024 9 214
Modifié le 12 mai 2024 à 13:04

Bonjour,

1/ *d'un tableau de programmation dynamique *: Je dirais que l'on aura besoin d'un algorithme pour trouver le nombre optimum de pièces à rendre. On ne va pas enregistrer, à l'avance, toutes les possibilités.

2/ *indice* Ton indice c'est juste le numéro d'une possibilité. Pas le nombre de pièces à rendre qui devrait être la somme des valeurs du tableau d'indice i. Même si le tableau argent[] n'a pas de raison d'exister (cf 1), avec 4 pièces, ton exemple du tableau avec seulement 3 compteurs n'est pas cohérent.


1
yg_be Messages postés 22859 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 7 juin 2024 1 474
13 mai 2024 à 15:55

Habituellement, en programmation dynamique, on mémorise toutes les solutions des sous-ensembles du problème, puis on parcourt très rapidement cela pour trouver la solution au problème.

La clé de tout cela, c'est de définir intelligemment quels sont ces sous-ensembles:

  • d'une part, afin d'avoir un nombre réduit de sous-ensembles, bien moindre que le nombre de combinaisons possibles
  • d'autre part, afin de pouvoir évaluer rapidement toutes ces solutions, chaque sous-problème étant évalué en utilisant les solutions aux sous-problèmes évalués précédement

C'est une façon assez fascinante de résoudre des problèmes d'optimisation.  Au départ, c'est beaucoup moins intuitif que la récursivité, et, pour certains problèmes, extrèmement plus efficace.

0
jee pee Messages postés 39826 Date d'inscription mercredi 2 mai 2007 Statut Modérateur Dernière intervention 7 juin 2024 9 214 > yg_be Messages postés 22859 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 7 juin 2024
13 mai 2024 à 16:04

D'accord. Je vois bien l'utilisation si par exemple pour la monnaie à rendre, on avait la caisse du supermarché devant nous, avec tant de pièces pour chaque valeur.

0
yg_be Messages postés 22859 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 7 juin 2024 1 474
13 mai 2024 à 08:22

bonjour,

ton tableau n'est pas correct.  cela devrait être:

[(0,0,0),(1,0,0),(0,1,0),(1,1,0)...]

Surtout, tu as écrit tout cela avant d'avoir précisément compris comment ton algorithme de programmation dynamique allait se comporter.  Tu écris des généralités, sans décrire ton algorithme.

0
yg_be Messages postés 22859 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 7 juin 2024 1 474
13 mai 2024 à 08:29

Es-tu certain de disposer d'un nombre infini de piéces de chaque valeur?  Si c'est le cas, je ne vois pas l'interet d'utiliser un algorithme de programmation dynamique pour faire ce calcul.

0