Bine aţi venit pe Scientia QA!
Pentru a putea publica întrebări şi răspunsuri, trebuie să vă înregistraţi.
Atenţie! Este posibil ca e-mailul de confirmare a înregistrării să intre în Spam.
  • Inregistrare
Pune o întrebare

Newsletter


3.5k intrebari

6.7k raspunsuri

15.1k comentarii

2.2k utilizatori

1 plus 0 minusuri
578 vizualizari
Stiind ce valori au monedele care circula in prezent in Romania (1 ban, 5 bani, 10 bani, 50 de bani), sa se determine in cate feluri se poate obtine suma de 1 leu din combinatii diferite de monede, folosind oricate monede.
a intrebat Senior (6.8k puncte) in categoria Tehnologia Informatiei
0 0
Posibil să fie 158 de moduri.
0 0
Eu nu cunosc raspunsul corect, asa ca va trebui sa fiti o idee mai generoasa cu detaliile rezolvarii. Am postat intrebarea in IT pentru ca se preteaza la o asa rezolvare, asa ca si un cod de program e un posibil raspuns. De complexitate cat mai mica posibil...
0 0
Am folosit numai pixul și hîrtia. Din acest motiv nu am dat un răspuns pentru că am văzut în ce categorie ați clasat-o. Aș putea să-mi verific rapid rezultatul, eventual cu JavaScript, dar sînt destul de încrezătoare în pixul meu.
1 0
Am avut si eu, in sfarsit, putin timp la dispozitie si am reusit sa incropesc un programel. Am ajuns la acelasi rezultat ca si dvs., 158.

Eu am mers pe verificarea tuturor combinatiilor posibile, cu numarul de monede de 50 de bani variind in plaja 0 la 2, cele de 10 bani in plaja de la 0 la 10, cele de 5 bani in plaja de la 0 la 20, iar cele de 1 ban in plaja 0 la 100. Deci 4 instructiuni (for, endfor) in Octave (Matlab), cu o verificare a sumei monedelor rezultate la fiecare pas.

Ar fi interesant de gasit un algoritm mai destept, care sa necesite mai putini pasi de verificat...
0 0
Se poate face simplu și un algoritm care să testeze mai puține variante. Dar nu cred că poate ieși mai scurt și mai ușor de scris decît al dumneavoastră.

Ideea ar veni cam așa:

- Pornim cu un număr de monede de 50 de bani de la 0 la 2. Calculăm cît mai trebuie completat cu monede mai mici, dacă e cazul.
- Completăm cu monede de 10 bani, de la zero la cît încape în suma rămasă. Calculăm restul.
- Completăm cu monede de 5 bani, la fel.
- Completăm cu monede de 1 ban, la fel.
1 0

Cel mai simplu este să-i dăm computerului să adune 

1 + \sum_{k = 1}^{11}(2k-1) + \sum_{k = 1}^{6}(2k-1) 

 Execută 17 operații. Asta în caz că nu știm:

  \sum_{k = 1}^{n}(2k-1) = n^{2} 

0 0
@Gheorghita:
Eu nu am inteles. Care e ideea?

2 Raspunsuri

1 plus 0 minusuri
 
Cel mai bun raspuns
Aici e un program in C++ pe care l-am gasit pe net cu mici modificari aduse de mine ca sa ruleze.O mica observatie e evident mai optim sa consideram un vector de maxim 4 valori care sa reprezinte cantitatile de monede de tipul respectiv.Exact asta determina programul cu metoda backtracking.Datele vor fi afisate intr-un fisier  care daca nu exista in proiect este creat automat.n reprezinta numarul de tipuri de monede,s suma necesara de obtinut,t contorizeaza numarul de solutii.a[100] e declarat ca reprezentand valorile monezilor evident acel 100 e prea mare .

#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=4;s=100;t=0;
a[1]=1;a[2]=5;a[3]=10;a[4]=50;
    back(1,0);
    fout.close();
    return 0;
}

