Question

В банкомате имеются в достаточном количестве купюры номиналом 50, 100, 200, 500 и 1000 рублей. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в n рублей или вывести -1, если указанную сумму выдать нельзя. Входные данные. Одно число n (1 ≤ n ≤ 10^6).Выходные данные. Вывести наименьшее количество купюр, которыми можно выдать n рублей.(Pascal)

Answer 1

Ответ:

выводится: сколько и каких купюр надо выдать.

если запрашиваемую сумму выдать невозможно - выведется соответствующее сообщение.

Объяснение:

Pascal

const

 k: array[0..4] of integer =(1000,500,200,100,50);

var

 z:integer;

 

 function getk(i, s: integer): integer;

 begin

   if s=0 then exit;

   if s div k[i] > 0 then  println(s div k[i], 'куп. по', k[i], 'рублей');

   getk(i+1, s-k[i]*(s div k[i]))

 end;    

begin

 writeln('Сколько рублей ходите снять?');

 readln(z);

         

 if z mod 50 <> 0 then print('Выдать запрашиваемую сумму невозможно')

 else getk(0,z);

 

end.

Answer 2

Для решения этой задачи можно воспользоваться жадным методом. Жадный метод заключается в том, чтобы всегда выбирать максимально возможную купюру на каждом шаге. В данном случае, начиная с самой крупной купюры, мы будем поочередно вычитать ее из суммы до тех пор, пока не достигнем нужной суммы n.

Вот пример кода на языке Pascal:

program MinBanknotes;

var
  n, count, remainder: Integer;

begin
  // Вводим сумму n
  writeln('Введите сумму n: ');
  readln(n);

// Инициализируем счетчик купюр
  count := 0;

// Выбираем купюры, начиная с самой крупной
  if n >= 1000 then
  begin
    count := n div 1000; // количество купюр номиналом 1000
    n := n mod 1000; // остаток после выдачи купюр номиналом 1000
  end;

if n >= 500 then
  begin
    count := count + n div 500; 
    n := n mod 500;
  end;

if n >= 200 then
  begin
    count := count + n div 200;
    n := n mod 200;
  end;

if n >= 100 then
  begin
    count := count + n div 100;
    n := n mod 100;
  end;

if n >= 50 then
  begin
    count := count + n div 50;
    n := n mod 50;
  end;

// Проверяем, удалось ли выдать сумму точно
  if n = 0 then
    writeln('Минимальное количество купюр: ', count)
  else
    writeln('Невозможно выдать указанную сумму');

end.

Этот код сначала проверяет, сколько купюр номиналом 1000, 500, 200, 100 и 50 рублей можно использовать для выдачи суммы n. Затем выводится минимальное количество купюр, которое необходимо использовать для выдачи суммы n, или выводится -1, если указанную сумму нельзя выдать.