IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Помогите, комбинаторная программа медленно работает, Подскажите, дело в самой задаче или в алгоритме?
сообщение
Сообщение #1


Гость






Задача такая: надо распределить определённый объём по нескольким другим и оценить такие сочетания.
Я сделал так:
=================================================
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 -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата
Возможно ли создание гораздо более быстрого алгоритма?
У тебя время, в основном, тратится НЕ на вычисления, а на вывод информации. Смотри... Твой первоначальный вариант выдал мне 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 единиц... А ведь его можно еще уменьшить... Так что...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Цитата(volvo @ 14.09.2006 10:34) *

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


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


Гость






Вот тут я делал нечто очень подходящее тебе:
Разбиение числа на слагаемые

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

Справишься?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






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

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...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 1
Пол: Мужской
Реальное имя: Bkmz

Репутация: -  0  +


Цитата(volvo @ 15.09.2006 3:35) *

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

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

Сообщение отредактировано: knight -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 21.11.2017 16:49
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"