As vrea sa explic programul ,eu personal am incercat sa fac dar m-am incurcat rau in timp ce acest program este foarte bine conturat si comprimat.void afis() evident nu are rost decat sa scrie solutie cand apare.Tehnica de bactracking este bazata pe incercari succesive .Functia back care are 2 parametri este apelata initial cu valorile 1 si 0  din programul principal.Deoarece functia back apare in propriul program ca reapelare acest gen de reapelare se numeste recursivitate si in caz ca nu isi poate lua valoare se intoarce automat la ultima valoare care exista in memoria unde are  date inregistrate(practic citeste inlantuit ) ,deci ea se opreste doar atunci cand numai are valoare pe care sa o modifice in ultima memorie si se intoarce in programul principal dand return 0 ,ceea ce reprezinta terminarea programului.Acest lucru se intampla cand prima valoare a ajuns la 100 si practic nu a mai avut alte valori inregistrate in memorie ca sa se intoarca,valorile nule fiind automat deservite .In c++ daca nu are atribuita valoare ea automat primeste valoarea 0 si e citita ca 0.
a raspuns Experimentat (2.3k puncte)
selectat de
0 0
Asta e partial un rezultat scris in fisier:

75*1 3*5 1*10 0*50
solutia numarul148
75*1 5*5 0*10 0*50
solutia numarul149
80*1 0*5 2*10 0*50
solutia numarul150
80*1 2*5 1*10 0*50
solutia numarul151
80*1 4*5 0*10 0*50
solutia numarul152
85*1 1*5 1*10 0*50
solutia numarul153
85*1 3*5 0*10 0*50
solutia numarul154
90*1 0*5 1*10 0*50
solutia numarul155
90*1 2*5 0*10 0*50
solutia numarul156
95*1 1*5 0*10 0*50
solutia numarul157
100*1 0*5 0*10 0*50
solutia numarul158
0 0
Multumesc mult pentru raspunsuri, zec. Am fost foarte aglomerat in ultimele zile, asa ca raspund cu mare intarziere. Deocamdata de pe tableta. Maine seara sper sa am timp sa incerc si eu programul pe un laptop si o sa va intreb mai multe, daca nu inteleg, atunci.

Multumesc inca o data.
0 0
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.
0 0
Hopa că s-au schimbat datele de intrare. Doamna Gheorghița se întreabă dacă se poate rezolva matematic și această nouă formă a problemei. Mîța mea crede că da. După un whiskey și vreo două țigări sînt de acord cu ea. Eu am opinia că o problemă care presupune implicarea computerului mai întîi se analizează matematic, se descoperă un artificiu.  Pentru zec, toată stima pentru efortul depus. Cele spuse de mine despre backtracking rămîn valabile. S-a nimerit ca în acest caz să nu fie mare diferență. Și ce este proiectul Euler?
0 0
Problema e ca pe dvs. v-am intrebat de unde ati scos formulele alea scrise frumos la un raspuns anterior, pentru ca nu am inteles ideea, si nu mi-ati raspuns. Sa inteleg ca folositi, dvs. si pisica dvs. (cu prietenie intreb), tot ceva de genul acela? Si, daca da, imi explicati si mie cum ajungeti la respectivele formule?

Project Euler e un site pe care l-am descoperit acum vreo 3 saptamani si care contine o multime de probleme de matematica-informatica, a caror rezolvare cu algoritmi de genul fortei brute nu e suficienta pentru a se ajunge la un timp de rulare rezonabil pe computer. De unde si nevoia de algoritmi isteti. Cautati project Euler pe Google...
0 0

Că tot n-am ce face și mai ales pentru că m-a scos din sărite o problemă pe care am pus-o și nu sînt capabilă să o rezolv, vă declarun număr natural n se poate descompune în n +1 moduri sub forma unei sumei de două numere naturale, incluzîndu-l și pe 0. Așa am reușit noi să găsim 158. Nu este mare lucru, mă minunez de ce v-ați mirat. Nu caut nimic, m-am lămurit cu Project Euler.

0 0
Foarte zgarcita sunteti cu explicatiile!

Sper ca va referiti la problema cu hexagoane, patrate si pentagoane. Ma bucur sa aud ca nu ati renuntat! :)
1 0

Măi să fie:

Notez cu a, b, c, d numărul de monede dn fiecare categorie, în ordinea menționării lor în enunț.
a + 5b +10c + 50d = 100. Dacă d = 2 nu mai am ce calcula și ajung la :
1. a + 5b +10c = 100 sau
2. a + 5b +10c = 50
a trebuie să fie multiplu de 5 => a = 5k.

