Last active
October 21, 2018 15:47
-
-
Save funvit/ec99ba79be4f73166e0995475b57e697 to your computer and use it in GitHub Desktop.
Тренировка ума. Решение задачи банкомата (выдача суммы купюрами наибольшего номинала). Вариант без лимитов.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # !/bin/python3.6 | |
| # Алгоритм банкомата, используя левостороннее дерево. | |
| # Вариант без лимитов банкнот! | |
| class Node(list): | |
| # Левостороннее дерево | |
| _value = None | |
| _childrens = None | |
| _parent = None | |
| __childrens_next_idx = -1 | |
| def __fill_recursive(self, values): | |
| # recursion | |
| if not values: | |
| return None | |
| self._value = values[0] | |
| for i in range(len(values)): | |
| if i < len(values) - 1: | |
| # we need to go deeper :-) | |
| _c = Node(None) | |
| _c._parent = self | |
| _c.__fill_recursive(values[i + 1:]) | |
| self._childrens.append(_c) | |
| def __init__(self, values): | |
| self._childrens = list() | |
| if values: | |
| self.__fill_recursive( | |
| sorted(values, reverse=True) | |
| ) | |
| def next(self): | |
| if not self._childrens: | |
| raise StopIteration() | |
| elif self.__childrens_next_idx < len(self._childrens) - 1: | |
| self.__childrens_next_idx += 1 | |
| return self._childrens[self.__childrens_next_idx] | |
| else: | |
| raise StopIteration() | |
| @property | |
| def parent(self): | |
| return self._parent | |
| @property | |
| def value(self): | |
| return self._value | |
| def __str__(self): | |
| return str(self._value) | |
| def cash_dispenser(banknote_types, amount_to_split): | |
| assert isinstance(banknote_types, (list, tuple)) | |
| assert isinstance(amount_to_split, int) | |
| # нужно создать несколько наборов деревьев | |
| ngs = list() | |
| for i in range(len(banknote_types)): | |
| ngs.append( | |
| Node(banknote_types[i:]) | |
| ) | |
| result = { | |
| 'banknotes': dict(), | |
| 'cant_split': None, | |
| } | |
| for ng in ngs: | |
| ne = ng # root | |
| remain = int(amount_to_split) | |
| while True: | |
| if remain >= ne.value: | |
| cnt = remain // ne.value | |
| remain = remain - cnt * ne.value | |
| result['banknotes'][ne.value] = cnt | |
| if remain == 0: | |
| break | |
| # next | |
| try: | |
| ne = ne.next() | |
| except StopIteration: | |
| # no next - reset result | |
| result['banknotes'] = {} | |
| remain = amount_to_split | |
| # switch parent | |
| if ne.parent is not None: | |
| ne = ne.parent | |
| else: | |
| ne = None | |
| if ne is None: | |
| break | |
| result['cant_split'] = remain > 0 or not result['banknotes'] | |
| if not result['cant_split']: | |
| break | |
| return result | |
| import unittest | |
| class CashDispenserTest(unittest.TestCase): | |
| banknote_types = (5000, 1000, 500, 100, 50) | |
| def test_1250(self): | |
| result = cash_dispenser(self.banknote_types, 1250) | |
| self.assertFalse(result['cant_split']) | |
| self.assertEqual({ | |
| 1000: 1, | |
| 100: 2, | |
| 50:1 | |
| }, result['banknotes']) | |
| def test_11150(self): | |
| result = cash_dispenser(self.banknote_types, 11150) | |
| self.assertFalse(result['cant_split']) | |
| self.assertEqual({ | |
| 5000: 2, | |
| 1000: 1, | |
| 100: 1, | |
| 50:1 | |
| }, result['banknotes']) | |
| def test_120_with_30banknote(self): | |
| result = cash_dispenser( | |
| (5000, 1000, 500, 100, 50, 30), | |
| 120) | |
| self.assertFalse(result['cant_split']) | |
| self.assertEqual({ | |
| 30:4 | |
| }, result['banknotes']) | |
| def test_260_with_30banknote(self): | |
| result = cash_dispenser( | |
| (5000, 1000, 500, 100, 50, 30), | |
| 260) | |
| self.assertFalse(result['cant_split']) | |
| self.assertEqual({ | |
| 100: 2, | |
| 30:2 | |
| }, result['banknotes']) | |
| def test_300_with_30banknote(self): | |
| result = cash_dispenser( | |
| (5000, 1000, 500, 100, 50, 30), | |
| 300) | |
| self.assertFalse(result['cant_split']) | |
| self.assertEqual({ | |
| 100: 3, | |
| }, result['banknotes']) | |
| def test_should_fail_with_135(self): | |
| result = cash_dispenser( | |
| self.banknote_types, | |
| 135) | |
| self.assertTrue(result['cant_split']) | |
| def test_60_with_banknotes_overlap(self): | |
| result = cash_dispenser( | |
| (50, 30), | |
| 60) | |
| self.assertFalse(result['cant_split']) | |
| self.assertEqual({ | |
| 30: 2, | |
| }, result['banknotes']) | |
| def test_120_with_banknotes_overlap(self): | |
| result = cash_dispenser( | |
| (50, 30), | |
| 120) | |
| self.assertFalse(result['cant_split']) | |
| self.assertEqual({ | |
| 30: 4, | |
| }, result['banknotes']) | |
| if __name__ == '__main__': | |
| import sys | |
| if len(sys.argv) > 1: | |
| print(cash_dispenser( | |
| (5000, 1000, 500, 100, 50, 30), | |
| int(sys.argv[1]) | |
| )) | |
| else: | |
| print('Run with amount to dispense') |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Забавно.
Был баг. Если доступные купюры 50 и 30, и нужно выдать 60.
Решилось через использование нескольких деревьев.