Jump to content
dancezar

Problema C++

Recommended Posts

  • Active Members

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 6

Bancnota de 5 lei X 1

Bancnota de 1 leu X 2

Ca sa nu zica nimeni ca nu am rezolvare:

cpp.jpg

http://s23.postimg.org/x1g1hwux6/cpp.jpg

Rezolvarile 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 by danyweb09
Link to comment
Share on other sites

Merci de challenge, ai pm

Parerea 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.

  • Upvote 1
Link to comment
Share on other sites

  • Active Members
Merci de challenge, ai pm

Parerea 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

Link to comment
Share on other sites

  • Active Members
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 dinamica

Bun am 2 solveri mirrorer si skull cine revizuieste primul codul castiga locul si rp:D

//am dat la amandoi

Challenge inchis

Felicitari tuturor solverilor

-H3xoR

-dooma

-new_luca

-MARIUSCS

-manxten

-skull

-mirrorer

Rezolvarea 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/UKmbF3ZD

new_luca :http://pastebin.com/rDsgx3Nt

Mariuscs :http://pastebin.com/dnjx1bHv (Varianta completa)

manxten :http://pastebin.com/W8NLk03b (Toate solutiile)

skull :http://pastebin.com/KYS4iH3i (Varianta completa)

mirrorer :http://ideone.com/xhfib7

sper sa nu fi uitat pe nimeni daca am uitat pe cineva fluierati oleca si gata

Desigur puteti veni cu variantele revizuite.

Am postat rezolvarile ca sa invatam uni de la alti.

Ne vedem la urmatorul challenge stima

Edited by danyweb09
Link to comment
Share on other sites

Nu m-am uitat pe toate solutiile, doar pe prima, care e si gresita.

Testul gresit:


n = 3
bancnota 1 = 1
bancnota 2 = 7
bancnota 3 = 10
s = 24
Bancnota 10 de 2 ori.
Bancnota 1 de 4 ori.

Ar trebui sa arate asa:


n = 3
b1 = 1
b1 = 7
b1 = 10
s = 24
Numarul minim de bancnote 3
bancnota de 7 de 2 ori
bancnota de 10 de 1 ori

Cum 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 by skull
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.



×
×
  • Create New...