Récursivité dans un système "monnayeur"

Question

Bonsoir,


Voilà je dois réaliser l'algorithme et le codage en Pascal d'un
"monayeur non optimisé". Ce que j'entends par là c'est qu'on dispose de
pièces de monnaie (2?, 1?, 0,5?, 0,2?, 0,1?, 0,05?, 0,02?, 0,01?) et
que l'on doit donner le nombre de possibilités de faire l'appoint.
J'appelle "non optimisé" le fait que le monnayeur ne doit pas calculer
la meilleure façon de rendre l'argent (avec le moins de pièces
possibles), mais qu'il doit nous donner toutes les possibilités. Et
c'est bien là que je bloque.

J'ai tenté de découvrir une formule générale de récurrence mais je ne
pense pas qu'il faille passer par là : en effet c'est un exercice sur
la récursivité, qui a pour suite le même monnayeur mais cette fois avec
un nombre limité pour chaque pièce.


Voilà, je comprends bien comme "optimiser" la machine pour qu'elle
rende le moins de pièces possibles, mais je ne sais pas comment faire
pour le reste, ça fait des heures que je suis dessus et je bloque 


Un ptit coup de pouce serait le bienvenu... merci d'avance.


Bonne soirée,

TiteFleur

cptpingu · Answer

En théorie, voici une methode:

Tu cree un algorithme qui prend en parametre un tableau (qui contient toutes les pieces existantes), la somme désiré, un talbeau qui va contenir tout les etapes de ton parcours et enfin la somme en cours.
Ensuite, par recursivité tu devrais avoir un algorithme de cette forme:

procedure algo(var const tab_element, tab_solution: array, somme_actuelle, const somme_voulue: integer);
debut
  Si somme_actuelle = somme_voulue alors
    afficher(tab_solution); // tu cree un procedure qui affiche les elements du tableau
  sinon
      si somme_actuelle < somme_voulue alors
      debut
          setlength(tab_solution, taille(tab_solution) + 1)
           pour i = 0 a taille(tab_element) -1 faire
           debut
               tab_solution[taille - 1] = tab_element[i];
               algo(tab_element, tab_solution, somme_actuelle + tab_element[i], somme_voulue)
           fin
       fin
   fin si
fin

J'espere ne pas avoir laissé d'erreur. L'algo n'est pas tres otpimisé (notemment au niveau des ressources memoires avec bcp de copie de tableau). Le principe est proche des arbre binaires. Tu generes toute les possibilité a un rang donnée, et tu descends en profondeur, tant que tu n'as pas dépassé une certaine valeur limite. Si c'est le cas rien ne sera affiché. Si la somme voulue est trouvé, ca sera affiché.

cptpingu · Answer

Petite correction:

procedure algo(var const tab_element, tab_solution: array, somme_actuelle, const somme_voulue: integer);
debut
  setlength(tab_solution, taille(tab_solution) + 1)
  tab_solution[taille - 1] = somme_actuelle;
  Si somme_actuelle = somme_voulue alors
    afficher(tab_solution); // tu cree un procedure qui affiche les elements du tableau
  sinon
      si somme_actuelle < somme_voulue alors
      debut
           pour i = 0 a taille(tab_element) -1 faire
           debut
               algo(tab_element, tab_solution, somme_actuelle + tab_element[i], somme_voulue)
           fin
       fin
   fin si
fin

Francky23012301 · Answer

Salut,

Et la bonne vieille méthode des systèmes d'équations, vous l'oubliez ?? C'est pas bien lol

cptpingu · Answer

Voila, je t'ai ecrit un code qui fonctionne. Je te déconseille d'entrer des valeusr supérieurs a 0.1? sinon tu
risques d'attendre un moment...

program monnaieur;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  TType = integer;
  TTab  = array[0..7] of TType;
  TRes  = array of TType;
var
  // J'ai multiplier tes valeurs pour éviter les problemes
  // de comparaisons de 2 flottants, et ne pas m'embêter avec
  // l'affichage
  tab : TTab = (200, 100, 50, 20, 10, 5, 2, 1);

procedure print_tab(var tab: TRes);
var
  i: integer;
  res : string;
begin
  for i := 0 to length(tab) - 1 do
    case tab[i] of
      1   : write('0.01? ');
      2   : write('0.02? ');
      5   : write('0.05? ');
      10  : write('0.10? ');
      20  : write('0.20? ');
      50  : write('0.50? ');
      100 : write('1?    ');
      200 : write('2?    ');
      else
    end;
  writeln;
end;

procedure affiche(var tab: TTab; const piece:TType; res: TRes;
  somme_actuelle: TType; const somme_voulue: TType);
var
  i: integer;
begin
  SetLength(res, length(res) + 1);
  res[length(res) - 1] := piece;
  if somme_voulue = somme_actuelle then
    print_tab(res)
  else
   if somme_actuelle < somme_voulue then
     for i := 0 to length(tab) - 1 do
       affiche(tab, tab[i], res, somme_actuelle + tab[i], somme_voulue);
end;

procedure main();
var
  res : TRes;
  somme_voulue : single;
begin
   res := nil;
   // Evitez de dépasser 0.1?
   write('Somme voulue ? ');
   readln(somme_voulue);
   affiche(tab, 0, res, 0, round(somme_voulue * 100));
end;

begin
   main();
   readln;
end.

Récursivité dans un système "monnayeur"

4 réponses

Votre réponse

Discussions similaires