Am reusit sa studiez si eu cu atentie codul sursa. Cred ca imi e destul de clar algoritmul implementat.
Nu stiu daca sa fiu de acord cu doamna Gheorghita cand spune ca, in acest caz, e cam totuna cu 4 for-uri imbricate cu o instructiune de test. Mie imi pare ca varianta cu 4 for-uri imbricate propusa de mine si testarea sumei pentru toate combinatiile de monede este, doar in acest caz, mai rapida.
Pentru o comparatie serioasa intre cele doua variante, pentru a vedea care dintre algoritmi e mai performant, am schimbat problema si am introdus in joc mai multe tipuri de monede, crescand si suma la care trebuie ajuns.
Eu am facut asta pentru varianta mea, cu for-urile imbricate, iar cand acestea sunt, de pilda, 8 (monede de 1,2,5,10,20,50,100,200), cu suma totala 200, am stat mult si bine si am asteptat pentru raspunsul final.
Al dvs.program, adaptat de mine, a rulat in acest caz in 0.19 secunde si a afisat numarul corect de solutii. L-am testat pe acest site: codechef.com/ide
Am folosit urmatorul cod sursa:
#include <fstream>
using namespace std;
ofstream fout("date.out");
int x[100], a[100], n,s,t;
void afis()
{
for(int i=1;i<=n;i++)
fout<<x[i]<<"*"<<a[i]<<" ";
fout<<endl;
fout<<"solutia numarul"<<t;
fout<<endl;
}
void back(int k,int sp)
{
int i;
for(i=0;i<=(s-sp)/a[k];i++)
{
x[k]=i;
sp=sp+x[k]*a[k];
if(sp<=s && k<=n) if(k==n && sp==s){t++; afis();}
else if(k<n) back(k+1,sp);
sp=sp-x[k]*a[k];
}
}
int main()
{n=8;s=200;t=0;
a[1]=1;a[2]=2;a[3]=5;a[4]=10;a[5]=20;a[6]=50;a[7]=100;a[8]=200;
back(1,0);
fout.close();
printf("%d",t);
return 0;
}
A returnat t=73682 solutii...
Pentru cei interesati, intrebarea mea a fost bazata pe problema nr. 31 din Project Euler.
