Modalitati De A Platii Suma De 5 Lei Cu Bancnote 1, 2 Sau 3 Lei

[Courage]

O vânzatoare trebuie sa dea un rest de 5 lei unui client. Pentru simplitate se considera ca poate da acest rest utilizând oricâte bancnote de 1, 2 sau 3 lei. Sa se genereze toate modalitatile de a platii suma de 5 lei cu bancnote 1, 2 sau 3 lei .

Indicatii de rezolvare:

Problemele de mai sus se vor rezolva utilizând tehnica backtracking, varianta iterativa. Modelul de baza pentru aceasta tehnica este reprezentat de functia de mai jos.

void back()

 {

 int areSuccesor;

 int niv;

 niv=1;

 init(niv);

 while(niv>0)

 {

 do {

 areSuccesor=succesor(niv);

 }while(areSuccesor!=0 && valid(niv)==0);

 if (areSuccesor!=0){

 if (solutie(niv))

 afiseaza(niv);

 else{

 niv=niv+1;

 init(niv);

 }

 }

 else

 niv=niv-1;

 }

 }

 [/C]

 Pentru rezolvarea unei probleme se utilizeaza o stiva în care vor fi generate solutiile.

 Stiva a fost declarata ca un vector de întregi si notata cu sol. Pe fiecare nivel (pozitie) în stiva se afla un element din multimea solutiilor.

 De asemenea au fost utilizate functiile, de mai jos a caror implementare depinde de problema de rezolvat.

 • functia init(niv) - la urcarea în stiva, pe nivelul la care s-a ajuns se pune o valoare care nu se afla în multimea considerata, dar de la care, la pasul urmator, se ajunge la primul element din acea multime (de regula valorile 0 sau -1);

 • functia succesor(niv) - pe un anumit nivel, gaseste elementului urmator celui considerat, element netestat; functia returneaza 1, daca exista succesor acesta fiind pus în stiva si 0 în caz contrar;

 • functia valid(niv) - verifica daca elementul ales îndeplineste sau nu conditiile de continuitate ale problemei si returneaza 1 daca le îndeplineste si 0 în caz contrar;

 • functia solutie(niv) - testeaza daca s-a ajuns sau nu la solutia finala, returnând 1, respectiv 0;

 • functia afiseaza (niv) - tipareste solutia, de la 1 si pâna la nivel.


 Rezolvare:

 [C]#include <stdio.h>

 #include <stdlib.h>

 #include <conio.h>



 int i,k,n,v[100],sol=0,banc[4]={0,5,7,10};

 char isS,isV=0;


 void Init(int k){


     v[k]=0;


 }


 int Succesor(int k){


     if (v[k]<n){

         v[k]++;

         return 1;

     }

     else

         return 0;


 }


 int Valid(int k){

     int s=0;

     for (i=1;i<=k;i++)

         s=s+banc[v[i]];    

     if (s>50) return 0;


     return 1;

 }


 int Solution(int k){

     int s=0;

     for (i=0;i<=k;i++)

         s=s+banc[v[i]];

     if (s==50) return 1;

     return 0;


 }


 void Print(int k){


     printf("%d : ",++sol);


     for (i=1;i<=k;i++)

         printf("%d ",banc[v[i]]);


      printf("\n");

 }


 void Back(){


     k=1;

     Init(k);


     while (k>0){

         isS=0;isV=0;

             do{

                 isS=Succesor(k); // cauta succesor

                 if (isS) isV=Valid(k);

             } while (isS && !isV);


         if (isS && isV) //este succesor si este valid

             if (Solution(k))

                 Print(k);

             else {

                 k++;

                 Init(k);

             }

         else  //nu am succesor -> cobor o pozitie in stiva

             k--;

     }

 }


 int main()

 {

     n=3;

     Back();

     getch();

     return 0;

 }

sursa: tutorialehd.info