Форум: "Потрепаться";
Текущий архив: 2003.08.18;
Скачать: [xml.tar.bz2];

Вниз

Обращение к коллективному разуму. :о)) нужен алгоритм.   Найти похожие ветки 

← →
sniknik   (2003-07-31 17:37) [0]

Задача такая,
нужны все варианты чисел составляющих в сумме какоето число.
Числа из которых составляется число (значения) и само число задаются и могут быть любыми. (в разумных пределах :о))
Примерный порядок - число = 100-150, количество составляющих около 20-и, значения составляющих положительные и все меньше числа.

Например задано число 22, составляющие из значений 10, 5, 2
варианты
"10 10 2"
"10 5 5 2"
"5 5 5 5 2"
.... и т.д. до
"2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2"
Варианты должны быть уникальными по значениям а не по порядку появления значений т.е. если есть "10 5 5 2" то "5 5 10 2" или "5 10 5 2" уже не нужны.

Есть какое нибудь, желательно математическое/оптимальное решение/идеи?

---

← →
Юрий Зотов   (2003-07-31 19:09) [1]

Пусть число равно M, кол-во слагаемых - N, а сами слагаемые - Xi (где i = 1..N).

Имеем уравнение:
A1*X1 + A2*X2 + ... + AN*XN = M
c N неизвестными A1..AN, причем для каждого Ai существует ограничение: 0 <= Ai <= (M div Xi). Кроме того, известно, что все числа в задаче - целые и положительные.

Из одного уравнения можно получить только одно неизвестное (а с учетом требования его целочисленности - и то не всегда). Значит, остальными надо задаться. Отсюда и решение перебором.

Сортируем Xi по убыванию(чтобы избежать повторов и оптимизировать алгоритм по скорости). Пишем N-1 вложенных циклов FOR. В каждом цикле счетчик Ai пробегает от 0 до (M div Xi). В теле самого внутреннего цикла рассчитываем AN. Если оно целое - то решение найдено, складываем его в коробочку и гоним циклы дальше. Если не целое - просто гоним циклы дальше.

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

---

← →
nikkie   (2003-07-31 19:17) [2]

>Юрий Зотов
>Чтобы впустую не гонять счет, желательно проверять выход текущей суммы за пределы M
для этого достаточно крутить цикл не до M div Xi, а до (M - сумма пред.слагаемых) div Xi.

>Пишем N-1 вложенных циклов FOR.
если число N априорно неизвестно, то не получится. проще всего для этого написать рекурсию.

---

← →
Иван Шихалев   (2003-07-31 21:30) [3]

procedure SuperPuper (Prefix : string = ""; X : integer);
var
first : integer;
begin
case X of
1 : WriteLn (Prefix + "1")
2 : begin
WriteLn (Prefix + "1+1");
WriteLn (Prefix + "2")
end
else for first := 1 to X - 2 do
( Prefix + "+" + IntToStr (first) procedure SuperPuper (Prefix : string = ""; X : integer);
var
first : integer;
begin
case X of
1 : WriteLn (Prefix + "1")
2 : begin
WriteLn (Prefix + "1+1");
WriteLn (Prefix + "2")
end
else for first := 1 to X - 2 do
SuperPuper (Prefix + "+" + IntToStr (first), X - fisrt);
end
end;

---

← →
Иван Шихалев   (2003-07-31 21:33) [4]

> ( Prefix + "+" + IntToStr (first)
> SuperPuper (Prefix + "+" + IntToStr (first),
> X - fisrt);
>


Пропустил немного - если Prefix = "", то и "+" не надо.

---

← →
Иван Шихалев   (2003-07-31 21:34) [5]

Совсем заврался:

Prefix + IntToStr (first) + "+"

---

← →
Aldor   (2003-07-31 23:12) [6]

2 Иван Шихалев ©

2 sniknik
Это задача определения количества способов выдачи определенной суммы денег при заданных достоинствах? :)


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

2) Ваш алгороитм делает очень много лишних операций: он считает все варианты, в том числе и одинаковые. Это требует n^n операций. При n равном 100-150, невыполнимо.
Решение в том, чтобы добавлять "монеты", начиная с наибольшего достоинства до наименьшего с тем условием, что после добавления монеты определенногр достоинства, монеты с бОльшим достоинством добавлены быть не могут.
Это обеспечит проработку всех вариантов без лищних операций.


