1 Востаннє редагувалося frz (09.07.2020 19:14:18)

Тема: банкомат - видати потрібну суму найменшою кількістю банкнот

Всім привіт. Це моя перша програмка на Python, не судіть строго, мене тут в даному випадку більше цікавить сам алгоритм.
Ціль - вивести три числа через пробіл, кількість банкнот трьох номіналів, 100 50 і 20.

Для спрощення вхідний параметр завжди додатній і завжди потрібне число можна скласти з перелічених вище номіналів.

Моя проблема не в слабкому знанні саме цієї мови, а швидше в пошуку вірного алгоритму. Бо віднімати числа в циклі тут неефективно. Наприклад, для вхідного значення 290 все гаразд, однак для 110 в мене спершу відніметься 100 і тоді залишиться 10, для якого нема номіналу. Тут потрібно пропустити номінал 100 і брати одну банкноту 50 плюс три банкноти по 20. В кого є ідеї для алгоритму, запрошую висловлюватися.

Прихований текст
def atm(value):
    rest = value
    result = ''
    var100 = 0
    var50 = 0
    var20 = 0
    if (rest - 100 >= 0):
        while True:
            rest = rest - 100 
            if (rest >= 0):
                var100 = var100 + 1
            else: 
                rest = rest + 100
                break
    if (rest - 50 >= 0):
        while True: 
            rest = rest - 50
            if (rest >= 0):
                var50 = var50 + 1
            else: 
                rest = rest + 50
                break
    if (rest - 20 >= 0):
        while True: 
            rest = rest - 20
            if (rest >= 0):
                var20 = var20 + 1
            else: 
                rest = rest + 20
                break
    result = str(var100) + ' ' + str(var50) + ' ' + str(var20)
    return result

print (atm(290))

2

Re: банкомат - видати потрібну суму найменшою кількістю банкнот

Мабуть краще буде так:
Перевіряємо запит(сума для видачі), якщо запит більше ніж є на рахунку тоді:
Пишемо на екрані " Ідіть в баню, не достатньо коштів на рахунку";
Запит менше залишку на рахунку, тоді:
ділимо запит на найбільший номінал, це буде кількість банкнот цього номіналу;
фіксуємо кількість купюр;
Залишку від ділення немає, переходимо до функції видачі коштів;
є залишок від ділення,
ділимо на наступний номінал, той що менше попереднього;
фіксуємо кількість банкнот;
І так до найменшого номіналу, або до ділення без залишку;
Якщо після ділення на найменший номінал є залишок;
Пишемо на екрані " Ідіть в баню, не можливо видати потрібну суму" :)
Функція видачі коштів();
відраховуємо потрібну кількість номіналів згідно пофіксених лічильників купюр;
видаємо гроші;
Пишемо на екрані "Візьміть гроші, не забудьте забрати катку, приходьте ще" :)

Якось так це бачу..

3

Re: банкомат - видати потрібну суму найменшою кількістю банкнот

ділимо запит на найбільший номінал, це буде кількість банкнот цього номіналу;

У випадку вхідного параметру 110 це буде невірно... Буде 100 + 10, а номінал 10 не передбачений.

не можливо видати потрібну суму

Але в умові задачі вказано, що задану суму завжди можна видати комбінацією наявних номіналів.
У випадку суми 110 повинно бути 50 + 20 + 20 + 20.

4

Re: банкомат - видати потрібну суму найменшою кількістю банкнот

https://en.m.wikipedia.org/wiki/Change-making_problem

Виявляється, задача описана навіть у вікіпедії. Почав читати.

Подякували: Droid 771

5 Востаннє редагувалося frz (16.07.2020 10:39:18)

Re: банкомат - видати потрібну суму найменшою кількістю банкнот

Буду вдячний, якщо хтось знайде логічну помилку шляхом тестування на інших різних числах, які дадуть невірний результат.

Нагадую, результат показує мінімальну кількість банкнот у порядку 100, 50, 20, котрі потрібні для обміну на введену суму (сума вводиться завжди така, що дасть можливість обміняти на наявні номінали).

