novashdima
25-04-2013, 17:50
Всем привет, понадобилось написать в программе пару алгоритмов, реализовал, часть функций за ленью взял из инета и переписал, часть сам написал. В общем все было отлично, все проблемы поборены, дополнительные условия поставлены и тут я решил изменить входные данные (во время проектирования сколько раз вы меняете входные данные? я раз 5, при которых я знаю конечный результат). В общем для эксперимента удалил 5 символов во входной строке (пересчет данных происходит при изменении, то есть за это время произошло 5 просчетов) и после удаления этого самого 5 символа вылетел Stack Overflow, пол минуты на просмотр стека вызовов и контрольных комментов кода для 100% уверенности. Как я и думал проблема с рекурсией, почему то при пересчетах стек остается забит старыми данными. Пробовал чистить и переменные и уничтожать объекты с очисткой памяти и от объекта и просто неюзаемой памяти, но не помогает, чему я не удивлен. Привожу рекурсивную функцию:
procedure TForm1.SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer);
var
dS, S:real; { Среднее значение массива }
i, m:integer; { m - номер средней буквы в последовательности, S - сумма чисел, левой ветки }
c_branch:string; { текущая история поворотов по веткам }
begin
{ проверка если это вход нулевой то очистить историю }
if (c_branch<>' ') then c_branch := full_branch + branch
else begin
c_branch := '';
ds := 0;
S := 0;
i := 0;
m := 0;
end;
{ Критерий выхода: если позиции символов совпали, то это конец }
if (start_pos = end_pos) then
begin
StringGrid2.Cells[2, start_pos] := c_branch;
exit;
end;
{ Подсчет среднего значения частоты в последовательности }
dS := 0;
for i:=start_pos to end_pos do
dS:= dS + StrToFloat(StringGrid2.Cells[1,i]);
dS := dS/2;
{ Тут какой угодно можно цикл for, while, repeat поиск середины }
S := 0;
i := start_pos;
m := i;
while ((S+StrToFloat(StringGrid2.Cells[1, i])<dS) and (i<end_pos)) do
begin
S := S + StrToFloat(StringGrid2.Cells[1, i]);
inc(i); inc(m);
end;
{ Рекурсия левая ветка дерева }
SearchTree('1', c_branch, start_pos, m);
{ Правая ветка дерева }
SearchTree('0', c_branch, m+1, end_pos);
end;
//вызов самой функции:
SearchTree(' ',' ', 1, Length(str));
procedure TForm1.SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer);
var
dS, S:real; { Среднее значение массива }
i, m:integer; { m - номер средней буквы в последовательности, S - сумма чисел, левой ветки }
c_branch:string; { текущая история поворотов по веткам }
begin
{ проверка если это вход нулевой то очистить историю }
if (c_branch<>' ') then c_branch := full_branch + branch
else begin
c_branch := '';
ds := 0;
S := 0;
i := 0;
m := 0;
end;
{ Критерий выхода: если позиции символов совпали, то это конец }
if (start_pos = end_pos) then
begin
StringGrid2.Cells[2, start_pos] := c_branch;
exit;
end;
{ Подсчет среднего значения частоты в последовательности }
dS := 0;
for i:=start_pos to end_pos do
dS:= dS + StrToFloat(StringGrid2.Cells[1,i]);
dS := dS/2;
{ Тут какой угодно можно цикл for, while, repeat поиск середины }
S := 0;
i := start_pos;
m := i;
while ((S+StrToFloat(StringGrid2.Cells[1, i])<dS) and (i<end_pos)) do
begin
S := S + StrToFloat(StringGrid2.Cells[1, i]);
inc(i); inc(m);
end;
{ Рекурсия левая ветка дерева }
SearchTree('1', c_branch, start_pos, m);
{ Правая ветка дерева }
SearchTree('0', c_branch, m+1, end_pos);
end;
//вызов самой функции:
SearchTree(' ',' ', 1, Length(str));