разложение числа Опции

[-dila-]

Здраствуйте! Мне тут задачку задали... Вот условие: есть число М и последовательность из N чисел а1,а2,...аN. Надо посчитать, сколькими способами можно представить М в виде суммы этих чисел. Например: М=6, числа: 1,3,5,2, тогда 6=1+5=1+2+3, итого 2 способа.
Вот что получилось у меня:

Код

Program summa;

type tms=array[1..100] of integer;

procedure in_mas(var ms:tms; n,m:integer);
var i:integer;
begin
 for i:=1 to n do
  begin
   writeln('Введите числа, меньшие ',m);
   readln(ms[i]);
  end;
end;

procedure find(var ms:tms; n,m,s,sum:integer; var count:integer);
var i:integer;
begin
 if sum<m then
  begin
   for i:=s to n do
    begin
     sum:=sum+ms[i];
     find(ms,n,m,s,sum,count)
    end;
  end
 else
   if sum=m then
   count:=count+1
end;

var
ms:tms;
n,m,sum,count,s:integer;

begin
writeln('Введите число:');
readln(m);
writeln('Введите кол-во элементов');
readln(n);
in_mas(ms,n,m);
s:=1;
sum:=0;
count:=0;
find(ms,n,m,s,sum,count);
writeln(count);
readln;
end.

Help!!! Помогите сделать так, чтобы прога заработала! Пожалуйста!!!

Сообщение отредактировано: -dila- - 29.09.2005 19:56

[klem4]

числа: 1,3,5,2, тогда 6=1+5=1+2+3, итого 2 способа.

а как же : 1+1+1+1+1+1 = 3+3 = 2+2+2 = 3+1+2 = 5 + 1 = 2 + 1 + 3 = 6...

количество слогаемых не ограничено чтоли ?? я вот уже 6 способов нашел

тут конечно больше 6-ти слогаемых не будет (если m=6 и числа именно такие)... могу предложить полный перебор )) но это не выход, кстати такая задача помойму была на форуме, поищи ...

Сообщение отредактировано: klem4 - 28.09.2005 22:40

[volvo]

-dila-, такой вариант устроит?

var
  n: integer;
  c: array[1..100] of smallint;
  print: boolean;

const
  diapazon: set of byte = [1, 2, 3, 5];

procedure find(num,k,len: smallint);
var i: smallint;
begin
  if num=0 then begin
    print := true;
    for i := 1 to pred(len) do
      if not (c[i] in diapazon) then print := false;

    if print then begin
      for i:=1 to len-1 do write(c[i],' '); writeln
    end;
  end
  else begin
    for i:=1 to k do
      if num-i>=0 then begin
        c[len]:=i;
        find(num-i,i,len+1);
      end;
  end;
end;

begin
  n := 6;
  find(n,n,1);
  readln
end.

[-dila-]

Спасибо большое за код! Общую идею я вроде поняла, вот только pred(len) мы не проходили. Недьзя ли это на что-нибудь заменить?

И еще:

Код

const
 diapazon: set of byte = [1, 2, 3, 5];

Эти числа, по условию задачи, должны вводиться с клавиатуры...

[volvo]

Тогда вот так:

var
  n: integer;
  c: array[1..100] of smallint;
  print: boolean;

  diapazon: set of byte;

{
  Здесь сама процедура Find
  ... 
}

var x: byte;
begin
  diapazon := []; { изначально - пустое множество }

  repeat { Для окончания ввода слагаемых ввести 0 }
    Write( 'Следующее слагаемое: ' ); ReadLn(x);

    If x > 0 Then
      diapazon := diapazon + [x]; { и добавляем введенное число к множеству }
  until x = 0;

  n := 6; { <--- Это тоже можно при необходимости считать с клавиатуры }
  find(n,n,1);
  readln
end.

Кстати, Pred(len) это то же самое, что len - 1 :yes:

[-dila-]

Так намного лучше. Еще раз спасибо!

[Kolyancz]

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

[volvo]

что бы между числами были плюсы, но что бы после последнего числа плюса не было. Как это сделать?

Немного по-другому печатать:

procedure find(num,k,len: smallint);
const sign: array[boolean] of char = ('+', ' '); { <--- Вот это добавляется }
var
  i: smallint;
begin
  if num=0 then begin
    print := true;
    for i := 1 to pred(len) do
      if not (c[i] in diapazon) then print := false;

    if print then begin
      for i:=1 to len-1 do write(c[i], sign[i = len - 1]); writeln { <--- ну, и здесь }
    end;
  end
  else begin
    for i:=1 to k do
      if num-i>=0 then begin
        c[len]:=i;
        find(num-i,i,len+1);
      end;
  end;
end;