1. a + 5b +10c = 100 => k + b + 2c = 20 =>( k + b) = 20 - 2c. Pentru că țineți minte ce am spus în comentariul anterior => (k + b) se poate descompune într-un număr de moduri egal cu suma 1 + 3 +..... 19 + 21 = 121. La fel și pentru articolul nr. 2. Sper că nu me-am făcut de rîs cu aceste explicații, evidente poate pentru unii.

Am pus recent o întrebare de geometrie - nu pot să cred că nu-i dau de capăt. La ea mă refeream.

HPP - stă și așteaptă o soluție. Unii membri ai acestui site au așteptat să vină echinocțiul de primăvară ca să dea un răspuns.

0 0
Multumesc! In sfarsit, lumina! :)
Eu cu siguranta nu ma numaram printre cei multi pentru care explicatiile dvs. anterioare erau evidente...
0 0

Nu erau evidente pentru că interesul dvs. era deviat spre fapte mai importante.

Așa blînd, cum ar fi versurile și muzica trupei Goombay Dance Band, vă întreb dacă problemele interesante pe care le propuneți au și soluțiile oferite, și dacă nu ,încercați să le rezolvați mai întîi?

0 0
La intrebarile de matematica ori, ca aici, informatica, de cele mai multe ori gasesc problemele pe net. Deci e clar ca sunt usor de gasit si solutii. Doar ca ma intereseaza sa vad la ce solutii ajungeti dvs., colegii de site, si de aceea uneori modific intrucatva enuntul. Rareori se intampla sa am si solutii proprii la acest gen de probleme. Cateodata, cred ca ati remarcat, sunt intrebari din alte domenii, generate de mici curiozitati de-ale mele. De ce ma intrebati?
0 0

V-ați fofilat de la un răspuns concret. Amiguitate specifică unor categorii de persoane: inteligente, etc....

De ce să nu vă întreb? Am această libertate pe acest site, atîta timp cît nu mut calul de șah într-un mod nepermis.

Mi se pare că uneori știți soluțiile la unele întrebări proprii, fapt remarcabil de altfel,  dar  evitați să arătați acest aspect.

Între timp, i-am dat de capăt. Superbă problemă.

0 0
@Gheorghita:
Ne puteti arata o rezolvare similara si pentru varianta reformulata a problemei, cu cele 8 tipuri de monede si suma 200?
0 plusuri 0 minusuri
o idee corecta de algoritm e bazat pe  algoritmul de backtracking.

Backtrackingul functioneaza ca o stiva adica in cazul nostru vom avea de parcurs urmatoarele:

-initializare.Acest pas atribuie in general ultimei valori din lista o valoare mai mare decat ceea precedenta .La inceput cand stiva e goala practic atribuie primei valori valoarea nula,dupa care se va face initializare doar dupa o solutie valida

-atribuire.Dupa initializare atribuim valoare incrementata  valorile fiind tipurile de monede si facem verificarea valori.

-verificarea.Se verifica daca suma e mai mica decat 100 in caz acesta se face backtracking pe nivelul urmator adica adaugam un  nou element in stiva.In cazul in care este egal cu 100 avem solutie si in caz de solutie afisam si contorizam solutii.In caz mai mare decat 100 avem depasire si eliminam ultimul element din lista practic facem backtracking inapoi.

-daca avem solutie se trece la o solutie noua se face backtracking inapoi cu initilizare noua programul se opreste cand numai putem initializa cu o alta valoare adica am ajuns la monedele de 50.

-
a raspuns Experimentat (2.3k puncte)
0 0
Poti scrie un mic algoritm, un pseudocod ori chiar un programel intr-un limbaj de programare des utilizat? Nu prea reusesc sa urmaresc ideea de implementare pe explicatiile scrise...
0 0
Backtracking, în acest caz,  este tot una cu patru for-uri imbricate și o instrucțiune de test. De obicei, acest algoritm se aplică la probleme unde se merge pe dibuite, cum ar fi ieșirea dintr-un labirint sau  săritura calului de șah.

...