Problema C++

[dancezar]

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:

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 November 6, 2013 by danyweb09

[H3xoR]

Ai PM.

Mul?umesc!

[dooma]

Mersi de challenge!

[new_luca]

Am incercat si eu o rezolvare naiva.

[dancezar]

Felicitari tuturor pentru challenge am mai pus 2 locuri in plus.Dupa ce vor fi ocupate voi inchide challenge-ul

[MARIUSCS]

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.

[dancezar]

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

[bcman]

@danyweb

Fa, te rog, un test (pe programele celor ce participa) cu urmatoarele date de intrare:

n = 3

b1 = 1

b2 = 7

b3 = 10

s = 14

Solutia corecta ar fi ca bacnota 2 trebuie folosita de 2 ori si celelalte deloc.

[dooma]

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

[H3xoR]

@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

[dancezar]

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 ceilalti

Un loooc

Edited November 6, 2013 by danyweb09

[mirrorer]

Am sa postez si eu o problema ceva mai dificila sunt curios cine o rezolva primul asa ca fiti pe faza

[skull]

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.

[MARIUSCS]

Imi explica si mie cineva va rog ce inseamna backtracking in contextul asta?

[dancezar]

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 November 6, 2013 by danyweb09

[skull]

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 November 6, 2013 by skull