N - заданное число
k - количество достоинств (монет)
A[0..k - 1] - массив достоинств. Предварительно отсортированный(!)

procedure Solve(OutStr: string; N: Integer; Index: Integer)
{Index - индекс текущего максимального достоинства}
var
I: Integer;
begin
if Index = 0 then
ВыдатьРешение: OutStr + последнее дост-во A[0], повторенное N div A[0] раз.
else
for I := Index downto 0 do
if A[I] <= N then
( OutStr, N - A[Index], I) 2 Иван Шихалев ©

2 sniknik
Это задача определения количества способов выдачи определенной суммы денег при заданных достоинствах? :)


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

2) Ваш алгороитм делает очень много лишних операций: он считает все варианты, в том числе и одинаковые. Это требует n^n операций. При n равном 100-150, невыполнимо.
Решение в том, чтобы добавлять "монеты", начиная с наибольшего достоинства до наименьшего с тем условием, что после добавления монеты определенногр достоинства, монеты с бОльшим достоинством добавлены быть не могут.
Это обеспечит проработку всех вариантов без лищних операций.


N - заданное число
k - количество достоинств (монет)
A[0..k - 1] - массив достоинств. Предварительно отсортированный(!)

procedure Solve(OutStr: string; N: Integer; Index: Integer)
{Index - индекс текущего максимального достоинства}
var
I: Integer;
begin
if Index = 0 then
ВыдатьРешение: OutStr + последнее дост-во A[0], повторенное N div A[0] раз.
else
for I := Index downto 0 do
if A[I] <= N then
Solve(OutStr, N - A[Index], I);
end;

Задача решается вызовом Solve(IntToStr(A[k - 1]), n - A[k - 1], k - 1);


И еще: при использовании string тратится очень много памяти, создается огромное множество строк.
Решение: использовать одну глобальную строку как стек, в который перед вызовом Solve добавляется очередное число, а после удаляется из него. При таком решении занимаемая память будет минимальна (но код будем менее читаемым, потому здесь это и не релизовано, хотя все, конечно, субъективно).


---

← →
Aldor   (2003-07-31 23:16) [7]

В догонку: массив достинств должен быть отсортирован по возрастанию

---

← →
Иван Шихалев   (2003-07-31 23:39) [8]

> требует n^n операций.


n! Хотя и это, действительно, слишком много.

---

← →
Юрий Зотов   (2003-07-31 23:53) [9]

> nikkie © (31.07.03 19:17)
> если число N априорно неизвестно, то не получится. проще всего
> для этого написать рекурсию.

Сути не меняет. Я специально говорил именно о циклах, чтобы проще было понять идею.

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

---

← →
VD602   (2003-08-01 00:00) [10]

> n! Хотя и это, действительно, слишком много.

Нет, n^n. Закон роста рекурсии: k^l; k - количество детей от каждой ветки. l - количество уровней рекурсии.

Вы были бы правы, если рассматривались все перестановки чисел от 1 до n. Но здесь не перестановка - числа могут повтроряться.

---

← →
Aldor   (2003-08-01 00:05) [11]

2 VD602

Опередил :)) Но очень хорошо все написал. Считай мои мысли.

---

← →
sniknik   (2003-08-01 00:31) [12]

похоже до меня не дошло ;о)) (нескладывается пока)
> Юрий Зотов © (31.07.03 19:09)
с циклами действительно не то... но я как понял положил рещение в рекурсию (1-й вариант) и поменял, не "набор" значений а "отнимание".

написал так
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
Button2: TButton;
procedure ButtonClick(Sender: TObject);
private
Count: integer;
Ar: array of integer;
procedure CalcVal_1(St: string; Val, Shift: integer); //неудачная попытка вычислений
procedure CalcVal_2(St: string; Val, Shift: integer); //прямой перебор
end;

var
Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.CalcVal_1(St: string; Val, Shift: integer);
var i: integer;
function StOfVal(Val, Count: integer): string;
begin
result:= DupeString(IntToStr(Val) + " ", Count);
end;
begin
if Val < Shift then exit;
if Val Mod Shift = 0 then begin
Memo1.Lines.Add(St+StOfVal(Shift, Val Div Shift));
exit
end;
for i:= 0 to Count-1 do
CalcVal_1(St+StOfVal(Shift, Val Div Shift), Val Mod Shift, Ar[i]);
end;

