Задача в PascalABC.NET. Задана сумма денег в купюрах N. Провести размен монетами, если в кассе есть N1 — штук по рублю, N2-штук по 2 рубля, N5-штук по 5 рублей, N10 — штук по 10 рублей

Вопрос школьника по предмету Информатика

Задача в PascalABC.NET. Задана сумма денег в купюрах N. Провести размен монетами, если в кассе есть N1 — штук по рублю, N2-штук по 2 рубля, N5-штук по 5 рублей, N10 — штук по 10 рублей

Ответ учителя по предмету Информатика

«Жадный» алгоритм

// PascalABC.NET 3.2, сборка 1417 от 28.03.2017

// Внимание! Если программа не работает, обновите версию!

begin

  var k:=Arr(1,2,5,10); // номиналы монет

  var m:=ReadArrInteger(‘Кол-во монет по ‘+k.JoinIntoString+’ руб:’,4);

  var n:=ReadInteger(‘Сумма в купюрах, руб:’);

  if m.Zip(k,(p,q)->p*q).Sum<n then begin // нехватка монет

    Writeln(‘Размен невозможен’); exit

    end;

  var s:=»; // для результатов

  for var i:=k.Length-1 downto 0 do

    if (n>=k[i]) and (m[i]>0) then begin // номинал участвует

      var t:=min(n div k[i],m[i]); // кол-во монет

      n:=n-k[i]*t; // остаток

      if s.Length>0 then s+=’, ‘;

      s+=t+’ по ‘+k[i]+’ руб.’;

      end;

  if n<>0 then Writeln(‘Размен невозможен’)

  else Writeln(s)

end.

Примеры

Кол-во монет по 1 2 5 10 руб: 350 215 86 130

Сумма в купюрах, руб: 1526

130 по 10 руб., 45 по 5 руб., 1 по 1 руб.

Кол-во монет по 1 2 5 10 руб: 500 146 0 38

Сумма в купюрах, руб: 432

38 по 10 руб., 26 по 2 руб.

Кол-во монет по 1 2 5 10 руб: 10 20 30 40

Сумма в купюрах, руб: 25000

Размен невозможен