Информатика и технология программирования

       

Результат функции рекурсивного поиска


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

Прежде всего, рекурсивная функция будет производить полный перебор возможных вариантов, без завершения по первому попавшемуся.


xxx step(char *lw)
{ ...
for (...)
{ ...
if (step(pw))
{}
}
return ...}

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


char *s(...)
{ char *p;
p=s(...); // вызов char *s(){...}


if (...) p=s(...); // вызов char *s(){...}


if (...) p=s(...); // вызов char *s(){...}


}

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




char *step(char *lw ) // результат - строка с цепочкой слов

{ ... // параметр - слово, с которого

// начинается цепочка

for (n=0; w[n]!=NULL;n++) //просмотр оставшихся слов

{
char *pw,*pp; int l; // слово уже выбрано -

if (*w[n]==0) continue; // пропустить

if ((l=TEST(lw,w[n]))!=-1 )
// можно присоединить к текущему

{
pw=w[n]; //убрать очередное слово из списка

w[n]=""; //рекурсивный вызов для нового

if ((pp=step(pw))!=NULL)
{ // !=NULL - цепочка выcтроена

s=new char[l+strlen(pp)];
strcpy(s,lw); // присоединить текущее слово

strcpy(s+l,pp); // к началу и использовать как

delete pp; // новый результат

}
w[n]=pw;
}
} ...}

Естественно, что из множества полученных результатов выбирается единственный, который " ретранслируется наверх" . В нашем случае - из полученных цепочек выбирается минимальная по длине - что делается классическим циклом поиска минимума

smin=NULL;
for (n=0; w[n]!=NULL;n++)
{ ...if ((pp=step(pw))!=NULL)
{
s= ... //сформировать очередной результат

delete pp; //запоминание самой короткой строки

if (smin==NULL) smin=s; else
if (strlen(smin)&#62strlen(s))
{ delete smin; smin=s; }
}
}
return smin;



Окончательный вариант программы приведен ниже. Функция проверки " перекрытия " слов возвращает количество " неперекрытых" букв в первом слове, 0 - если первое слово - пустая строка, либо -1, если слова не перекрываются





//------------------------------------------------------bk54-04.cpp

&#35include &#60iostream.h&#62
&#35include &#60string.h&#62
char *w[]={"bba","abb","ba",NULL};



int TEST(char *s, char *r)
{
int n,k;
k=n=strlen(s);
if (n==0) return 0;
for (;*s!=0 &#38&#38 n&#62 0; s++,n--)
if (strncmp(s,r,n)==0)
return k-n;
return -1;
}

char *step(char *lw)
{ int n; char *s,*smin;
for (n=0; w[n]!=NULL;n++)
if (*w[n]!=0) break;
if (w[n]==NULL)
{
s=new char[strlen(lw)+1];
strcpy(s,lw);
return s;
}
smin=NULL;
for (n=0; w[n]!=NULL;n++)


{
char *pw,*pp; int l;
if (*w[n]==0) continue;
if ((l=TEST(lw,w[n]))!=-1)
{
pw=w[n];
w[n]="";
if ((pp=step(pw))!=NULL)
{
s=new char[l+strlen(pp)];
strcpy(s,lw);
str cat(s +l,pp);
delete pp;
if (smin==NULL) smin=s; else
if (strlen(smin)&#62strlen(s))
{ delete smin; smin=s; }
}
w[n]=pw;
}
}
return smin;
}

void main() { cout &#60&#60 step("");}

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



//------------------------------------------------------bk54-05.cpp

&#35include &#60iostream.h&#62
&#35include &#60string.h&#62
char *w[]={"bba","abb","ba",NULL};



int TEST(char *s, char *r)
{
int n,k;
k=n=strlen(s);
if (n==0) return 0;
for (;*s!=0 &#38&#38 n&#62 0; s++,n--)
if (strncmp(s,r,n)==0) return k-n;
return -1;
}

&#35define SZ 80
struct string
{
int null; // Признак строка пустая

char str[SZ]; // Строка ограниченной длины

};
string step(char *lw) // Функция возвращает структуру как результат

{ int n;
string s,smin; // Локальные переменные - структуры

for (n=0; w[n]!=NULL;n++)
if (*w[n]!=0) break;
if (w[n]==NULL) // Последняя строка

{ s.null=0; strcpy(s .str,lw); return s; }
smin.null =1; // Признак строка еще пока пустая

for (n=0; w[n]!=NULL;n++)
{
char *pw; int l;
string pp; // Результат рекурсивного вызова

if (*w[n]==0) continue;
if ((l=TEST(lw,w[n]))!=-1)
{
pw=w[n];
w[n]="";
pp=step(pw) ; // Рекурсивная функция возвращает

if (!pp.null) // структурированную переменную

{ // За распределением памяти под

s.null=0; // структурированные переменные

strcpy(s .str,lw); // не следим

strcat(s.str,pp .str);
if (smin. null) smin=s; else
if (strlen(smin .str)&#62strlen(s .str))
smin=s; // Прямое присваивание структур

}
w[n]=pw;
}
}
return smin;
}
void main() { cout &#60&#60 step("") .str;}


Содержание раздела