procedure TForm1.CalcVal_2(St: string; Val, Shift: integer);
var i: integer;
begin
if Val - Shift <= 0 then begin
if Val - Shift = 0 then Memo1.Lines.Add(St);
exit
end;
for i:= 0 to Count-1 do
CalcVal_2(St+" "+IntToStr(Ar[i]), Val - Shift, Ar[i]);
end;

procedure TForm1.ButtonClick(Sender: TObject);
var i: integer;
begin
Count:= 3;
SetLength(Ar, Count);
Ar[0]:= 10;
Ar[1]:= 5;
Ar[2]:= 1;

if TButton(Sender).Name = "Button1" then begin
for i:= 0 to Count-1 do
CalcVal_1(IntToStr(Ar[i])+" ", 20, Ar[i]);
end;

if TButton(Sender).Name = "Button2" then begin
for i:= 0 to Count-1 do
( IntToStr(Ar[i]) похоже до меня не дошло ;о)) (нескладывается пока)
> Юрий Зотов © (31.07.03 19:09)
с циклами действительно не то... но я как понял положил рещение в рекурсию (1-й вариант) и поменял, не "набор" значений а "отнимание".

написал так
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
Button2: TButton;
procedure ButtonClick(Sender: TObject);
private
Count: integer;
Ar: array of integer;
procedure CalcVal_1(St: string; Val, Shift: integer); //неудачная попытка вычислений
procedure CalcVal_2(St: string; Val, Shift: integer); //прямой перебор
end;

var
Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.CalcVal_1(St: string; Val, Shift: integer);
var i: integer;
function StOfVal(Val, Count: integer): string;
begin
result:= DupeString(IntToStr(Val) + " ", Count);
end;
begin
if Val < Shift then exit;
if Val Mod Shift = 0 then begin
Memo1.Lines.Add(St+StOfVal(Shift, Val Div Shift));
exit
end;
for i:= 0 to Count-1 do
CalcVal_1(St+StOfVal(Shift, Val Div Shift), Val Mod Shift, Ar[i]);
end;

procedure TForm1.CalcVal_2(St: string; Val, Shift: integer);
var i: integer;
begin
if Val - Shift <= 0 then begin
if Val - Shift = 0 then Memo1.Lines.Add(St);
exit
end;
for i:= 0 to Count-1 do
CalcVal_2(St+" "+IntToStr(Ar[i]), Val - Shift, Ar[i]);
end;

procedure TForm1.ButtonClick(Sender: TObject);
var i: integer;
begin
Count:= 3;
SetLength(Ar, Count);
Ar[0]:= 10;
Ar[1]:= 5;
Ar[2]:= 1;

if TButton(Sender).Name = "Button1" then begin
for i:= 0 to Count-1 do
CalcVal_1(IntToStr(Ar[i])+" ", 20, Ar[i]);
end;

if TButton(Sender).Name = "Button2" then begin
for i:= 0 to Count-1 do
CalcVal_2(IntToStr(Ar[i]), 20, Ar[i]);
end;
end;

в первом случае не все значения, на примере 20 и [10, 5, 1]
получаются
10 10 10
5 5 5 5 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
нехватает
10 10 5 5
и тд

во втором лишние (и долго, на реальных цифрах не дождался конца "расчетов")
10 10
10 5 5
10 5 1 1 1 1 1
10 1 5 1 1 1 1 //лишнее
10 1 1 5 1 1 1
10 1 1 1 5 1 1
10 1 1 1 1 5 1
10 1 1 1 1 1 5
10 1 1 1 1 1 1 1 1 1 1
......

сегодня уже думать больше не получается ;о)), отложу до завтра (хотя чуствую осталось чуть чуть :о)))).

во понаписали! видел только 2 поста до того как сам начал, а тут уже вон сколько. но звиняйте все одно до завтра, почитаю остальные завтра и обдумаю. спасибо.

---

← →
Aldor   (2003-08-01 00:58) [13]

> в первом случае не все значения,

И правильно, потому что решение неверно:

CalcVal_1(St+StOfVal(Shift, Val Div Shift), Val Mod Shift, Ar[i]);

При таком решении 10 10 5 5 и не должно быть. Потому что вы требуете максимально заполнить наибольшим числом, а по условию надо отработать все варианты.

> не дождался конца "расчетов"

см. VD602 (01.08.03 00:00).