Прихований текст
def atm(amount):

      Opt = [0 for i in range(0, amount+1)]
      sets = {i:[] for i in range(amount+1)}
      banknotes = [20, 50, 100]
      n = len(banknotes)
      for i in range(1, amount+1):
            smallest = float("inf")
            for j in range(0, n):
                 if (banknotes[j] <= i):
                       smallest = min(smallest, Opt[i - banknotes[j]]) 
                       if smallest == Opt[i - banknotes[j]]:
                             sets[i] = [banknotes[j]] + sets[i-banknotes[j]]
            Opt[i] = 1 + smallest 
      banknotes = sorted(sets[amount])
      var100 = 0
      var50 = 0 
      var20 = 0
      for x in banknotes: 
          if x == 100:
              var100 = var100 + 1
          elif x == 50: 
              var50 = var50 + 1
          else: 
              var20 = var20 + 1
      result = str(var100) + ' ' + str(var50) + ' ' + str(var20)
      return result
    
print (str(110) + ': ' + atm(110))
print (str(120) + ': ' + atm(120))
print (str(40) + ': ' + atm(40))
print (str(90) + ': ' + atm(90))
print (str(190) + ': ' + atm(190))
print (str(210) + ': ' + atm(210))

110: 0 1 3
120: 1 0 1
40: 0 0 2
90: 0 1 2
190: 1 1 2
210: 1 1 3

6 Востаннє редагувалося Vo_Vik (16.07.2020 04:19:03)

Re: банкомат - видати потрібну суму найменшою кількістю банкнот

А як би ви робили без програми це? Ну словесний алгоритм.

Ось якби це робив я.

Прихований текст

Поки amount % 20 == 10
Val50++
amount -=50
Поки amount > 100
Val100++
amount -=100
Поки amount >20
  Val20++
amount -=20

7 Востаннє редагувалося frz (17.07.2020 17:30:58)

Re: банкомат - видати потрібну суму найменшою кількістю банкнот

Vo_Vik написав:

А як би ви робили без програми це? Ну словесний алгоритм.

Це динамічне програмування і я його ще не зрозумів, код не мій. Точніше, мій лише починаючи з цього рядка:

banknotes = sorted(sets[amount])

Я добре вмію ґуґлити ) Знайшов за ключовими словами "atm python" код, котрий виконує те що мені потрібно. Тільки той код виводив результат не в тому вигляді, котрий потрібно було мені, тому кінцівку трохи переробив. Я вже зробив print кожного кроку, щоб так би мовити "віддебажити", однак динамічне програмування я поки що не осилив. Якщо комусь зрозуміло, то поясніть. Та як би там не було, поки що не бачу недоліків у цьому коді.

Ось якби це робив я.

Прихований текст

Поки amount % 20 == 10
Val50++
amount -=50
Поки amount > 100
Val100++
amount -=100
Поки amount >20
  Val20++
amount -=20

Робити це в циклі неефективно.
Переконайтеся самі - спробуйте отримати такі ж результати за допомогою вашого алгоритму:

Прихований текст

110: 0 1 3
120: 1 0 1
40: 0 0 2
90: 0 1 2
190: 1 1 2
210: 1 1 3

8

Re: банкомат - видати потрібну суму найменшою кількістю банкнот

Чому не ефективно. Там взагалі можна через 3 формули це зробити.

9

Re: банкомат - видати потрібну суму найменшою кількістю банкнот

Vo_Vik написав:

Чому не ефективно. Там взагалі можна через 3 формули це зробити.

Я вище описав цю проблему з циклом:

Наприклад, для вхідного значення 290 все гаразд, однак для 110 в мене спершу відніметься 100 і тоді залишиться 10, для якого нема номіналу. Тут потрібно пропустити номінал 100 і брати одну банкноту 50 плюс три банкноти по 20.

Можливо, я не до кінця зрозумів, що саме ви описали "словесно". То розкажіть детальніше, будь ласка. Мати декілька варіантів ще краще.

Мене дещо непокоїть, що я не розумію код котрий я доопрацював і котрий працює відмінно (бо поки не знайдено недоліків), однак описати словами його алгоритм я поки що не можу... :(

10

Re: банкомат - видати потрібну суму найменшою кількістю банкнот

Гляньте уважно на мій псевдо код. Воно не те що у вас словами описано.