Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

2.4. Dərinliyə seçmə alqoritmi

Bu alqoritm stek tipli massivdən istifadə etməklə, qrafda ixtiyari iki düyün arasında mövcud olan bütün yolları qurmağa imkan verir [10,17]. Alqoritmi şərh etmək üçün aşağıdakı elementləri daxil edək:

- verilmiş qrafın düyünlərinin qonşuluq matrisi;
- minorant, - majorant düyünlərdir; alqoritm qurulan zaman şəkil 2.19-a istinad olunmuşdur, sadəlik üçün işarəsi əvəzinə “1” simvolundan, əvəzinə “6” simvolundan istifadə olunmuşdur ;
S,Z–stekləri qurulan yolun keçilən hissəsinin yadda saxlanılması üçün istifadə olunur; S-potensial yolun cari addıma aid qurulan hissəni, Z – cari addımdan bir addım əvvəlki addıma aid hissəsini yadda saxlamaq üçün istifadə olunur, bu struktur geriyə qayıtma zamanı düyünə düşməmək üçün istifadə olunur.

Şək.2.19. Alqoritmin tətbiqi üçün istifadə olunan şəbəkənin modeli

1	2	3	0
2	4	5	0
3	4	5	0
4	6	0	0
5	6	0	0
6	0	0	0

Şək.2.20. Qonşuluq matrisi

Dərinliyə seçmə alqoritmi:

1. elementlərini yadda saxlamaq;
2. S,Z =0 (steklərin hesablamalara hazırlanması );
3. S(1)=1 (S-in 1-ci xanasına şəbəkənin 1-ci düyününün nömrəsini mənimsətməli), Z(i)=0,
4. ;
5. ;
6. ;
7. Əgər , keç 11-ci addıma, əks halda davam et;
8. Əgər x ≤ Z(1), 5-ci addıma keç, əks halda davam et;
9. S(i)=S(i-1) əməliyyatını yerinə yetir, burada , yəni S stekinin məzmununu sağa sürüşdür: S(1)=x, Z(i)=Z(i-1), burada: ; Z(2)=S(1); Z(1)=0;
10. Əgər olarsa, onda planını çap et, növbəti addıma keç; əks halda 4-cü addıma keç;
11. S,Z steklərinin məzmununu bir xana sola sürüşdür:
S(i)=S(i+1), Z(i)=Z(i+1), burada , S(L)=0, Z(L)=0;
12. Əgər S(1)=0 , onda - stop, əks halda 4-cü addıma keç.
Cədvəl 2.1-də hesablamaların gedişatı və alınan nəticələr öz əksini tapıb.


Cədvəl 2.1
Dərinliyə seçmə alqoritmi ilə S və Z steklərinin məzmununun adımdan addıma dəyişməsi

S(1)	S(2)	S(3)	S(4)	Z(1)	Z(2)	Z(3)	Z(4)	j	x
1	0	0	0	0	0	0	0	1	2
2	1	0	0	0	2	0	0
4	2	1	0	0	4	2	0	1	4
6	4	2	1	0	6	4	2	1	6
4	2	1		6	4	2	0
…	…	…	…	…	…	…	…	…	…
6	5	2	1	0	6	5	2	1	6
…	…	…	…	…	…	…	..	…	…
6	4	3	1	0	6	4	3	1	6

3.Rekursiv funksiyaların hesablanması üsulları və analizi
3.1. Birdəyişənli rekursiv funksiyalar

Alqoritmlərə aid ən mühüm anlayışlardan biri rekursiv funksiya anlayışıdır. Funksiyanı hesablamaq üçün müxtəlif üsullar var: cədvəllə, birbaşa hesablama üsulu, rekursiv üsul. Birbaşa hesablama üsulu daha əlverişli olsa da bəzi hallarda funksiyanı başqa bir üsulla, məsələn, rekursiv üsulla vermək, daha münasib, hətta zəruridir. Rekursiv funksiya funksiyanın xüsusi növüdür. Onun hesablanması riyazi induksiya üsuluna əsaslanır. Hər bir rekursiv funksiya müsbət tam ədədlər çoxluğunda təyin olunur. Funksiyanın hesablanması zamanı onun əvvəlki addımlardakı qiymətlərindən, həmçinin addımın nömrəsindən istifadə oluna bilir.

Əgər f(n) funksiyası üçün aşağıdakı şərtlər ödənərsə :
1) bu funksiya n N olmaqla , n-in müəyyən n₀ başlanğıc qiymətində təyin olunub, 2) bu funksiyanın hər hansı k>n₀ nöqtəsində təyin olunmasından k+1 nöqtəsində də təyin olunması alınırsa, onda bu funksiya ümumiyyətlə n₀-dan byük bütün natural qiymətlərdə təyin olunub, belə funksiya rekursiv qaydada hesablanan funksiya, ya da sadəcə rekursiv funksiya adlanır.
Rekursiv üsulla hesablanan funksiyalara müxtəlif sahələrdə rast gəlinir. Bunlardan birinə nəzər salaq[4]. Fərz edək, iqtisadiyyatın müəyyən sahəsinə M məbləğində investisiya ayrılmışdır. Hesablama periodun sonunda aparılır və faiz gəliri iM məbləğinə bərabərdir, ona görə də investisiyanın ümumi həcmi M+iM= (1+i)M ədədinə bərabər olacaq. Növbəti perioda görə investisiyanın məbləği belə hesablanır: (1+i)M+i(1+i)M=(1+i)²M. Üçüncü perioda görə (1+i)³M və s.