З.Ы.

if Val < Shift then exit;


Лучше проверять это условие в цикле, ДО входа в процедуру.

---

← →
sniknik   (2003-08-01 08:51) [14]

Иван Шихалев © (31.07.03 21:30)
тот же самый перебор?

Aldor © (31.07.03 23:12)
не, это задача (начало) нахождения оптимального расположения товара на полках. одно из требований показать все возможные варианты.

насколько понимаю и у тебя перебор, причем "if Index = 0 then " проверять условие выхода по индексу не совсем правильно.

Aldor © (01.08.03 00:58)
да, решение не верное. но если передавать внутрь не остаток от деления а -очередную составляющую (для получения всех вариантов) то все вырождается в очередной вариант перебора.
насчет кода, это ерунда нужна не программа нужна логика, лиш бы попонятней. красоту после можно навести (время вызова процедуры пока не важно, время вобще пока не учитывается лиш бы оно было приемлемым (не больше суток к примеру)).

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

---

← →
Aldor   (2003-08-01 13:10) [15]

> не, это задача (начало) нахождения оптимального расположения товара на полках

Вот, это хорошо - отличный пример практического применения теоретической задачи алгоритмики.

> "if Index = 0 then " проверять условие выхода по индексу не совсем правильно.

Это перебор, но отличие в том, что он СОКРАЩЕННЫЙ, не обрабатываются лишние варианты. Вот вы сказали "либо какой нибудь изящьный изворот". Здесь он и есть: если после добавления какого-то числа "запретить" добавление чисел, больших этому, то лишние варианты не обрабатываются и скорость значительно сокращается. Для этого, кстати, и нужно предварительно отсортировывать массив. Если не верите, воьзмите хотя бы монетки или те же самые товары и посмотрите, что получится. Аргумент Index как раз и обеспечивает такой "запрет".

Вы правильно сказали, что " проверять условие выхода по индексу не совсем правильно."
Действительно, не совсем. Еще может быть случай, когда товары\монетки просто закончились. Поэтому строку if-then заменяем на:


if index = 0 or N = 0 then
ВыдатьРешение: OutStr + последнее дост-во A[0], повторенное N div A[0] раз.
else
( index = 0) > не, это задача (начало) нахождения оптимального расположения товара на полках

Вот, это хорошо - отличный пример практического применения теоретической задачи алгоритмики.

> "if Index = 0 then " проверять условие выхода по индексу не совсем правильно.

Это перебор, но отличие в том, что он СОКРАЩЕННЫЙ, не обрабатываются лишние варианты. Вот вы сказали "либо какой нибудь изящьный изворот". Здесь он и есть: если после добавления какого-то числа "запретить" добавление чисел, больших этому, то лишние варианты не обрабатываются и скорость значительно сокращается. Для этого, кстати, и нужно предварительно отсортировывать массив. Если не верите, воьзмите хотя бы монетки или те же самые товары и посмотрите, что получится. Аргумент Index как раз и обеспечивает такой "запрет".

Вы правильно сказали, что " проверять условие выхода по индексу не совсем правильно."
Действительно, не совсем. Еще может быть случай, когда товары\монетки просто закончились. Поэтому строку if-then заменяем на:


if index = 0 or N = 0 then
ВыдатьРешение: OutStr + последнее дост-во A[0], повторенное N div A[0] раз.
else
// ...



Вот так и получается, что когда доходим до минимального составляющего числа (index = 0), других вариантов, кроме как вставить дальше только это число нет (вспомните про "запрет"), поэтому и выдаем всю строку.

---

← →
Aldor   (2003-08-01 13:16) [16]

Проше прощения за описку:
"скорость значительно сокращается"
читать как
"время значительно сокращается"

Разница существенная :)

---

← →
sniknik   (2003-08-01 14:03) [17]

Aldor © (01.08.03 13:10)
> Это перебор, но отличие в том, что он СОКРАЩЕННЫЙ,
работает быстрее точно, но результат неправильный вот что делаю (ничего не переврал?)

