Кол-во циклов зависит от вводимой переменной N

← →
Magic (2008-07-09 08:54) [0]

День добрый! Суть вопроса: есть уравнение: сумма от j=1 до N, (j*m[j]=N). (например, для N=2 получаем 1*m[1]+2*m[2]=N). Чтоб решить уравнение необходимо перебирать значения m[1] и m[2] в пределах от 0 до 2. То есть получается цикл в цикле. Все это хорошо, но вот при N=20, 20 циклов как то много писать, да и программа не мобильна. А теперь сам вопрос: Как это сделать? Спасибо!

← →
Johnmen © (2008-07-09 09:06) [1]

Поднимите мне веки (с)
Где тут более одного цикла?

← →
Magic (2008-07-09 09:38) [2]

Johnmen! Будьте так добры написать код программы, если Вас это не затруднит. Спасибо!

← →
engine © (2008-07-09 09:41) [3]

function SumN( N : Integer) : Double; var j : Integer; begin Result := 0; for j := 1 to N do Result := Result + j*m[j]; end;

← →
Сергей М. © (2008-07-09 09:55) [4]

> engine © (09.07.08 09:41) [3]

Ему ж, кажись, именно уравнение надо решить, а не просто расчитать функцию аргумента N ..

for N:= MinN to MaxN do
if N = SumN(N) then Break;

if N <= MaxN then
Show Message("Уравнение имеет решение при N = " + IntToStr(N));

← →
Magic (2008-07-09 10:00) [5]

Engine! Не будет работать! m[j] - массив данных, со значениями от 0 до N. Решаю данное уравнение при N=2. 1*m[1]+2*m[2]=2 - перебираем значения m[1] и m[2] от 0 до 2 : m[1]=0 , тогда чтобы уравнение было верным m[2]=1 (1*0+2*1=2); берем m[1]=2 (m[1]=1 не подходит) , тогда m[2]=0.

for i:=0 to N do begin
M[1]:=i;
for j:=0 to N do begin
M[2]:=j;
s:=M[1]+2*M[2];
if s=N then {выводим например в листбокс для проверки}

но если N=10 - 10 циклов писать ...!!! Может есть другой способ?

← →
Ega23 © (2008-07-09 10:06) [6]

Рекурсию писать.

← →
Magic (2008-07-09 10:10) [7]

Программа для N=5:

for i:=0 to N do begin
M[1]:=i;
for j:=0 to N do begin
M[2]:=j;
for x:=0 to N do begin
M[3]:=x;
for l:=0 to N do begin
M[4]:=l;
for z:=0 to N do begin
M[5]:=z;
s:=M[1]+2*M[2]+3*M[3]+4*M[4]+5*M[5];

if s=N then begin

listbox1.Items.Add("M1="+floattostr(M[1])+":::"+
"M2="+floattostr(M[2])+":::"+"M3="+floattostr(M[3])+":::"+
"M4="+floattostr(M[4])+":::"+"M5="+floattostr(M[5]));

end; // if"s end

end
end;
end;
end;
end;

Нужны все возможные варианты массива M[].

← →
Magic (2008-07-09 10:12) [8]

Рекурсия не поможет. Нет зависимости последующих значений решения от предыдущих.

← →
Сергей М. © (2008-07-09 10:20) [9]

> m[j] - массив данных, со значениями от 0 до N

И нафига нужно держать в элементах массива значения, равные индексам соответствующих элементов ?

Непонятно, зачем тут понадобился массив ..

> значения m[1] и m[2] в пределах от 0 до 2

Откуда там возьмется 0 ("ноль"), если он, согласно твоим же пояснениям, может находиться лишь в элементе m[0] ?

← →
Ega23 © (2008-07-09 10:20) [10]

> Рекурсия не поможет. Нет зависимости последующих значений
> решения от предыдущих.

Зависимость очередного шага от предыдущего в рекурсии - это один из частных случаев.

← →
Magic (2008-07-09 10:32) [11]

Сергей М. согласен, можно без массива. Тогда будет не M[1], а M1, значения которого перебираются от 0 до N; M0 не существует вообще. Уравнение: сумма от j=1 до N (j*Mj=N)

← →
McSimm © (2008-07-09 10:34) [12]

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

Там не индексы, там произвольные значения от 0 до N

> Нужны все возможные варианты массива M[]

С перестановками

> Рекурсия не поможет.

Почему?

Sum(j*m[j]) => N*m[N] + S(k*m[k]), k = 1..N-1

function SumN

← →
Magic (2008-07-09 10:43) [13]

Ega23! при N=2 решениями уравнения явл:
m1=2, m2=0 (1*2+2*0=2) и
m1=0, m2=1 (1*0+2*1=2)

при N=3:
m1=0, m2=0, m3=1 (1*0+2*0+3*1=3);
m1=1, m2=1, m3=0 (1*1+2*1+3*0=3);
m1=3, m2=0, m3=0 (1*3+2*0+3*0=3);

Где тут зависимость?

← →
Ega23 © (2008-07-09 10:46) [14]

> Где тут зависимость?

3=2+1

← →
Сергей М. © (2008-07-09 10:47) [15]

> Magic

http://alglib.sources.ru/combinatorial/backpack.php

оно ?

Размен монет. Направленный перебор.

← →
Magic (2008-07-09 11:50) [18]

Спасибо всем, Ребята! Задача о рюкзаке и метод Размена монет похожи на мою задачку.
Направление задано ...

Если суммы не слишком велики, можно решать динамическим программированием за асимптотическиое время O(N*Sum)

пардон, это количество вариантов решения можно за указанное время посчитать, а сами их составлять получится, конечно, за пропорциональное общей их длине время

type TOnResult= procedure(a: array of integer) of object; procedure Banker(n: integer; OnResult: TOnResult); procedure DoLevel(level, sum: integer; a: array of integer); var i: integer; begin; a[Level]:=0; repeat; i:=level-1; while i>=sum do begin; a[i]:=0; i:=i-1; end; if i>0 then DoLevel(i, sum, a) else begin; a[0]:=sum; OnResult(a); end; a[Level]:=a[level]+(level+1); sum:=sum-(level+1); until sum<0; end; var a: array of integer; i: integer; begin; if not Assigned(OnResult) then exit; SetLength(a,n); if n>1 then DoLevel(n-1, n, a) else begin; a[0]:=1; OnResult(a); end; end; procedure TForm1.ShowResult(a: array of integer); var i: integer; s: string; begin; s:=""; for i:=0 to Length(a)-1 do s:=s+" "+IntToStr(a[i] div (i+1)); Memo1.Lines.Add(s); end; procedure TForm1.Button1Click(Sender: TObject); var n: integer; begin; Memo1.Lines.Clear; n:=StrToIntDef(Edit1.Text, 0); if n>0 then Banker(n, ShowResult); end;

Кол-во циклов зависит от вводимой переменной N - возможно ли? Найти похожие ветки