Рекурсивни алгоритми
1. Понятие
2. Пряка и непряка рекурсия
3. Дълбочина на рекурсията
4. Приложение на рекурсията
Пресмятане на n!
Числата на Фибуначи
Намиране на двоично представяне на цяло десетично число без знак.
Извеждане на числова пирамида.
Изчертаване на Хилбертови криви.
Алгоритми с
отстъпване (с връщане назад)
1. Понятие
Казва се, че един обект е рекурсивен, ако той частично се съдържа в себе си или е дефиниран чрез себе си.
Рекурсия
се среща не само в математиката, но и в обикновения живот. Пример може да се
даде с руската кукла, наречена “матръошка”, която съдържа в себе си същите
кукли, но с по-малки размери. Рекурсията е особено мощно средство в
математическите дефиниции. Няколко познати примера са тези за естествените
числа, дървовиднете структури и някои функции.
1. Естествени числа:
Ø
1 е естествено число;
Ø
приемникът на естествено число
е естествено число.
2. Дървовидни структури:
Ø
О е дърво (наречено празно
дърво);
Ø
ако t1 и t2 са дървета, то 
е дърво (начертано
обратно);
3.
Функция факториал n! (за неотрицателни цели
числа):
Ø
0! = 1;
Ø
ако n>0, то n! =
n.(n-1)!
Силата
на рекурсията очевидно се състои във възможността за дефиниране на безкрайно
множество от обекти чрез краен оператор. По същия начин чрез крайна рекурсивна
програма може да се опише безкраен брой пресмятания дори ако тази програма не
съдържа явни цикли. Рекурсивните алгоритми обаче са особено подходящи, когато
проблемът, който ще се решава, или функцията, която ще се пресмята, или
структурата от данни, коята ще се обработва, са вече дефинирани чрез рекурсия.
Изобщо една рекурсивна програма може да се изрази като група r от основни оператори Si (несъдържащи P) и самата P:
P º r[ Si , P]
2. Пряка и непряка рекурсия
Необходимо
и достатъчно средство за рекурсивно изразяване на програми е процедурата или подпрограмата, защото тя дава възможност да се приписва име на
оператор, чрез което той да може да бъда повикван. Ако една процедура P1
съдържа явно обръщане към себе си, се казва, че тя е пряко рекурсивна; ако
P1 съдържа обръщане към друга процедура Р2, която от своя страна съдържа (пряко
или непряко) обръщане към P1, казва се, че P1 е непряко рекурсивна. В този случай използването на рекурсия може
и да не е съвсем очевидно от текста на програмата.
P1 º r[ Si , P1] - пряка рекурсия
P1 º r[ Si , P2] - непряка рекурсия
P2 º r[ Si , P1]
Обикновено с процедурата
се свързва множество от локални обекти, като променливи, константи, типове и
процедури, които са дефинирани локално в тази процедура и не съществуват извън
процедурата. Всеки път, когато такава процедура се активира рекурсивно, се
създава ново множество от локални променливи. Макар че те имат същите имена,
както техните съответни елементи в множеството, локално за предишното копие на
процедурата, стойностите им са различни и всички недоразумения, които могат да
въникнат вследствие еднаквите имена, се избягват чрез правилата за област на
действие на идентификаторите; идентификаторите винаги се отнасят за последното
създадено множество от променливи. Същите правила важат и за параметрите на
процедурата, които по дефиниция са валидни само в нея.
3. Дълбочина на рекурсията
Подобно
на циклите рекурсивните процедури създават условия за съществуване на
незавършващи пресмятания, ето защо е необходимо да се разгледа проблемът за край на изпълнението. Очевидно едно
основно изискване е рекурсивното извикване на процедурата P да се подчинява на
условие В, което в даден момент да престава да бъде удовлетворено. Следователно
схемата за рекурсивни алгоритми може да се изрази по-точно така:
P º r[ Si , if B then P]
Основният
начин да се покаже, че един цикъл е завършен, е да се дефинира функция f(x) (х е множество от променливите в програмата) по
такъв начин, че f(x) £ 0 да
бъде условие за край на изпълнението е да се докаже, че f(x) намалява при всяко изпълнение на цикъла. По същия начин
може да се покаже, че една рекурсивна програма не е безкрайна, т.
е. че тя ще завърши в някакъв момент, като се покаже, че f(x) намалява при всяко изпълнение на P. Особено
очевиден начин да се осигури завършване на програмата е с нея да се свърже
параметър n и при всяко изпълнение на Pn да се
намалява с 1. Заменянето на условието B с n > 0 гарантира края на изпълнението. Това може да се
изрази чрез следната програмна схема:
P(n) º r [Si , if n > 0 then P(n-1)]
В
практическите приложения е задължително да се покаже, че дълбочината на
рекурсията е не само крайна, но и достатъчно малка. Причината за това е, че
при всяко рекурсивно активиране на процедурата Р е необходимо известно
количество памет за нейните променливи. Освен тези локални променливи трябва да
се регистрира и текущото състояние на пресмятанията, за да може да стане
връщане към тях, когато завърши текущото активиране на Р и се възобнови
старото.
4. Приложение на рекурсията
Рекурсивните алгоритми са особено подходящи, когато съответният проблем или
данни, които ще се обработват, са дефинирани рекурсивно. Това обаче не означава, че такива рекурсивни дефиниции гарантират превъзходство
на рекурсивния алгоритъм над всички други начини за решаване на проблема.
Пример:
Пресмятане
на n! - както вече казахме, по дефиниция
0!
= 1 и
n! = n*(n-1)!, където n е цяло положително
число. С оглед капацитета на
компютърната памет ще сложим още едно, допълнително ограничение n<34.
И така рекурсивната
функция изглежда по следния начин:
|
|
Извикващата
функция може да има вида:
void main (void)
{
int n;
do{ cout<<"n =" ;
cin>> n;
}while (n<0 || n>34);
cout<<n<<"!
=" << fact (n);
}
|
|
|
1
|
int fact (int n)
|
|
2
|
{
|
|
3
|
int nf;
|
|
4
|
if (n
= = 0) return 1;
|
|
5
|
nf =
n*fact (n-1);
|
|
6
|
return nf ;
|
|
7
|
}
|
|
|
|
Дълбочината
на рекурсията се определя от променливата n и намалява стойността си с
еденица при всяко ново извикване. Когато n получи стойност 0 се слага
край на рекурсивното извикване и започва процес на излизане от рекурсията.
Как
изглежда изпълнението на тази функция? Знаете, че в C++ всяка извикана функция
получава място в стека и след приключването и, това място се освобождава. Да предположим,
че за n е била въведена стойност 3. При първото извикване, функцията fact
получава място в стека за локалните си променливи n и nf. В n се записва 3. На трети ред от функцията се прави проверка за n = 0 (3 = 0). Отговорът е "НЕ" и се преминава
към изпълнение на четвърти ред от функцията, където на nf се присвоява
стойността 3*(върнатата стойност от изпълнението на функцията fact с
аргумента (n-1)). Следователно извършва се рекурсивно извикване на функцията без да е
завършило текущото и изпълнение. При второто извикване на fact, отново
се заделя място в стека за променливите n и nf, като n получава стойност 2, а nf = 2*(върнатата стойност от рекурсивното изпълнение на fact с аргумент 1). Прави се проверка за n=0 и следва ново извикване на функцията fact, с аргумент 1. Отново
се заделя място в стека за променливите n=1 и nf=1*(върнатата стойност от изпълнението на функцията
fact с аргумент 0). Прави се проверка за n=0 и следва ново извикване на
функцията fact, с аргумент 0. Отново се заделя място в стека n=0 и nf. При
това извикване на трети ред от функцията проверката (n = = 0) дава положителен резултат и се изпълнява оператора return 1, т.е.
освобождава се заетата памет за последното извикване на функцията и в
предходното извикване (третото) на четвърти ред се връща стойност 1. nf = 1*1 => nf = 1. Изпълнява се пети
ред от функцията и в предходното (второ) извикване на четвърти ред се връща
стойност 1 в израза nf =2*1. Заетата памет за третото
извикване на функцията fact се освобождава. Изпълнява се пети ред и в
предходното (първо) извикване се връща стойност 2 в израза nf =3*2, n=6.
Заетата памет за второто извикване на функцията fact се освобождава. Изпълнява се пети ред и функцията връща в главната
програма стойност 6, което е и стойността на 3!. Заетата
памет за първото извикване на функцията fact се освобождава.
GРекурсията е много близка до итерацията в своята логика и много рекурсивни
алгоритми могат да се решат чрез итерация.
Пример
Изчисляване на n! чрез итерация.
void main (void)
{
int i, n, nf ;
cout<<"n =" ;
cin>> n;
for ( nf=1 , i=n ; i>0 ; i--)
nf
= nf * i ;
cout<<n<<"!
=" << nf;
}
Има случаи, при които задачата е дефинирана рекурсивно,
но се решава по-елегантно с итерация. Пример за това са числата
на Фибуначи, които се дефинират рекурсивно:
fn+1 = fn + fn-1 за n>0,
f1 = 1
f0 = 0
Рекурсивната функция има
вида:
int Fib(int n)
{
if (n = = 0) return 0;
if (n = = 1) return 1;
return Fib(n-1) + Fib(n-2);
}
Пример: Търсим петото число. Изпълнението на
рекурсивната функция води до лавинообразно увеличаване на рекурсивните
извиквания (фиг.6), което заема много памет в стека.
Задачата
може да се реши с много по-малък разход на памет
итеративно(чрез цикъл).
Където Fi е i - тото число на Фибуначи, а Fi1 - (i-1) - то число на Фибуначи и Fn - n-тото (търсеното) число на Фибуначи. Те
имат начални стойности съответно: Fi=1 и Fi1=0 - по определение.
Рекурсията трябва да се избягва
винаги, когато има очевидно решение чрез итерация.
Алгоритмите,
които по природа са рекурсивни, а не итеративни, трябва да се формулират чрез
рекурсивни функции.
Примери за рекурсивни алгоритми:
1. Намиране на двоично представяне на цяло десетично число без знак.
void Convert(unsigned N)
{
if (N<2) cout<<N;
else {
Convert (N/2);
Cout<<N%2 ;
}
}
2. Извеждане на числова пирамида.
# include <iostream.h>
# include <conio.h>
int x0=40;
void myout (int i, int c)
{
int
x,y=i;
x=x0+(i-c);
gotoxy (x,y); cout<<
c;
x=x0-(i-c);
gotoxy (x,y); cout<<
c;
c--;
if (c = = 0) return;
else myout(i,c);
}
void main(void)
{
int i,c,n;
clrscr ();
cout<<"Задайте височината на пирамидата! n="; cin>>n;
for (i=1; i<n; i++)
{
c=i;
myout (i,c);
}
}
3. Изчертаване на Хилбертови
криви.
Може да
се каже, че всяка крива H(i+1) се получава от 4 броя Hi криви с намалени на
половина размери, подходящо завъртяни и свързани с три линии.
H1 може
да се разглежда от 4 H0(празни) криви свързани с три линии. Ако четирите
съставни части на H(i+1) означим с буквите A, B, C и D (съобразно четирите завъртания), а със стрелки свързващите
линии, то то можем да кажем:
Дължината на една свързваща линия е h. Линия от положението на лъча до точка с
координати (x, y) се
изчертава с функцията lineto(x, y) от библиотеката graphics.h.
За всяка една от четирите ориентации функциите изглеждат
така:
Функция
за изчертаване на фиг.А:
void A( int I ) //изчертаване на фиг. A
{
if (I > 0) //контролира
се дълбочината на рекурсията
{
D(I - 1);
X -= h; lineto( X,
Y ); //изчертава
свързващата линия между фигурите D и A
A(I - 1);
Y += h; lineto( X,
Y ); //изчертава свързващата линия между фигурите A и A
A(I - 1);
X += h; lineto( X,
Y ); //изчертава свързващата линия между фигурите A и B
B(I - 1);
}
}
Функция
за изчертаване на фиг.B:
void B( int I ) //изчертаване на фиг. B
{
if (I > 0) //контролира
се дълбочината на рекурсията
{
C(I - 1);
Y -= h; lineto( X,
Y ); //изчертава
свързващата линия между фигурите C и B
B(I - 1);
X += h; lineto( X,
Y ); //изчертава свързващата линия между фигурите B и B
B(I - 1);
Y += h; lineto( X,
Y ); //изчертава свързващата линия между фигурите B и A
A(I - 1);
}
}
Функция
за изчертаване на фиг.C:
void C( int I ) //изчертаване
на фиг. C
{
if (I > 0) //контролира
се дълбочината на рекурсията
{
B(I - 1);
X += h; lineto( X,
Y ); //изчертава
свързващата линия между фигурите B и C
C(I - 1);
Y -= h; lineto( X,
Y ); //изчертава
свързващата линия между фигурите C и C
C(I - 1);
X - = h; lineto( X,
Y ); //изчертава свързващата линия между фигурите C и D
D(I - 1);
}
}
Функция
за изчертаване на фиг.D:
void D( int I ) //изчертаване на фиг. D
{
if (I > 0) //контролира
се дълбочината на рекурсията
{
A(I - 1);
Y += h; lineto( X,
Y ); //изчертава
свързващите линии между фигурите
D(I - 1);
X -= h; lineto( X, Y );
D(I - 1);
Y - = h; lineto( X, Y );
C(I - 1);
}
}
Дълбочината на рекурсията се контролира от i.
Началната стойност на h (h0) се определя по
формулата h0 = m*2k за k>=N и m>0. N е броя на Хилбертовите
криви.
Изчертаването на Хилбертовите криви започва от средата на
екрана, отлистено 1/2h в дясно и нагоре (за да се получат фигури,
центрирани спрямо екрана).
/*
Изчертаване на Хилбертови криви */
#include <graphics.h>
#include <conio.h>
#define N 5 //брой на фигурите
#define SLineL 384 //основен р-р на линията
int X, Y,
LineL = SLineL;
void B( int I );
void C( int I );
void D( int I );
void A( int I ) //изчертаване на фиг. A
{
if (I > 0) //контролира
се дълбочината на рекурсията
{
D(I - 1);
X -= LineL; lineto( X, Y
); //изчертава свързващата линия между фигурите D и A
A(I - 1);
Y += LineL; lineto( X, Y
); //изчертава свързващата линия
между фигурите A и A
A(I - 1);
X += LineL; lineto( X, Y
); //изчертава свързващата линия
между фигурите A и B
B(I
- 1);
}
}
void B( int I ) //изчертаване на фиг. B
{
if (I > 0) //контролира
се дълбочината на рекурсията
{
C(I - 1);
Y - = LineL; lineto( X, Y
); //изчертава свързващата линия между фигурите C и B
B(I - 1);
X += LineL; lineto( X, Y ); //изчертава свързващата линия между фигурите B и B
B(I - 1);
Y += LineL; lineto( X, Y
); //изчертава свързващата линия между фигурите B и A
A(I - 1);
}
}
void C( int I ) //изчертаване
на фиг. C
{
if (I > 0) //контролира
се дълбочината на рекурсията
{
B(I - 1);
X += LineL; lineto( X, Y
); //изчертава свързващата линия между фигурите B и C
C(I - 1);
Y - = LineL; lineto( X, Y
); //изчертава свързващата линия между фигурите C и C
C(I - 1);
X -= LineL; lineto( X, Y
); //изчертава свързващата линия между фигурите C и D
D(I - 1);
}
}
void D( int I ) //изчертаване на фиг. D
{
if (I > 0) //контролира
се дълбочината на рекурсията
{
A(I -
1);
Y +=
LineL; lineto( X, Y ); //изчертава свързващите линии между фигурите
D(I - 1);
X -= LineL; lineto( X, Y );
D(I - 1);
Y - = LineL; lineto( X, Y );
C(I - 1);
}
}
void main(void)
{
int I =
1,
X0,
Y0,
GraphDriver = DETECT, GraphMode = VGAHI;
initgraph( &GraphDriver, &GraphMode,
"c:\\tc\\BGI\\"); //инициализира
графичен режим
X0 = getmaxx() / 2; Y0 = getmaxy() / 2; //начални
координати - средата на екрана
setcolor( YELLOW ); //жълт
цвят за чертане
do
//цикъл, в който се изчертават N на брой Хилбертови криви
{
LineL /= 2; //намалява
дължината на основната линия два пъти
X0 += LineL / 2; Y0 - = LineL
/ 2; //новите начални координати
X = X0; Y = Y0;
moveto( X, Y
); //премества
се лъча в новите централни координати
A(I); //извиква
се ф-ята за изчертаване на фигура А
}
while
(I++ != N);
getch(); //чака
натискане на клавиш
closegraph(); //затваря
графичния режим
}
Алгоритми
с отстъпване (с връщане назад)
Особено важен клон задачи са тези, за които не може да се
намери фиксирано правило за решаване и единствения възможен подход е методът на
пробите и грешките.
Общата схема се състои в разбиване на проблема на отделни
задачи. Често пъти тези задачи се изразяват най-естествено чрез рекурсия и се състоят
в изследване на краен брой подзадачи. Можем да гледаме на целият процес като на
процес на претърсване (изпробване), при който постепенно се построява и сканира дървото на
подзадачите. В редица случай дървото на такова претърсване расте много бързо,
обикновено експоненционално, в зависимост от даден параметър. В сответствие с
това нараства и времето за претърсване. Често се използва отсичане на части от
дървото, като се използват евристични методи, с което пресмятанията се свеждат
до приемливи граници.
Пример за алгоритми
с отстъпване е задачата за коня
и шахматната дъска:
Постановка:
Дадена е дъска с размери N*N (N2
полета). Конят, на който е разрешено да се движи по правилата на
шаха, се поставя на полето с начални координати (X0,
Y0).
Трябва да се намери покритие на цялата дъска, ако такова съществува, т.е. да се
определи разходка от
N2 - 1 хода, по такъв начин, че всяко поле на дъската да бъде
посетено точно веднъж.
1.
Трябва
да се реши проблемът дали да се извърши следващия ход или да се установи, че
такъв е невъзможен.
void Try() // опит със следващ ход
{
<Инициализиране на възможните ходове
do{
Избор на следващия кандидат от списъка със следващи
ходове
if (<приемлив ход)
{
Регистрация на хода
if (Дъската не е пълна)
{
Опит със следващ ход
if (<неуспех)
Изтриване на предишната регистрация
}
}
} while (ходът е неуспешен> && <има още кандидати);
}
2.
Да
се реши как ще се извършва
регистрацията.
Дъската се описва с матрица Board[N][N] от тип unsigned int. Избира се цяла, а не булева стойност, за да може да се запази историята
на обхождане (т.е. поредния номер на хода при който е заето полето). И така:
Board[x][y]=0
- непосетено поле
Board[x][y]=I - посетено на I-тия
ход
1<=I<=N2
3.
Как
да получаваме информация за това дали ходът е успешен или не.
Това налага функцията Try да връща резултат:
1 - при успех
0 - при неуспех
int Try(void) {……..}
4.
Допълнителни уговорки:
а) налага се функцията да получава като аргументи I, X, Y (I - номер на хода;X,Y - координати на клетката)
б) проверката за дъската
не е пълна се прави с израза I<N2
в) приемлив
резултат
Въвеждат се локални променливи Testx и Testy за евентуалните координати на следващата стъпка. За да е приемлив резултата(хода)
трябва
За да не излезе коня от шахматната дъска
|
|
0<=Testx<=N-1
0<=Testy<=N-1
Board[Testx][Testy]=0
г) Регистрация
на хода
Board[Testx][Testy]=I
д) Изтриване
на предишната регисрация
Board[Testx][Testy]=0
е) Трабва ни още една локална променлива Result, на която да присвояваме
върнатата стойност от рекурсивното извикване на Try.
И така функцията Try добива вида:
int Try( int I,int X,int Y ) //търси позволен код
за коня и връща 1 при успех и 0 при
неуспех
{
int TestX, TestY, //
новите координати на коня
Result; //резултата от изпълнението на функцията
do{
Избор
на следващия кандидат от списъка със следващи ходове
if (( 0 <= TestX ) && ( TestX <
N ) && //ако новата
координата по Х не излиза от дъската
( 0 <= TestY ) && ( TestY <
N ) && //и новата координата по Y не излиза от
дъската
( Board[ TestX ][ TestY ] == 0 )) //и полето не е посетено до сега
{
Board[ TestX ][ TestY ] = I; //в полето се записва № на хода при който е
посетено
if ( I < N*N ) //ако не са обходени всички полета
{
Result = Try( I + 1, TestX, TestY ); //рекурсивно извикване на ф-ята
if ( !Result ) //ако резултатът от рекурсивното
извикване е 0 (неуспех)
Board[ TestX ][ TestY ] = 0; //състоянието на полето се
възстановява в 0 (непосетено)
}
else Result = 1; //ако са обходени всички полета
ф-ята връща 1 (успех)
}
}while (!Result && I<N*N); //ако
стане 1 или всички възможни ходове се изчерпят се
//напуска цикъла
return Result;
}
Остава да решим и последния проблем: определяне на правилата за скоковете на коня
(избор
на следващия кандидат)
Възможните ходове са 8. Ако координатата на коня е (x0, y0), те могат да се получат
така:
|
1 X0+2
Y0+1
2
X0+1 Y0+2
3 X0 -1 Y0+2
4 X0-2 Y0+1
5 X0-2 Y0-1
6 X0-1 Y0-2
7 X0+1 Y0-2
8 X0+2 Y0-1
|
|
|
6
|
|
7
|
|
|
5
|
|
|
|
8
|
|
|
|
к
|
|
|
|
4
|
|
|
|
1
|
|
|
3
|
|
2
|
|
Може да се дефинират два масива с координатите на
отместване: DifferenceX[8] и DifferenceY[8].
Остава да се напише и пълния алгоритъм:
/*
Обхождане с коня на шахматната дъска */
#include
<iostream.h>
#define N
8 //размера на шахматната дъска
#define SqrN
64 //N2
int Board[N][N], //описва
шахматната дъска
DifferenceX[8]={2,1,-1,-2,-2,-1,1,2}; //описва отместванията по Х
int DifferenceY[8]={1,2,2,1,-1,-2,-2,-1}; //описва отместванията по Y
int X0, Y0; //начални координати на коня
//инициализира
дъската (попълва всички полета със стойност 0)
void
InitializeBoard( void)
{
int
I, J;
for ( I = 0; I < N; I++ )
for ( J = 0; J < N; J++ )
Board[ I ][ J ] = 0;
}
int Try( int I,int X,int Y ) //търси позволен код
за коня и връща 1 при успех и 0 при
неуспех
{
int
TestX, TestY, // новите
координати на коня
K = 0, //индекс на масива с възможните
ходове
Result = 0; //резултата от
изпълнението на функцията
do //цикъл за търсене на
удачен ход
{
TestX = X + DifferenceX[ K ]; //определя се новата координата по X
TestY = Y + DifferenceY[ K ]; //определя се новата координата по Y
if (( 0 <= TestX ) && ( TestX
< N ) && //ако
новата координата по Х не излиза от дъската
( 0 <= TestY ) && ( TestY
< N ) && //и новата координата по Y не излиза от
дъската
( Board[ TestX ][ TestY ] == 0 )) //и полето не е посетено до сега
{
Board[ TestX ][ TestY ] = I; //в полето се записва №
на хода при който е посетено
if ( I < SqrN ) //ако не
са обходени всички полета
{
Result = Try( I + 1, TestX, TestY ); //рекурсивно извикване на ф-ята
if ( !Result ) //ако резултатът от
рекурсивното извикване е 0 (неуспех)
Board[ TestX ][ TestY ] = 0; //състоянието на полето се възстановява в
0 (непосетено)
}
else Result = 1; //ако са обходени всички
полета ф-ята връща 1 (успех)
}
}
while (( !Result
) && ( ++K < 8 ));
//ако стане 1 или всички възможни
ходове се изчерпят се
//напуска
цикъла
return Result;
}
void
WriteSolution( void ) //извежда
състоянието на полетата на дъската
{
int
I, J;
cout<<endl;
for ( I = 0; I < N; I++ )
{
for ( J = 0; J < N; J++ )
cout<< Board[ I ][ J ] ;
cout<<endl;
}
}
void main(void)
{
cout<<"въведете началните
координати на коня"<<endl;
do { //цикъл за въвеждане на коректни
начални координати
cout<<"X0=";cin>>X0;
cout<<"Y0=";cin>> Y0 ;
}while (( X0 < 1 ) || ( Y0 < 1 ) || ( X0
> N ) || ( Y0 > N ));
InitializeBoard(); //инициализира дъската
Board[ --X0 ][ --Y0 ] = 1; //записва първия ход на дъската
//тъй като в С++ индексите започват от 0,
// матричните координати на коня са с 1 по-малки от
действителните
if ( Try( 2, X0, Y0 )) //извиква ф-ята Try за търсене на втори и следващи ходове и ако търсенето е
WriteSolution(); // успешно, извежда
състоянието на дъската
else cout<<"Не може да се
обходи"<<endl; //ако
търсенето не е успешно, извежда съобщение
}
