| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Кол-во циклов зависит от вводимой переменной N - возможно ли? [D7]
Magic © (2008-07-09 08:54:00)День добрый! Суть вопроса: есть уравнение: сумма от 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 циклов как то много писать, да и программа не мобильна. А теперь сам вопрос: Как это сделать? Спасибо!
Sha (2008-07-10 10:36:00) [1]
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;
MBo (2008-07-09 13:36:00) [2]пардон, это количество вариантов решения можно за указанное время посчитать, а сами их составлять получится, конечно, за пропорциональное общей их длине время
MBo (2008-07-09 12:23:00) [3]Если суммы не слишком велики, можно решать динамическим программированием за асимптотическиое время O(N*Sum)
Magic (2008-07-09 11:50:00) [4]Спасибо всем, Ребята! Задача о рюкзаке и метод Размена монет похожи на мою задачку.
Направление задано ...
Sha (2008-07-09 10:53:00) [5]Размен монет. Направленный перебор.
Сергей М. (2008-07-09 10:48:00) [6]
> Magic
http://alglib.sources.ru/combinatorial/backpack.php
оно ?
Сергей М. (2008-07-09 10:47:00) [7]
> McSimm © (09.07.08 10:34) [12]
Тогда, похоже, формулировка задачи растет из разновидности "задачи о рюкзаке"..
Ega23 (2008-07-09 10:46:00) [8]
> Где тут зависимость?
3=2+1
Magic (2008-07-09 10:43:00) [9]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);
Где тут зависимость?
McSimm (2008-07-09 10:34:00) [10]>
> И нафига нужно держать в элементах массива значения, равные
> индексам соответствующих элементов ?
>
> Непонятно, зачем тут понадобился массив ..
Там не индексы, там произвольные значения от 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:32:00) [11]Сергей М. согласен, можно без массива. Тогда будет не M[1], а M1, значения которого перебираются от 0 до N; M0 не существует вообще. Уравнение: сумма от j=1 до N (j*Mj=N)
Ega23 (2008-07-09 10:20:00) [12]
> Рекурсия не поможет. Нет зависимости последующих значений
> решения от предыдущих.
Зависимость очередного шага от предыдущего в рекурсии - это один из частных случаев.
Сергей М. (2008-07-09 10:20:00) [13]
> m[j] - массив данных, со значениями от 0 до N
И нафига нужно держать в элементах массива значения, равные индексам соответствующих элементов ?
Непонятно, зачем тут понадобился массив ..
> значения m[1] и m[2] в пределах от 0 до 2
Откуда там возьмется 0 ("ноль"), если он, согласно твоим же пояснениям, может находиться лишь в элементе m[0] ?
Magic (2008-07-09 10:12:00) [14]Рекурсия не поможет. Нет зависимости последующих значений решения от предыдущих.
Magic (2008-07-09 10:10:00) [15]Программа для 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[].
Ega23 (2008-07-09 10:06:00) [16]Рекурсию писать.
Magic (2008-07-09 10:00:00) [17]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 циклов писать ...!!! Может есть другой способ?
Сергей М. (2008-07-09 09:55:00) [18]
> 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));
engine (2008-07-09 09:41:00) [19]
function SumN( N : Integer) : Double;
var j : Integer;
begin
Result := 0;
for j := 1 to N do
Result := Result + j*m[j];
end;
Magic (2008-07-09 09:38:00) [20]Johnmen! Будьте так добры написать код программы, если Вас это не затруднит. Спасибо!
| |
Страницы: 