Cədvəl 3.1
İnvestisiya haqqında məsələnin rekursiv hesablamaları

periodlar	faizlə birlikdə investisiya məbləği
[0;1]	M
(1;2]	M+iM
(2;3]	(1+i)^2M
..........................................	............................................
(n-1;n]	(1+i)^n-1M

Beləliklə, n perioda görə investisiyanın ümumi məbləği M+ (1+i)M+(1+i)²M+...+(1+i)^n-1M =M F(n,i) düsturu ilə hesablana bilər. Burada:

F(n,i)=1+(1+i)+ (1+i)²+...+(1+i)^n-1.
Aydındır ki, bu cəm həndəsi silsilə təşkil edir, ona görə də yaza bilərik:
F(n,i) = = .
Deməli, F(n,i) kəmiyyətini yuxarıdakı kimi birbaşa düsturla hesablamaq olar. Lakin bunu həm də rekursiv qaydada hesablamaq olar:
F(n,i)=1+(1+i)+(1+i)²+...+(1+i)^n-1=1+(1+i)(1+(1+i)+ (1+i)²+...+(1+i)^n-2)=1+(1+i) F(n-1,i).
F(n,i) kəmiyyətinin hesablanması üçün düstur belə olacaq:

F(1,i)=1,

F(n,i)=1+(1+i)F(n-1,i), n olduqda. (3.1)
Birdəyişənli rekursiv funksiya kimi hesablanan nümunələrdən biri də zəncirvari kəsrlərdir[3]. Zəncirvari kəsrlər nəzəriyyəsi həqiqi ədədlərin rasional yaxınlaşması nəzəriyyəsi ilə, dinamik sistemlər nəzəriyyəsi ilə, həmçinin riyaziyyatın bir çox sahələri ilə sıx bağ­lıdır. Qədim riyaziyyatçılar həqiqi ədədləri bir-biri ilə əlaqəli ardıcıl zəncirlər şəklində təsvir edə bilirdilər. Arximed məhz bu yolla düsturunu almışdır.
V əsrdə hind riyaziyyatçısı Ariabhat “xırdalama üsulu” ilə analoji metodu birinci və ikinci tərtib qeyri – müəyyən tənliklərin həllinə tətbiq etmişdir. Bu üsulun köməyi ilə ədədinin təqribi qiyməti hesablanmışdır, . XVI əsrdə Rafael Bombelli zəncirvari kəsrlərin köməyilə kvadrat kökləri hesab­lamışdır.
1613 – cü ildə Petro Antonio Kataldi zəncirvari kəsrlər nəzəriyyəsinin müasir dövr üçün başlanğıcını qoydu. O, zəncirvari kəsrlərin əsas xassələrini qeyd etdi və tərifləri verdi. Sonra onun nəzəriyyəsini Con Ballis genişləndirdi. “Zəncirvari kəsr” termini XVIII əsrin sonunda yarandı.
Ilk növbədə bu kəsrlər həqiqi ədədlərin rasional yaxınlaşmasına tətbiq olunurdu, məsələn, Xristian Hüyhensi onu dişli çarxın layihələndirilməsində istifadə etmişdir. Hüyhensi artıq bilirdi ki, yaxınlaşan kəsrlər ixtisar olunmayandır.
XVIII əsrdə zəncirvari kəsrlər nəzəriyyəsini ümumiləşdirən Leonard Eyler və Jozef Lui Laqranj olmuşdur.
Zəncirvari kəsrlərin ümumiləşmiş yazılışı aşağıdakı kimidir:
(3.2)
Zəncirvari kəsrlərin, (i=1, 2, 3, ....) elementləri qismində həqiqi ədədlər, kompleks ədədlər, hətta bir və ya çoxdəyişənli funksiyalar da ola bilər. kəsrlərinə zəncirvari kəsrlərin düyünləri deyilir. ədədi sıfırıncı düyün hesab olunur. Əgər zəncirvari kəsrlər sonludursa, onu aşağıdakı kimi yazmaq olar:
(3.3)
Əgər zəncirvari kəsrlər sonsuz sayda düyünə malik olarsa, onu aşağıdakı kimi yazmaq olar:

Əgər zəncirvari kəsrdəbütün əmsalları 1-ə bərabər olarsa, bu kəsrə adi, yaxud standart zəncirvari kəsr deyilir.
İxtiyari sonlu zəncirvari kəsri adi kəsrə çevirmək olar. Bundan ötəri zəncirvari kəs­rin yazılışında göstərilən bütün əməliyyatları yerinə yetirmək lazımdır.
Bundan başqa, yuxarıda qeyd olunan hökmün əksi də doğrudur: ixtiyari müsbət rasional ədədi natural elementli zəncirvari kəsrə çevirmək olar. Tutaq ki, kəsri verilmişdir. Bu kəsrin tam hissəsini ilə işarə edək, onda kəsrini aşağıdakı kimi təsvir edə bilərik:

burada –qalıqdır. Əgər bu kəsr düzgün kəsrdirsə, onda

kəsrinin surət və məxrəcini ədədinə bölsək, alarıq:

burada tam qiymətlidir, q ədədinin -a bölünməsindən alınan qalıqdır.
Indi də kəsrinin surət və məxrəcini -ə bölək:

burada tam qiymətlidir, isə –ın -ə bölünməsindən alınan qalıqdır.
Hesablamanı analoji qaydada davam etdirmək olar.
Ümumiyyətlə, şərti ödəndiyi üçün, müəyyən addımda nəticəsinin alınması labüddür.

Nəhayət, kəsrlərini yerinə yazsaq, aşağıdakı kimi zəncirvari kəsr alınar:



Məsələn, göstərmək olar ki:
Məlum qaydalardan istifadə etməklə zəncirvari kəsri də adi kəsrə çevirmək olar. Misal:



Aşağıdakı çevirmələri yerinə yetirək:



Beləliklə, alırıq:

Bir çox hallarda rekursiyadan azad olaraq birbaşa düsturla hesablama aparmaq mümkündür. Məsələn, aşağıdakı qaydada verilmiş rekursiv hesablamaya baxaq:
f(1)=1;
f(k)=f(k-1)+k.
Xüsusi hallara baxaq:
f(1)= 1= ;
f(2)=1+2=3= ;
f(3)= 3+3=6= ;
f(4)=4+6= .
Məntiqcə ümumiləşmiş birbaşa düstur belə olmalıdır:
f(n)= .
Bunun doğruluğunu riyazi induksiya ilə isbat edək:
f(1) = = 1;
f(2)= 3;
f(3) = =6.
k-1 üçün hökmün doğruluğunu qəbul edib k üçün bunun doğruluğunu isbat etməyə çalışaq.
f(k-1)=

f(k)= f(k-1)+k= +k= = =

İsbat olundu.
Birbaşa düstur riyazi induksiya ilə isbat olunandan sonra rekursiv düsturun yerinə istifadə oluna bilər. Bəzən verilən məsələni həll etmək üçün həm rekursiv, həm də birbaşa düsturlar mövcud olur. Lakin elə məsələlər var ki, onların hesablanmasın yalnız birbaşa, müəyyən məsələlərin həlli üçün yalnız rekursiv üsullardan istifadə oluna bilər. Elə məsələlərə baxaq ki, onların həllində həm birbaşa, həm də rekursiv düsturlardan istifadə oluna bilər. Məsələn, Hanoy qülləsi haqqında məsələnin mürəkkəbliyini araşdırmaq tələb olunsa, disklərin sayından (n) asılı olaraq aşağıdakı düsturlardan istifadə oluna bilər:
f(n)=2ⁿ (3.4)
(3.4) düsturu birbaşa düsturdur.
f (1)=1
f(n)=2*f(n-1)+1 (3.5)
(3.5) düsturu rekursivdir.
Elə məsələlər var ki, bunların həlli üçün rekursiv düstur dəqiq cavab verdiyi halda, bunun birbaşa düsturu təqribi cavab verir. Bu hal onunla əlaqədardır ki, bu məsələni həll etmək üçün dəqiq birbaşa düstur qurmaq qeyri-mümkündür.
Aşağıdakı düstura Stirlinq düsturu deyilir.
(3.6)
n
son

p=p*i
ədədi böyük olduqda rekursiv funksiyanın hesablanması praktiki cəhətdən çətin olarsa, birbaşa düstur təqribi olsa da, ondan istifadə etmək daha məqsədəuyğundur.
Aşağıdakı cədvəldə hər iki üsulla hesablana bilən bəzi funksiyalara aid nümunələr verilmişdir[3].
Cədvəl 3.2
Rekursiv və birbaşa üsullarla hesablanan bəzi funksiyalar

Rekursiv üsulla	Birbaşa üsulla
g(0)=1, g(k+1)=ag(k)	g(k)=
g(0)=1, g(k+1)= g(k)	g(k)=
g(1)=2, g(k)=2kg(k-1)	g(k)=2^kk!
g(0)=5, g(k)=2g(k-1)-7 (k>0)	g(k)=7-2^k+1
g(0)=1, g(1)= -6, g(k)=6g(k-1)-9g(k-2) (k>1)	g(k)=3^k-k3^k+1
g(0)= -3, g(1)= -5, g(k)=6g(k-1)-8g(k-2)-3 (k>1)	g(k)= -1-2^k+1