Глотов 26 ноября 2019 в 07:34
Задача по информатике. Pascal или Delphi с подробным решением и объяснениями!
Банкомат
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каж дого номинала неограничен. Помогите Национальному банку решить эту задачу.
Входные данные
Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, ..., xN, не превосходящих 106 — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 106 —сумму, которую
необходимо выдать.
Выходные данные
Программа должна найти представление числа S виде суммы слагаемых из множества xi, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.
Примеры
входные данные
5
1 3 7 12 32
40
выходные данные
32 7 1
Задача по информатике. Pascal или Delphi с подробным решением и объяснениями!
Банкомат
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каж дого номинала неограничен. Помогите Национальному банку решить эту задачу.
Входные данные
Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, ..., xN, не превосходящих 106 — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 106 —сумму, которую
необходимо выдать.
Выходные данные
Программа должна найти представление числа S виде суммы слагаемых из множества xi, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.
Примеры
входные данные
5
1 3 7 12 32
40
выходные данные
32 7 1
Var v:array [0..100000] of integer; a:array [0..100,0..100000] of integer; m,p,k,w:integer;
procedure step(z,ma:integer);beginif zgt;0 then if a[z,ma]lt;gt;a[z-1,ma] then if a[z-1,ma]lt;a[z-1,ma-v[z]]+v[z] then begin step(z-1,ma-v[z]); write(v[z], ); end else step(z-1,ma) else step(z-1,ma); end;
beginread(k);for p:=1 to k do begin read(v[p]); end;read(w);for p:=1 to k do begin for m:=1 to w do begin if m-v[p]gt;=0 then a[p,m]:=(max(a[p-1,m-v[p]]+v[p],a[p-1,m])) else a[p,m]:=a[p-1,m]; end; end;if a[k,w]=w then step(k,w) else writeln(No solution);end.
procedure step(z,ma:integer);beginif zgt;0 then if a[z,ma]lt;gt;a[z-1,ma] then if a[z-1,ma]lt;a[z-1,ma-v[z]]+v[z] then begin step(z-1,ma-v[z]); write(v[z], ); end else step(z-1,ma) else step(z-1,ma); end;
beginread(k);for p:=1 to k do begin read(v[p]); end;read(w);for p:=1 to k do begin for m:=1 to w do begin if m-v[p]gt;=0 then a[p,m]:=(max(a[p-1,m-v[p]]+v[p],a[p-1,m])) else a[p,m]:=a[p-1,m]; end; end;if a[k,w]=w then step(k,w) else writeln(No solution);end.
Компьютеры и вычисления
349
0
Для комментирования необходимо зарегистрироваться на сайте