Задание 3. Время получать сдачу - 1

В наших широтах мы такого не встречали, а в США, похоже, распространён игрушечный кассовый аппарат, изображенный на фото выше. Цилиндры предназначены для хранения монет разного диаметра (и номиналов). Выдает их пружинный механизм, а сам агрегат можно закрепить на поясе ребёнка-кассира. 

Однако что будет, если кто-то рассчитается с кассиром крупной купюрой? Представьте, сколько мороки будет с тем, чтобы посчитать монетки на сдачу. Для минимизации количества выдаваемых монет можно использовать так называемые «жадные» алгоритмы. Они, согласно определению Национального Института Стандартов и Технологии (NIST) всегда находят оптимальное решение на каждом шаге решения задачи, допуская, что конечное решение (полученное из совокупности таких шагов) также будет оптимальным. 

Что это значит? Представим, что кассир должен покупателю сдачу в 41 цент, а у него на поясе есть цилиндры с монетками для сдачи номиналом в 25, 10, 5 и 1 цент. Руководствующийся «жадным» алгоритмом кассир сразу же захочет выдать максимум, на первом же шаге. На этом шаге оптимальным или наилучшим решением будет выдать 25 пенсов. 41-25 = 16. Осталось выдать 16 пенсов. Очевидно, 25 пенсов слишком много, значит, остается 10. 16-10 = 6. Теперь выдаем по тому же принципу 5 пенсов, и затем — 1. Таким образом, покупатель получит всего четыре монеты номиналом 25, 10, 5 и 1 пенс. 

Оказывается, «жадная» пошаговая инструкция выдачи денег оптимальна не только для этого случая, но также для номиналов валюты США (и Евросоюза тоже). То есть, если у кассира достаточно монет любого номинала, алгоритм будет работать лучшим образом, то есть, выдаст минимальное количество монет из всех возможных случаев. 

Итак, какое минимальное количество монеток нам нужно, чтобы дать сдачу? Это и есть наша третья задачка.

Создайте файл greedy.c в своей директории ~/workspace/pset1

Дано: монетки номиналом 25, 10, 5, 1 цент 

Программа должна:

  1. Спросить пользователя, сколько сдачи нужно выдать.
  2. Посчитать минимальное количество монет, с помощью которых можно это сделать

Примечание: для ввода будем пользоваться функцией GetFloat из библиотеки CS50 и printf из стандартной библиотеки ввода/вывода для вывода. Кроме того, программа должна проверять корректность ввода. 

Мы попросили вас использовать GetFloat, чтобы пользователь мог вводить значение в долларах и центах через точку. Например, если мы должны $9.75, пользователь должен ввести 9.75, но не $9.75 или 975. 

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

Внимание! Остерегайтесь неточностей, свойственных числам с плавающей точкой. Например, 0.01 не может быть представлено непосредственно как float. Попробуйте использовать форматированный вывод, например, с 50 знаками после запятой, используя указанный ниже код: 

float f = 0.01;
printf("%.50f\n", f);

Кстати, перед тем, как что-либо считать, будет логично перевести всю сумму в центы, (и заодно преобразовать её из float в int), что поможет избежать массы ошибок и сложностей. 

Чтобы наш автоматический анализатор кода мог правильно проверить вашу задачу, убедитесь, что последняя строка вывода вашей программы не содержит никакой другой информации, кроме минимального количества монеток: целое число с символом \n после него (те, кто учится на JavaRush, прекрасно знают, о чём мы здесь говорим =)). Ниже — пример, как должен выглядеть результат работы вашей программы. 

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
0.41
4

Учитывая особенность чисел с плавающей точкой, можно игнорировать нуль и вводить такое число в форме .41.

Конечно, пользователи, которые захотят проверить программу на возможность ввода некорректных данных по полной, должны увидеть что-то вроде:

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
-0.41
How much change is owed?
-0.41
How much change is owed?
foo
Retry: 0.41
4

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

Если во время тестирования приложения вы поймете, что цикл не останавливается, вы можете прервать выполнение программы комбинацией ctrl-c (иногда — многократной).

Как компилировать и выполнять программу вы уже знаете. 

Если вы хотите проверить правильность работы вашей программы, с помощью утилиты check50, в терминале введите следующую строку:

check50 2015.fall.pset1.greedy greedy.c

А если вам захочется поиграть с этой программой, выполненной ассистентами курса, пропишите следующую команду:

~cs50/pset1/greedy