Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ разложение числа

Автор: -dila- 28.09.2005 22:26

Здраствуйте! Мне тут задачку задали... Вот условие: есть число М и последовательность из 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!!! Помогите сделать так, чтобы прога заработала! Пожалуйста!!!

Автор: klem4 28.09.2005 22:37

Цитата

числа: 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 и числа именно такие)... могу предложить полный перебор

)) но это не выход, кстати такая задача помойму была на форуме, поищи ...

Автор: volvo 29.09.2005 19:19

-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- 29.09.2005 19:52

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

И еще:

Код

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

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

Автор: volvo 29.09.2005 20:00

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

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- 29.09.2005 20:26

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

Автор: Kolyancz 26.11.2008 19:32

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

Автор: volvo 26.11.2008 21:10

Цитата

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

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

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;