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

5.4. İnformasiyanın axtarışı üsulları
Fərz edək, ardıcıllığı verilmişdir, bundan başqa hər hansı ədədi verilmişdir. ədədini tapmaq tələb olunur. Bu işi görməyə çalışaq[10]. İki hala baxaq:
I) ardıcıllığı nizamlanmayıb. Bu halda adətən tam seçmə üsulundan istifadə olunur. b ədədi əvvəlcə a₁ ilə, sonra a₂ ilə və s., a_i=b olana qədər axtarış davam edir. Deməli, müqayisələrin sayı təsadüfi hadisədir. Ən yaxşı halda axtarış 1 müqayisə ilə tamamlanacaq (a₁=b), ən pis halda müqayisələrin sayı n-ə bərabər olacaq (a_n=b). Deməli, tam seçmə üsulu ilə müqayisələrin orta sayını halında qiymətləndirə bilərik:

II) Ardıcıllıq nizamlanmışdır. Bu halda müqayisələrin sayını kifayət qədər azaltmaq olar, buna, məsələn, parçanı yarıya bölmə üsulunu tətbiq etməklə nail olmaq olar.
Məsələ belə qoyulur: nizamlanmış ardıcıllığında b elementinə bərabər olan bir elementi tapmalı. Sadəlik üçün ardıcıllığın elementlərini ədədlərdən ibarət təsəvvür edək. Bu ədədlər bir-birindən fərqli olsun, yəni i≠j olduqda a_i≠a_j olsun. Qeyd edək ki, ardıcıllığın elementləri başqa obyektlər olsa da yenə bu ardıcıllığı ədədi ardıcıllıqla əvəz etmək olar. Məsələn, tutaq ki, hərflərdən ibarət müəyyən ardıcıllıq verilib, bu halda verilən ardıcıllığı ədədi ardıcıllığa çevirmək üçün a-1,b-2,c-3 və s. əvəzləmələrindən istifadə etmək olar. Ona görə də şərti olaraq yaza bilərik: a

i= ]+1 (5.4)

Misal: b=20 ədədini a(1),…,a(8) ardıcıllığında tapmaq tələb olunur. Parçanı yarıya bölmə üsulunu tətbiq edək.

out

Müq.-in sayı					1		2
a(i)	3	8	10	11	15	16	20	30
i	1	2	3	4	5	6	7	8

n=8,
i=[ ]+1=5,

a(i)=a(5)=15<20,
n=n-5=3,
i=[ ]+1=2,
a(i)=a(2)=20. İkinci addımda b=20 ədədi tapıldı.
“Out” yazılışı ardıcıllığın kənarlaşdırılan hissəsini göstərir.
Bu üsulla müqayisələrin sayını qiymətləndirmək üçün rekursiv (5.2) düsturundan istifadə olunacaq.
Beləliklə (5.2) düsturu yarıya bölmə üsulu ilə maksimal müqayisələrin sayını qiymətləndirmək üçün rekursiv düsturdur.


Cədvəl 5.1
Parçanı yarıya bölmə üsulu ilə müqayisələrin sayının elementlərin sayından asılı olaraq qiymətləndirilməsi

i (elementlərin sayı)	U(i) (müqayisələrin sayı)
1	1
2,3	2
4,5,6,7	3
8,9,10,11,12,13,14,15	4
......	.......
[2^k,2^k+1-1]	k+1

Cədvəl 5.1-də ardıcıllıqda elementlərin i sayından asılı olaraq müqayisələrin U(i) sayını birbaşa qiymətləndirmək üçün informasiya verilib. Məsələn: i=35 olarsa, müqayisələrin maksimal sayını birbaşa düsturla qiymətləndirək. Bunun üçün elə bir k ədədi tapmaq lazımdır ki, 35 [2^k,2^k+1-1] olsun.
32<35<63
2⁵<35<2⁶-1. Deməli, U(i)=6. Digər tərəfdən bu qiymətləndirməni rekursiv qaydada hesablasaq, yenə həmin nəticə alınacaq:
U(35)=1+U(17)=2+U(8)=3+U(4)=4+U(2)=5+U(1)=6
Fibonaççi üsulu ilə axtarış:
Bu üsulun tətbiqi zamanı parçanı 2 fərqli hissəyə bölürlər.

A 1,618x C x B

Hissələrin bir-birinə nisbəti “qızıl bölgü” prinsipi ilə aparılır. C nöqtəsinə uyğun gələn element b ədədi ilə müqayisə olunur, b ədədi bundan böyükdürsə AC parçası atılır, kiçikdirsə CB atılır, bərabərdirsə- stop, və s.
Misal: b=22 ədədini Fibonaççi üsulu ilə tapmalı.

a(i)	3	7	8	10	15	17	20	22	25	30	34
i	1	2	3	4	5	6	7	8	9	10	11

n=11 n=n-5=6
x+1,618x=11 x=[ ]=2
x=[ ]=4 i=x+1=3
i=x+1=5 a(3)=22, stop.
a(5)=15<22
Axtarışla bağlı başqa bir məsələyə baxaq. Fərz edək, ardıcıllığı verilmişdir, bundan başqa hər hansı ədədi verilmişdir. Bu ardıcıllığın k sayda elementlərini tapmaq tələb olunur ki, bunların cəmi b ədədinə bərabər olsun:

Bu axtarış məsələsinin həlli üsulunun seçilməsi də verilmiş ardıcıllığın nizamlanmasından asılıdır. Belə ki, ardıcıllıq nizamlanmamış olarsa, elementlərinin tam müqayisəsi zəruridir. Müqayisələrin sayı , yəni kombinezon düsturu ilə qiymətləndirilir.
elementləri nizamlanmış olarsa, ardıcıllıq iki hissəyə bölünür. Beləliklə, verilmiş ardıcıllığı şəklində təsvir etmək olar. Bu zaman şərti əsas götürülür. Aşağıdakı hallar mümkündür:
1) - bu halda məsələnin həlli yoxdur;
2) - bu halda məsələnin yeganə həlli var;
3) - məsələnin birdən çox həlli ola bilər.