Witam,
mam problem z przełożeniem zadania na język programowania C. Na kartce wydaje się oczywiste natomiast realizacja tego zadania programem sprawia mi nie lada trudność..
Treść zadania jest następująca:
"Dowolną kwotę rozłóż na wszystkie możliwe przypadki za pomocą 10 zł, 5 zł oraz 2 zł"
Prosiłbym bardzo o wskazówki do tego zadania.
Z góry dziękuję,
Przemysław.
Spróbuj na kartce rozłożyć 10000zł na wszelkie możliwe kombinacje 2, 5 i 10 zł. Siłą rzeczy weźmiesz się za myślenie o jakimś ogólnym, szybkim rozwiązaniu ;)
Rekurencja z powrotami.
def change(left, nominals):
change_r(left, [], nominals)
def change_r(left, current, nominals):
for i, nominal in enumerate(nominals):
if left >= nominal:
change_r(left - nominal, current + [nominal], nominals[i:])
if left == 0:
print(current)
def main():
nominals = [10, 5, 2]
change(25, nominals)
main()
Lecimy po kolei po dostępnych nominałach i wybieramy największy który jest mniejszy lub równy reszcie do wydania. Odejmujemy go od reszty i powtarzamy to samo, ale dalej pracujemy tylko na nominałach mniejszych lub równych temu wybranemu (tzn jeśli np. wybraliśmy teraz 5 to w kolejnym wywołaniu bierzemy pod uwagę już tylko nominały 5 oraz 2). Do niższego wywołania przekazujemy też listę już wybranych nominałów.
Jeśli jesteśmy na dnie rekurencji i pozostało nam do wydania 0 to wypisujemy aktualny wynik.
Zadanie samo w sobie ma wadę. Powinno uwzględniać stan bilonu w kasie do wydania ;) Ale wiem ze chodzi tutaj o algorytm a nie zastosowanie.
somedev napisał(a):
Zadanie samo w sobie ma wadę. Powinno uwzględniać stan bilonu w kasie do wydania ;) Ale wiem ze chodzi tutaj o algorytm a nie zastosowanie.
Pytanie ma sens.
Dziś już trochę mniej to ważne, ale 20 lat temu, jak przelew do osoby prywatnej był ewenementem, kasjer przygotowywał listę nominałów dla całej załogi jaką zamawia z banku. Tak algorytm był bardzo ważnym elementem programów płacowych czy księgowych
Cala rodzina rozwiazan problemu nazywa sie "Programowaniem Dynamicznym". Zobacz tutaj: https://algorithms.tutorialhorizon.com/dynamic-programming-coin-change-problem/