Помогите решить задачу в Паскале. Покупатель должен заплатить в кассу S рублей. У него...

Question

Помогите решить задачу в Паскале. Покупатель должен заплатить в кассу S рублей. У него имеются 1, 2, 5, 10, 50, 100, 500-рублевые купюры. Сколько купюр разного достоинства отдаст покупатель, если начнет платить с самых крупных?

Answer 1

PascalABC.NET 3.2, сборка 1383 от 09.02.2017
Внимание! Если программа не работает, обновите версию!

Используем "жадный" алгоритм. Он не всегда дает минимальное общее количество купюр, но зато простой в понимании.

begin
  var k:=Arr(500,100,50,10,5,2,1); // массив с достоинствами купюр
  var s:=ReadInteger('Введите сумму:'); // сумма к оплате
  Writeln('Уплатить:');
  var i:=0;
  while s>0 do begin
    var p:=s div k[i];
    if p>0 then Writeln(p,' шт. достоинством ',k[i],' руб.');
    s:=s mod k[i]; i+=1
    end;
end.

Примеры
Введите сумму: 3794
Уплатить:
7 шт. достоинством 500 руб.
2 шт. достоинством 100 руб.
1 шт. достоинством 50 руб.
4 шт. достоинством 10 руб.
2 шт. достоинством 2 руб.

Введите сумму: 507
Уплатить:
1 шт. достоинством 500 руб.
1 шт. достоинством 5 руб.
1 шт. достоинством 2 руб.