Jump to content

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


Courage

Recommended Posts

  • Moderators

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

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.