Условия: В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот ка...
Условия: В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Национальному банку решить эту задачу.
Входные данные: Первая строка входных данных содержит натуральное число n, 0
Гость
Гость
Ответ(ы) на вопрос:
Гостьтакой вариант на простом паскале со стратегией жадность
var
n, s, i: integer;
x: array[1..100]of integer;
answer: string;
begin
readln(n);
for i := 1 to n do
read(x[i]);
readln(s);
answer := IntToStr(s) + ' = ';
for i := n downto 1 do
begin
answer := answer + IntToStr(s div x[i]) + '*' + IntToStr(x[i]);
s := s mod x[i];
if i > 1 then
answer := answer + ' + ';
end;
if s <> 0 then
writeln('NO')
else
writeln(answer);
end.
Более полный и правильный вариант решения, но и куда более сложный
//PascalABC.Net 3.1 сборка 1200
uses System.Collections.Generic;
uses System;
var
x := new List;
c := new List>;
procedure getParcelling(sum, step: integer; coefficients: string; count: integer);
begin
if step >= x.Count then begin
if sum = 0 then c.Add((coefficients, count));
Exit;
end;
if step < 0 then step := 0;
for var j := 0 to (sum div x[step]) do
begin
var s := '';
if j > 0 then begin
if step > 0 then s += ' + ';
s += IntToStr(j) + '*' + IntToStr(x[step]);
end;
getParcelling(sum - x[step] * j, step + 1, coefficients + s, count + j);
end;
end;
begin
x := ReadArrInteger('x:', ReadInteger('n =')).ToList;
var sum := ReadInteger('sum =');
getParcelling(sum, 0, '', 0);
if c.Count = 0 then
writeln('No')
else begin
var min := c.Min(cc -> cc.Item2);
Println(c.Where(cc -> cc.Item2 = min));
end;
end.
Не нашли ответ?
Похожие вопросы