glupiychelovek

17.04.2021 09:33

Информатика

Есть ответ 👍

Решить на языке JavaScript Програма має розраховувати найменшу кількість монет, якою можна видати решту. Номінал монет 25¢, 10¢, 5¢ та 1¢. Корисно використовувати жадібний алгоритм. Наприклад, якщо потрібно видати якомусь покупцю 41¢, найперший (тобто найкращий) крок, який можна зробити, це видати 25¢ (цей крок "найкращий", тому що він наближує нас до 0 швидше, ніж видача будь-якої іншої монетки.) Зауважте, що такий крок зменшить задачу з 41¢ до задачі 16¢, адже 41 – 25 = 16. Задача ще не вирішена, але вже менша. Очевидно, що видача наступних 25¢ буде завеликою (якщо ми вважаємо, що касир не хоче втратити гроші), далі наступний крок з видача 10¢, зменшуючи здачу до 6¢. Далі видається одна 5¢ монетка, за якою слідує фінальний 1¢, на чому задача буде вирішеною. Таким чином покупець загалом отримає по одній монеті номіналом 25¢, 10¢, 5¢ та 1¢.