Алгоритм Фано-Шеннона - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Алгоритм Фано-Шеннона (http://forum.oszone.net/showthread.php?t=259403)

Алгоритм Фано-Шеннона

Всем привет, понадобилось написать в программе пару алгоритмов, реализовал, часть функций за ленью взял из инета и переписал, часть сам написал. В общем все было отлично, все проблемы поборены, дополнительные условия поставлены и тут я решил изменить входные данные (во время проектирования сколько раз вы меняете входные данные? я раз 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));

Цитата:

Цитата novashdima

Вот этого фокуса я не понял.

Код:

var

 c_branch:string; { текущая история поворотов по веткам ОЙ ЛИ?!}

begin

 { проверка если это вход нулевой то очистить историю }

 if (c_branch<>' ') then c_branch := full_branch + branch

 else begin  c_branch := ''; ...  end;

Внутри процедуры мы вводим локальную переменную. Т.е. выделяем под нее кусок памяти.
Что в данный момент находится в регистрах памяти неизвестно. Сходу делать предположение, что это какая-то там входная правильная(!) информация - грубейшая ошибка. У вас четко определено, что подается функции в качестве аргументов :
branch:char; full_branch:string; start_pos:integer; end_pos:integer
Не больше, не меньше. Делать проверку не инициализированной переменной, а потом на основе этого осуществлять работу программы? Бррр. Уберите это немедленно!
Собственно дальше можно не смотреть.
Переписывайте нормально алгоритм и приходите вновь.
То, что программа корректно отработала 5 известных случаев -- чистое везение.

Цитата:

Цитата lxa85

Внутри процедуры мы вводим локальную переменную. Т.е. выделяем под нее кусок памяти.
Что в данный момент находится в регистрах памяти неизвестно. Сходу делать предположение, что это какая-то там входная правильная(!) информация - грубейшая ошибка. У вас четко определено, что подается функции в качестве аргументов :
branch:char; full_branch:string; start_pos:integer; end_pos:integer
Не больше, не меньше. Делать проверку не инициализированной переменной, а потом на основе этого осуществлять работу программы? Бррр. Уберите это немедленно!
Собственно дальше можно не смотреть.
Переписывайте нормально алгоритм и приходите вновь.
То, что программа корректно отработала 5 известных случаев -- чистое везение. »

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

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

Цитата:

Цитата novashdima

как реализовать получше (с рекурсией у меня всегда проблемы с составлением были) »

Своей головой и без рекурсии. Т.е. самая короткая дорога - та, которую знаешь. Если рекурсия дается с трудом, пиши без нее. Машины последователь и не обладают встроенной возможностью работы рекурсией (это из области вычислительных машин).