Составить нужную сумму монетами Опции

[maximuss]

Определить количество 5, 20 и 50 копеечных монет, необходимое для набора суммы 4 рубля. При условии, что общее количество монет должно быть равно 20.

заранее спасибо

[Unconnected]

Самый примитивный перебор, для 3х видов монет можно сделать без рекурсии.. ну и тут можно ввести незначительные отсечения.

const sum=400;
      limit=20;
      m1=5;m2=20;m3=50;
var i,j,k:integer;

begin
  for i:=1 to (sum div m1) do
    for j:=1 to (sum div m2) do
      for k:=1 to (sum div m3) do
        if (i+j+k=limit) and (m1*i + m2*j + m3*k=sum) then writeln(i,' ',j,' ',k);
  readln;
end.

[Lapp]

Самый примитивный перебор, для 3х видов монет можно сделать без рекурсии..

Можно и без рекурсии (хотя, если число видов монет может меняться, то лучше все же с ней, родимой)). Но только зачем три цикла? Если убрать последний, то (как бонус)) и проверок меньше делать придется .

  for i:=1 to (sum div m1) do
    for j:=1 to (sum-i*m1) div m2 do
      if m1*i + m2*j + m3*(limit-i-j)=sum then writeln(i,' ',j,' ',limit-i-j);

Кроме прочего, я тут подкорректировал верхний предел второго цикла. По-хорошему, нужно в качестве предела брать минимум из ((sum-i*m1) div m2) и (limit-i), но это утяжелит код..

Сообщение отредактировано: Lapp - 24.07.2011 0:28