проверка на том же число 20 и варианты [10, 5, 1]
procedure TForm1.Solve(OutStr: string; N: Integer; Index: Integer);
{N - заданное число
k - количество достоинств (монет)
A[0..k - 1] - массив достоинств. Предварительно отсортированный(!)}
{Index - индекс текущего максимального достоинства}
var
I: Integer;
function StOfVal(Val, Count: integer): string;
begin
result:= DupeString(IntToStr(Val) + " ", Count);
end;
begin
if (index = 0) or (N = 0) then
Memo1.Lines.Add(OutStr+StOfVal(Ar[0], N div Ar[0]))
//ВыдатьРешение: OutStr + последнее дост-во A[0], повторенное N div A[0] раз.
else
for I := Index downto 0 do
if Ar[I] <= N then
Solve(OutStr, N - Ar[Index], I);
end;

вызов

Count:= 3;
SetLength(Ar, Count);
Ar[0]:= 1;
Ar[1]:= 5;
Ar[2]:= 10;
.....
if TButton(Sender).Name = "Button3" then begin
//Задача решается вызовом Solve(IntToStr(A[k - 1]), n - A[k - 1], k - 1);
( IntToStr(Ar[Count - 1]) Aldor © (01.08.03 13:10)
> Это перебор, но отличие в том, что он СОКРАЩЕННЫЙ,
работает быстрее точно, но результат неправильный вот что делаю (ничего не переврал?)

проверка на том же число 20 и варианты [10, 5, 1]
procedure TForm1.Solve(OutStr: string; N: Integer; Index: Integer);
{N - заданное число
k - количество достоинств (монет)
A[0..k - 1] - массив достоинств. Предварительно отсортированный(!)}
{Index - индекс текущего максимального достоинства}
var
I: Integer;
function StOfVal(Val, Count: integer): string;
begin
result:= DupeString(IntToStr(Val) + " ", Count);
end;
begin
if (index = 0) or (N = 0) then
Memo1.Lines.Add(OutStr+StOfVal(Ar[0], N div Ar[0]))
//ВыдатьРешение: OutStr + последнее дост-во A[0], повторенное N div A[0] раз.
else
for I := Index downto 0 do
if Ar[I] <= N then
Solve(OutStr, N - Ar[Index], I);
end;

вызов

Count:= 3;
SetLength(Ar, Count);
Ar[0]:= 1;
Ar[1]:= 5;
Ar[2]:= 10;
.....
if TButton(Sender).Name = "Button3" then begin
//Задача решается вызовом Solve(IntToStr(A[k - 1]), n - A[k - 1], k - 1);
Solve(IntToStr(Ar[Count - 1])+" ", 20 - Ar[Count - 1], Count - 1);
end;

результат выдает
10
10
10
чето тут не то, условие или > ВыдатьРешение: OutStr + последнее дост-во A[ 0], повторенное N div A[ 0] раз.?
не понимаю логику, как у тебя получается. :(

а вот насчет "запрета" чисел участвововших в расчетах обещаю подумать ;о). возможно это оно и есть. (решение) во всяком случае значительное сокращение времени будет (но вот попадут ли все решения в список, в таком варианте?).

---

← →
sniknik   (2003-08-01 14:23) [18]

лутше гораздо лутше(быстрее), с отсечением. но повторы всетаки встречаются.
всегото изменений (в переборе)
procedure TForm1.CalcVal_3(St: string; Val, Shift, IndexMax: integer);
var i: integer;
begin
if Val - Shift <= 0 then begin
if Val - Shift = 0 then Memo1.Lines.Add(St);
exit
end;
for i:= IndexMax to Count-1 do
CalcVal_3(St+" "+IntToStr(Ar[i]), Val - Shift, Ar[i], i);
end;

а уже можно дождатся конца "вычислений"

вызов
if TButton(Sender).Name = "Button4" then begin
for i:= 0 to Count-1 do
( IntToStr(Ar[i]) лутше гораздо лутше(быстрее), с отсечением. но повторы всетаки встречаются.
всегото изменений (в переборе)
procedure TForm1.CalcVal_3(St: string; Val, Shift, IndexMax: integer);
var i: integer;
begin
if Val - Shift <= 0 then begin
if Val - Shift = 0 then Memo1.Lines.Add(St);
exit
end;
for i:= IndexMax to Count-1 do
CalcVal_3(St+" "+IntToStr(Ar[i]), Val - Shift, Ar[i], i);
end;

а уже можно дождатся конца "вычислений"

вызов
if TButton(Sender).Name = "Button4" then begin
for i:= 0 to Count-1 do
CalcVal_3(IntToStr(Ar[i]), 20, Ar[i], 0);
end;

результат, с повторами :о(, пропусков не заметил (вроде нет).
10 10
10 5 5
10 5 1 1 1 1 1
10 1 1 1 1 1 1 1 1 1 1
5 10 5
5 10 1 1 1 1 1
5 5 5 5
5 5 5 1 1 1 1 1
5 5 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 10 5 1 1 1 1
1 10 1 1 1 1 1 1 1 1 1
1 5 5 5 1 1 1 1
1 5 5 1 1 1 1 1 1 1 1 1
1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

---

← →
Юрий Зотов   (2003-08-01 14:36) [19]

> sniknik © (01.08.03 14:23)

Попробуйте предварительно отсортировать набор слагаемых по убыванию. Не исчезнут ли повторы?

---

← →
sniknik   (2003-08-01 14:52) [20]

Юрий Зотов © (01.08.03 14:36)
нет просто переворачиваются получаемые строки
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5
1 1 1 1 1 1 1 1 1 1 5 5
1 1 1 1 1 1 1 1 1 1 10
1 1 1 1 1 5 5 5
1 1 1 1 1 5 10
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 5
5 1 1 1 1 1 5 5
5 1 1 1 1 1 10
5 5 5 5
5 5 10
10 1 1 1 1 1 1 1 1 1 1
10 1 1 1 1 1 5
10 5 5
10 10

---

← →
sniknik   (2003-08-01 15:00) [21]

ура!!! нашел глюк. получилось вполне приемлемо. именно с отсечением.
а глюк был в вызове в последнем варианте
вызов
if TButton(Sender).Name = "Button4" then begin
for i:= 0 to Count-1 do
( IntToStr(Ar[i]) ура!!! нашел глюк. получилось вполне приемлемо. именно с отсечением.
а глюк был в вызове в последнем варианте
вызов
if TButton(Sender).Name = "Button4" then begin
for i:= 0 to Count-1 do
CalcVal_3(IntToStr(Ar[i]), 20, Ar[i], {0 old} i{Ok} );
end;
спасибо участникам.

---

← →
Aldor   (2003-08-01 20:33) [22]

2 sniknik ©

Есть ошибки. Писал ночью, недоглядел. Все просто:
Соответствующую строку исправьте на:
Solve(OutStr + " " + IntToStr(Ar[I]) + " ", N - Ar[ I], I);

( "", 20, Count - 1) 2 sniknik ©

Есть ошибки. Писал ночью, недоглядел. Все просто:
Соответствующую строку исправьте на:
Solve(OutStr + " " + IntToStr(Ar[I]) + " ", N - Ar[ I], I);

B вызов должен быть:
Solve( "", 20, Count - 1);

Так работает.
Ради интреса попробуйте, должно получиться быстрее.

---

← →
Aldor   (2003-08-01 20:37) [23]

Я сейчас ее потестировал: при N = 100, Count = 10 работает за 0.1с Без вывода, он занимает бОльшую часть времени.

---

← →
sniknik   (2003-08-02 15:14) [24]

> Так работает.
> Ради интреса попробуйте, должно получиться быстрее.
попробовал, работает но не быстрее, последний вариант
sniknik © (01.08.03 14:23)
с исправленым глюком
sniknik © (01.08.03 15:00)
всетаки быстрей (сравнивал)

и у тебя еще одного условия не хватает
в процедуре
if ((index = 0) or (N = 0)) and (N mod Ar2[0] = 0) then ...
без него лишнии строки, с сумой не равные числу а немного меньше (если ряд начинается не с 1 например и не с двойки и число четное а с 4 к примеру)

---

← →
Aldor   (2003-08-02 22:30) [25]

> всетаки быстрей (сравнивал)
really strange, вариантов обрабатывается меньше. Ну что ж, пользуйтесь тем что есть, если найде научное объянение этому, сообщу.

---

← →
sniknik   (2003-08-02 22:52) [26]

чего его искать скорее всего вот оно
function StOfVal(Val, Count: integer): string;
begin
result:= DupeString(IntToStr(Val) + " ", Count);
end;
отрабатывает медленней чем просто +, а вызывается всегда даже для 1 значения (в конце). и наверное не настолько уж менше вариантов (некритично, не влияет на время).

---

Страницы: 1 вся ветка

Форум: "Потрепаться";
Текущий архив: 2003.08.18;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.56 MB
Время: 0.003 c