Monety raz jeszcze

0

Bankowiec napisał

Prosiłbym o pomoc w rozwiązaniu tego oto zadania.
na wejściu podane są cztery liczby, okreslające kolejno ilość monet o nominałach 2 5 7 9. Napisz funkcję. Jako argument podajemy pewną liczbe X. Zadanie funkcji to wypisanie, ile pieniędzy X da się wydać za pomocą dostepnych nominałów.
Przykład, dla 5,2,1,1 X=10
odp: 2 (5 monet po 2 i 2 monety po 5)

Temat wylądował w koszu, z uwagą że jest "problemem wydawania reszty". Uważam, że temat wylądował w koszu niesprawiedliwie.
Zmieńmy nominały na 2 3 4. Dokładniej
2 monety 4zł
4 monety 3zł
1 moneta 2zł
X=10
Jeżeli algorytm wydawania reszty zaproponuje 4+3+3, to kolejne zastosowanie tego algorytmu też da 4+3+3 i otrzymamy, że f(10)=2, 10 można wydać dwa razy
Jeżeli natomiast algorytm zaproponuje 4+4+2, to kolejnego wydania nie będzie i f(10)=1.
Problem nie sprowadza się zatem, do wielokrotnego problemu wydawania reszty.

0

nie calkiem sie zgodze.. jesli chodzi o 'nieresetowane' kombinacje, tzn mam na mysli ze dla:

2,5,7,9 =ilosci=> 2111
x=9

algo ma odpowiedzec: 2 [bo {(9),(2,7)}] //mozliwe oba NARAZ
a nie 3 [ {(9),(2,7),(2,2,5)} ] //3 dwojki! kazda opcja mozliwa, ale nie NARAZ

wiec, jesli zwracac kombinacje NARAZ, to po kazdej wybranej kombinacji IMHO wystarczy wycinac zuzyte 'monety' ze zbioru wejsciowego

hyyym.. ok, niekoniecznie to jest tak trywialne, bo np. dla:
1,2,3,4,5,6 = 1,3,1,1,0,0,
X=6 mozna wydac np jako 2+2+2 [odp:1]
ale tez jako 1+2+3, 2+4 [odp:2]
czyli algo 'std-monetowy' z wycinaniem zuzytych monet odpada - jak najpierw sprobuje 3x2 i wytnie 2jki to lepszej opcji nie zauwazy..

0

@quetzalcoatl, czy to czytałeś mojego posta ? Przecież podałem przykład, że

algo 'std-monetowy' z wycinaniem zuzytych monet odpada
.

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.