Помощь - Поиск - Пользователи - Календарь
Полная версия: разложение числа
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
-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!!! Помогите сделать так, чтобы прога заработала! Пожалуйста!!!
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 и числа именно такие)... могу предложить полный перебор smile.gif)) но это не выход, кстати такая задача помойму была на форуме, поищи ...
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-
Так намного лучше. Еще раз спасибо! smile.gif
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;
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.