Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 1000001)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.
Тесты
| Сумма | 130 | 999 | 7360 | 3 | 80 | 123450 | 567 | 440 |
| Число купюр | 3 | -1 | 18 | -1 | 3 | 249 | -1 | 4 |
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <stdio.h> int Q[] = { 500, 200, 100, 50, 20, 10 }; //создание одномерного массива, в который входят все имеющиеся купюры int main() { int n, q, x; //q - вспомогательная переменная в цикле scanf("%d",&n); x=0; //количество купюр, ему по умолчанию присваивается 0 for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему { q = Q[i]; x += n / q; //считаем, сколько раз входит купюра в сумму n %= q; //сумме присваивается остаток от деления на данную купюру } if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать printf("%d",x); return 0; } |
Алгоритм
В данной задаче очень удобно применить так называемый жадный алгоритм. Он заключается в том, чтобы взять купюру наибольшего достоинства, и найти, сколько раз она входит в данную сумму. То, что мы можем выдать только с помощью этой купюры, отнять от исходной суммы. Затем повторить операцию для оставшегося количества денег и самой большой из купюр меньшего достоинства. Перебрав таким образом все купюры, мы получим наименьшее их количество для получения данной суммы, что от нас, собственно, и требуется.
Такой алгоритм подходит не для всех валютных систем, а только для канонических — таких, в которых каждая купюра большего достоинства превышает меньшую более чем в два раза. В нашем случае это условие соблюдается.
Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Чтобы выяснить, так ли это, мы смотрим, что осталось от суммы после применения жадного»алгоритма. Если остаток равен [latex]0[/latex], то исходную сумму можно получить с помощью имеющихся купюр, и на экран выводится результат, полученный в цикле. Если же остаток больше [latex]0[/latex], такую операцию осуществить невозможно и программа выводит [latex]-1[/latex].
Публиковать можно только задачи, которые получены Вами в качестве индивидуального задания от кого-то из преподавателей. В любом случае оно должно быть оформлены так, как описано здесь и обязательно должно содержать все перечисленные там элементы.
Пожалуйста, доделайте это задание полностью и поставьте снова на проверку.
Спасибо, Игорь Евгеньевич. Исправила.
Есть несколько замечаний:
— Не нужно вставлять в коде программы пустые строки после каждой строки с текстом.
— 1 ≤ n ≤ 1000000 это тоже формула, значит нужен latex
-В разделе «Алгоритм» Вы не приводите ни обоснование правильности алгоритма, ни самого алгоритма. Например, последняя фраза «В конце программы проводится проверка на наличие остатка, меньшего 10» и соответствующий комментарий не соответствуют коду программы. Да, для данных значений элементов массива в конце в переменной n окажется остаток от деления на 10. Но 10 не является волшебным числом, волшебное число — минимальное значение элементов массива. Которое у Вас сейчас действительно 10 🙂
Пожалуйста, разберитесь в чём именно состоит алгоритм, который Вы публикуете. Это так называемый жадный алгоритм. Он гораздо глубже и интереснее чем «цикл, в котором находит количество тех или иных купюр».
Спасибо, разобралась и исправила.
Хорошо получилось. Зачтено.