Задача на сумму к оплате.

[caterva]

Помогите пожалуйста, срочно нужно досдать задачу, а я не понимаю как ее писать, в алгоритм никак не въеду=\
С терминала вводится число n. Считая, что введенное число-сумма, подлежащая оплате, напечатать все варианты ее оплаты в банкнотах и монетах, имеющихся на данный момент в обороте. Найти способ, требующий наименьшего количества банкнот и монет. В задаче нужно использовать рекурсию, номиналы банкнот и монет беруться из файла или вводятся как константы, можно присваивать их внутри программы, это несущественно.
Если кто то может-помогите, нужно позарез просто=\

[InternetStranger]

По секрету (из тервера) расскажу, что если N-ом обзовем количество уникальных денюжек (купюр или монетов), то всего вариантов, которыми можно набрать требуемую сумму (максимальное их количество):

Все варианты не стал перебирать - это не сложно.


В моей реализации: M( N=11 )=2047 вариантов. А потому алгоритм следующий:
1) Лучший вариант – в котором наименьшее количество банкнот и монет).
2) Если номиналы выразить в рублях, то монета определяется из условия: n<10
3) Сразу сообразим: если получится удачная комбинация из Z<N денюжек, то рассматривать комбинации Z+1 не имеет смысла по определению, потому будем сначала набирать сумму максимальными денюжками (рекурсией).
4) Кстати, кто не знаком с особенностями машинной арифметики:
в проге в переменной s накапливается после нескольких итераций ошибки округления. Пошагово можете посмотреть, кому интересно. В первую очередь подозрения ложатся на криворукость Борланда в фунции trunc.
Поэтому условие: s<>0 пришлось заменить на |s|>0.001;

const N = 11; // число уникальных монет и купюр
      mon  : array [1..N] of real =(5000,1000,500,100,50,10,5,1,0.1,0.05,0.01);  // массив с номиналами денюжек (в руб.)

var   comb : array[1..N] of integer;  // комбинации банкнот разных порядков (порядок - порядковый номер в массиве mon)

procedure money(s:real;p:integer);  // сколькими банкнотами p-го порядка можно набрать сумму, не превосходящую s
begin
     comb[p]:= comb[p] + trunc(s/mon[p]);
     s:= s - comb[p]*mon[p];
     if {s<>0}abs(s)>0.001 then begin
        inc(p);
        money(s,p);
     end;     
end;

procedure TForm1.Button1Click(Sender: TObject);
var p : integer;
    s : real;
begin
     memo1.clear;
     s:= strtofloat(edit1.text);
     for p:=1 to N do comb[p]:=0;
     money(s,1);
     for p:=1 to N do
         if comb[p]<>0 then begin
            if mon[p]>10 then memo1.lines.add(' + '+inttostr(comb[p])+' * '+inttostr(trunc(mon[p]))+'руб.')
            else memo1.lines.add(' + '+inttostr(comb[p])+' * '+inttostr(trunc(100*mon[p]))+'коп.');
         end;

end;

Исходник здесь!

[caterva]

Спс) Но..файл исходника поврежден, и открываться отказывается=\ и если честно, не совсем понятны значения команд memo1.clear , strtofloat(edit1.text) , memo1.lines.add , inttostr...Поясните плиз)))

[Elm0]

Сообщение от caterva

и если честно, не совсем понятны значения команд memo1.clear , strtofloat(edit1.text) , memo1.lines.add , inttostr...Поясните плиз)))

Delphi это..

[caterva]

...нда..теперь ясно) просто мне задача на паскале нужна, да и сама я только паскаль и с++ знаю)) а..нельзя то же самое в паскаль перевести?

[InternetStranger]

можно и на паскале. че-то я забыл про название раздела.
качай

[caterva]

хм..я так понимаю, эта программа выводит только максимальное количество купюр и монет, из которого можно собрать заданную сумму. А как вывести все возможные варианты?

[caterva]

ну в общем, спс огромное, я ее сама решила) там он ме правда ошибку выводит хз почему, но , думаю, разберусь. Спс за помощь+)

[InternetStranger]

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