Помощь - Поиск - Пользователи - Календарь
Полная версия: Помогите, комбинаторная программа медленно работает
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
knight
Задача такая: надо распределить определённый объём по нескольким другим и оценить такие сочетания.
Я сделал так:
=================================================
procedure TForm1.Button2Click(Sender: TObject);
var i:integer;
v:array of byte;// [0..4]
s,p:integer;
t:cardinal;
begin
i:=0;
p:=30;
setlength(v,3);
for i:=0 to length(v)-1 do
v[i]:=0;
t:=windows.GetTickCount ;
repeat
if v[0]=p then begin showmessage('Приехали'); break;end;
v[length(v)-1]:=v[length(v)-1]+1;
for i:=length(v)-1 downto 1 do
begin
if (v[i]> p-1) then begin V[i-1]:=V[i-1]+1; V[i]:=0; end;
end;
s:=0;
for i:=0 to length(v)-1 do s:=s+v[i];
if s=p then begin
for i:=0 to length(v)-1 do form1.Memo1.Lines.Add(inttostr(v[i])+' ');
form1.Memo1.Lines.Append('------------------------');
form1.Memo1.Lines.Append(inttostr(s));
form1.Memo1.Lines.Append('==========================');
end;
until v[0]=p;
t:=windows.GetTickCount -t;
form1.Memo1.Lines.Append(floattostr(t/100)+' c');
end;

================================================
это означает, что имеем некий массив типа байт, и гоним все сочетания, которые могут в нём быть, и в лёт отфильтровываем те сочетания, которые в сумму дают заданное значение.
Требования такие: должна быть довольно высокая точность деления объёма. (в примере это 30 а надо где-то более 100)
Данный пример отфильтровывает нужные сочетания где-то за минуту.
Возможно ли создание гораздо более быстрого алгоритма?
Например такого, который не фильтрует из всех сочетний, а создаёт их сам?
Спасибо за ответы.
volvo
Цитата
Возможно ли создание гораздо более быстрого алгоритма?
У тебя время, в основном, тратится НЕ на вычисления, а на вывод информации. Смотри... Твой первоначальный вариант выдал мне 49 с. Ну, о том, секунды это или нет, можно еще поспорить, не в этом сейчас дело. Будем считать, 49 единиц. Закомментируем 2 строки:

if s=p then begin
for i:=0 to length(v)-1 do form1.Memo1.Lines.Add(inttostr(v[i])+' ');
{ form1.Memo1.Lines.Append('------------------------'); }
form1.Memo1.Lines.Append(inttostr(s));
{ form1.Memo1.Lines.Append('=========================='); }
end;


Результат - меньше 32 единиц... А ведь его можно еще уменьшить... Так что...
knight
Цитата(volvo @ 14.09.2006 10:34) *

У тебя время, в основном, тратится НЕ на вычисления, а на вывод информации.


Во. Спасибо! Точно, чё-то я затупил. Да, и там в конце надо делить на 1000, тогда будут секунды.
Да, я это убрал, и результаты:
при длине масива в 3 элемента и точности (p) 100 время 0.07 секунды
А при длине уже в 4 элемента время 8.3 секунды
Если длина 5 - то я по дождал несколько минут а оно только еле-еле до половины допёрло.
Вот.
Ну у меня от времени довольно много зависит. Это только подпрограмма, которая должна сама выполняться какое-то количество раз, и вообще : получится то-ли типа рендеринга долгого и нудного, то-ли прога, считающая в лёт.
Может такая задача как-то кем-то решена, может ссылочку или хотябы её название кто-нить знает?
volvo
Вот тут я делал нечто очень подходящее тебе:
Разбиение числа на слагаемые

Нужно будет только немного подправить для твоего условия (ограничить длину последовательности), и добавить еще одну процедуру генерации всех возможных перестановок найденных чисел. В итоге, я думаю, должен получиться выигрыш во времени...

Справишься?
volvo
Вот я тут наколдовал что-то. Ты бы рассказал, как надо результаты представлять (точнее, куда передавать), а то неизвестно, что с ними делать (в массив что-ли в динамический закидывать?)... Но вот сама генерация при таком алгоритме происходит практически мгновенно:

uses windows;
var
p: integer;
len: integer;

type
parr = array[0 .. 10] of integer;

{.$define PRINTING}

procedure generate(prev: integer; var arr: parr; level: integer);
var i: integer;
begin
if level = 0 then begin
arr[len] := p - prev;
{$ifdef PRINTING}
for i := 0 to len do
write(arr[i]:4);
writeln;
{$endif}
end
else begin
for i := 0 to p - prev do begin
arr[len - level] := i;
generate(prev+i, arr, level - 1);
end;
end;

end;

var
arr: parr;
T: dword;
begin
p := 120;
len := 5;

T := gettickcount();
generate(0, arr, len);
writeln('p = ', p, ' len = ', succ(len), ' generated: ', gettickcount() - T, ' cycles...');
end.


Цитата(Console)
p = 120 len = 5 generated: 141 cycles...
p = 100 len = 6 generated: 1531 cycles...
p = 120 len = 6 generated: 3688 cycles...
p = 70 len = 7 generated: 3703 cycles...
Меньше чем за 4 секунды генерируются сочетания из 7 чисел, дающих в сумме 70...
knight
Цитата(volvo @ 15.09.2006 3:35) *

Вот я тут наколдовал что-то. Ты бы рассказал, как надо результаты представлять (точнее, куда передавать), а то неизвестно, что с ними делать (в массив что-ли в динамический закидывать?)...

Здравствуйте!
Спасибо большое. Да, в принципе можно в массив сочетания закинуть и там уже с ними эксперементировать.
Щас пытаюсь воткнуть код в делфи... Только я не понял как он работает. Всё вроде просто, а чего он делает не поюму.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.