«phpClub» — архив тем ("тредов"), посвящённых изучению PHP и веб-технологий.
Аноним 2018/11/22 14:24:13  №1299665 1
Ответы: >>1308667
Аноним 2018/12/09 15:32:42  №1308667 2
Из предыдущего треда:

>>1299665

> https://repl.it/@underbottom/ATM - банкомат.

> $count100 = 0;
> $count200 = 0;
> $count500 = 0;
Если ты начинаешь создавать переменные с цифрами на конце, скорее всего тебе нужен массив. Не $count100, а $count[100]. У тебя, чтобы добавить новый номинал, надо переделывать весь код.

В общем, там сейчас один и тот же код скопирован 6 раз, надо использовать массив и цикл вместо копипасты.

В Википедии написано, что жадный алгоритм работает только для "канонических" систем монет или купюр: https://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC#Размен_монет

> https://repl.it/@underbottom/smart-ATM -головоломка.

Да, тут идея относительно верная - перебирать все сочетания количеств купюр. Но проблема в том, что время выполнения программы быстро растет. Допустим, у тебя по 10 штук каждой купюры = это 10^6 = 1 млн. итераций (терпимо). Но если купюр будет по 100 штук, то это уже 100^6 = 10^12 = триллион итераций. Слишком долго будет работать.

Потому надо внедрять оптимизации перебора, вроде таких:

- если мы хотим выдать 6600, то не имеет смысл проверять варианты, где 2 и более купюры по 5000. Имеет смысл проверять варианты только 0x5000 и 1x5000
- если мы хотим выдать 500500, то сначала стоит попробовать вариант 100 x 5000, так как он ближе всего к цели, и только потом 99x5000, 98 x 5000 и тд.
- если мы хотим выдать 500500, и у нас сумма купюр номиналом < 5000 равна 6000, то не имеет смысла проверять варианты вроде 96 x 5000, 95 x 5000 итд., так как при их использовании нам не хватит мелких купюр.

Если ты будешь внедрять оптимизации, я тебе советую добавить в программу счетчик итераций, чтобы видеть эффект от них.

Я должен предупредить, что задача о размене - это разновидность задачи о ранце и при желании можно подобрать такие начальные условия, что даже с оптимизациями потребуется полный перебор вариантов. Но в реальных условиях (когда номиналы купюр круглые и купюр не более нескольких сотен), это должно работать. Если тебе интересно проверить это, можно подавать в цикле на вход твоей программе разные суммы и смотреть, сколько итераций потребуется на каждую.

Ну и у тебя скопировано 6 циклов, было бы выгоднее заменить их на рекурсивный вызов функции с одним циклом. Почитай про рекурсию и попробуй заменить циклы на нее. А то если мы хотим сделать 4 или 7 номиналов, надо код переделывать. Хватит копипастить.

Похожая задача о сдаче: https://habr.com/post/109384/

Почитать про задачи о размене: https://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D1.80.D0.B0.D0.B7.D0.BC.D0.B5.D0.BD.D0.B5

В этих задачах число купюр неограниченно. Потому тебе можно изучить алгоритм и доработать его для ограниченного числа купюр.