Active Members dancezar Posted November 6, 2013 Active Members Report Share Posted November 6, 2013 (edited) Ideia mi-a venit de la alin acea problema de ieri.Am gasit o problema pe net care mi se pare interesanta.Enunt:Se dau N tipuri de bancnote de valori b1,b2,b3,...bn in ordine aleatorie.Din fiecare tip se dispune un numar nelimitat de bancnote,iar bancnota b1 are mereu valoare 1.Se cere:Fiind data S(o suma de bani) se cere ca aceasta suma sa fie platita cu un numar minim de bancnote.Exemplu:pentru n=3 , bancontele de b1=1 b2=10 , b3=5 si S=67 lei ,trebuie sa afiseze :Bancnota de 10 lei X 6Bancnota de 5 lei X 1Bancnota de 1 leu X 2Ca sa nu zica nimeni ca nu am rezolvare:http://s23.postimg.org/x1g1hwux6/cpp.jpgRezolvarile trebuie scrise in C++(sau C) sa fie complete si sa rezolve problema data.Rezolvarea o trimiteti pe PM.La sfarsit am sa postez rezolvarea mea si a celorlanti ca sa le comparam.Primi 4 primesc + REP Solvers:-H3xoR-dooma - new_luca-MARIUSCS -manxten-skull Edited November 6, 2013 by danyweb09 Quote Link to comment Share on other sites More sharing options...
H3xoR Posted November 6, 2013 Report Share Posted November 6, 2013 Ai PM.Mul?umesc! 1 Quote Link to comment Share on other sites More sharing options...
dooma Posted November 6, 2013 Report Share Posted November 6, 2013 Mersi de challenge! 1 Quote Link to comment Share on other sites More sharing options...
new_luca Posted November 6, 2013 Report Share Posted November 6, 2013 Am incercat si eu o rezolvare naiva. 1 Quote Link to comment Share on other sites More sharing options...
Active Members dancezar Posted November 6, 2013 Author Active Members Report Share Posted November 6, 2013 Felicitari tuturor pentru challenge am mai pus 2 locuri in plus.Dupa ce vor fi ocupate voi inchide challenge-ul Quote Link to comment Share on other sites More sharing options...
MARIUSCS Posted November 6, 2013 Report Share Posted November 6, 2013 Merci de challenge, ai pmParerea mea e ca ar trebui sa se posteze mai des astfel de probleme pentru incepatori si nu numai...nu trebuie sa se ofere un premiu, ar fi mai interesat daca nu ar fi o limita de persoane care pot trimite pm.Pur si simplu daca algoritmul e bun apari in lista din primul post...pe mine sincer chestia asta m-a motivat sa incerc sa rezolv problema, daca mi-o lua alt cineva inainte nu imi mai bateam capul. 1 Quote Link to comment Share on other sites More sharing options...
Active Members dancezar Posted November 6, 2013 Author Active Members Report Share Posted November 6, 2013 Merci de challenge, ai pmParerea mea e ca ar trebui sa se posteze mai des astfel de probleme pentru incepatori si nu numai...nu trebuie sa se ofere un premiu, ar fi mai interesat daca nu ar fi o limita de persoane care pot trimite pm.Pur si simplu daca algoritmul e bun apari in lista din primul post...pe mine sincer chestia asta m-a motivat sa incerc sa rezolv problema, daca mi-o lua alt cineva inainte nu imi mai bateam capul.Pai daca e o limita de persoane e mai motivant pentru mine cel putin.Mai sunt 2 locuri apropo:D Quote Link to comment Share on other sites More sharing options...
bcman Posted November 6, 2013 Report Share Posted November 6, 2013 @danywebFa, te rog, un test (pe programele celor ce participa) cu urmatoarele date de intrare:n = 3b1 = 1b2 = 7b3 = 10s = 14Solutia corecta ar fi ca bacnota 2 trebuie folosita de 2 ori si celelalte deloc. Quote Link to comment Share on other sites More sharing options...
dooma Posted November 6, 2013 Report Share Posted November 6, 2013 @bcman - pentru datele puse de tine, trebuie programare dinamica, sau backtracking in cel mai rau caz. O sa retrimit solutia cand o sa am timp. Quote Link to comment Share on other sites More sharing options...
H3xoR Posted November 6, 2013 Report Share Posted November 6, 2013 (edited) @bcman - pentru datele puse de tine, trebuie programare dinamica, sau backtracking in cel mai rau caz. O sa retrimit solutia cand o sa am timp.//scuze Edited November 6, 2013 by H3xoR Quote Link to comment Share on other sites More sharing options...
Active Members dancezar Posted November 6, 2013 Author Active Members Report Share Posted November 6, 2013 (edited) am modificato si pe a mea:))Da solutia optima era cu backtracking acuma am primit de la manxten te trec acuma pe lista.Multumesc bcman pentru observatie.H3xoR shhhh //am sa verific si la ceilaltiUn loooc Edited November 6, 2013 by danyweb09 Quote Link to comment Share on other sites More sharing options...
mirrorer Posted November 6, 2013 Report Share Posted November 6, 2013 Am sa postez si eu o problema ceva mai dificila sunt curios cine o rezolva primul asa ca fiti pe faza 1 Quote Link to comment Share on other sites More sharing options...
skull Posted November 6, 2013 Report Share Posted November 6, 2013 Solutia optima e cu programare dinamica. Backtracking ai folosi daca ti-ar cere sa arati toate modalitatiile in care se poate plati suma cu bancnotele respective. 1 Quote Link to comment Share on other sites More sharing options...
MARIUSCS Posted November 6, 2013 Report Share Posted November 6, 2013 Imi explica si mie cineva va rog ce inseamna backtracking in contextul asta? Quote Link to comment Share on other sites More sharing options...
Active Members dancezar Posted November 6, 2013 Author Active Members Report Share Posted November 6, 2013 (edited) Solutia optima e cu programare dinamica. Backtracking ai folosi daca ti-ar cere sa arati toate modalitatiile in care se poate plati suma cu bancnotele respective.E adevarat ce spui dar cunostintele mele se duc pana la backtracking atat am studiat pana acum.Oricum nu e nevoie de nici o programare dinamicaBun am 2 solveri mirrorer si skull cine revizuieste primul codul castiga locul si rp:D//am dat la amandoiChallenge inchisFelicitari tuturor solverilor-H3xoR-dooma-new_luca-MARIUSCS-manxten-skull-mirrorerRezolvarea mea e cam rudimentara pe langa a colegilor:))http://pastebin.com/TLPNUDnT(varianta completa cred:)) )Haxor :http://pastebin.com/FJGDDQbK (Varianta completa)dooma :http://pastebin.com/UKmbF3ZDnew_luca :http://pastebin.com/rDsgx3NtMariuscs :http://pastebin.com/dnjx1bHv (Varianta completa)manxten :http://pastebin.com/W8NLk03b (Toate solutiile)skull :http://pastebin.com/KYS4iH3i (Varianta completa)mirrorer :http://ideone.com/xhfib7sper sa nu fi uitat pe nimeni daca am uitat pe cineva fluierati oleca si gataDesigur puteti veni cu variantele revizuite.Am postat rezolvarile ca sa invatam uni de la alti.Ne vedem la urmatorul challenge stima Edited November 6, 2013 by danyweb09 Quote Link to comment Share on other sites More sharing options...
skull Posted November 6, 2013 Report Share Posted November 6, 2013 (edited) Nu m-am uitat pe toate solutiile, doar pe prima, care e si gresita.Testul gresit:n = 3bancnota 1 = 1bancnota 2 = 7bancnota 3 = 10s = 24Bancnota 10 de 2 ori.Bancnota 1 de 4 ori.Ar trebui sa arate asa:n = 3b1 = 1b1 = 7b1 = 10s = 24Numarul minim de bancnote 3bancnota de 7 de 2 oribancnota de 10 de 1 oriCum am mai zis, rezolvarea are nevoie ori de programare dinamica(solutia optima) ori de backtracking(solutie care ruleaza sute de ani pentru valori mari ale lui N).PS. Pentru challenge-uri cu teste adevarate: http://www.infoarena.ro/ Edited November 6, 2013 by skull Quote Link to comment Share on other sites More sharing options...