Labaratoriya –10 Mavzu: Qidiruv masalasi, qidruv usullari Ishning maqsadi

---

LABARATORIYA –10 

 

Mavzu: Qidiruv masalasi, qidruv usullari 

 

Ishning maqsadi

:  Qidiruv usullarini  amalda qo’llanilishi va  shu usullardan 

foydalanibturli xil  dasturiy vositalar yaratishi haqidagi bilimlarga  ega bo’lish

. 

 

NAZARIY QISM 

Eng yomon holat tahlili.Ketma-ket izlash algoritmi ikki  xil  “eng yomon holat” variantiga 

ega.  Birinchi  holatda    maqsad  elementi  ro‘yxatda  yeng  oxirgi  o‘rinda  joylashgan  bo‘ladi. 

Ikkinchi  holatda  maqsad  jlementi  ro‘yxatda  avjud  bo‘lmaydi.  Ushbu  ikki  holatda  nechtadan 

taqqoslash amallari bajarilishini aniqlaymiz.  Agar ro‘yxat elementlari takrorlanmas deb faraz 

qilsak,  ro‘yxatning oxirgi elementiga yetgunga qadar algoritm N ta (ro‘yxat  N ta elementdan 

iborat) taqqoslashni bajaradi.  

Xuddi shunga o‘xshash tarzda maqsad elementi mavjud bo‘lmagan ro‘yxatda ham algoritm N 

ta  taqqoslash amalini bajaradi. 

O‘rtacha holat tahlili.Izlash algoritmlari uchun ikkita o‘rtacha holat bo‘lishi mumkin.  Birinchi 

holatda  izlash  jarayoni  doimo  muvaffaqiyatli  tugaydi  deb,    faraz  qilinadi.  Ikkinchi  holatda 

maqsad elementi mavjud bo‘lmaydi. Agar maqsad elementi ro‘yxatda mavjud bo‘lsa, u mumkin 

bo‘lgan N ta pozitsiyadan birini egallaydi. Uning bu pozitsiyalardan har birini egallash ehtimoli 

bir xil deb hisoblasak, bu ehtimol 1/N ga teng.  N  ta holatdan har bittasi uchun  algoritmning 

bajaradigan  taqqoslashlari  soni  izlanuvchi  element  tartibi  bilan  mos  tushadi.  Agar  maqsad 

element topilsa, return operatori ishlaydi va sikl to‘xtatiladi. Agar maqsad element topilmasa, 

har  bir  sikl  iteratsiyasida  start  o‘zgaruvchisining  qiymati  ortadi  yoki  end  o‘zgaruvchisining 

qiymati  kamayadi.  Bu  ikki  o‘zgaruvchining  qiymatlari  bir-biriga  yaqinlashib  boradi.Qaysidir 

qadamda bu ikki o‘zgaruvchining qiymati tenglashib, start=end=middle sharti uchun ham sikl 

yana  bir  marta  bajariladi.  Shundan  so‘ng  ushbu  indeksli  element  maqsad  element  bo‘lmasa, 

start ning qiymati middle va endga nisbatan  1 ga oshadi yoki aksincha end ning qiymati middle 

va start ga nisbatan 1 ga kamayadi. Ikki holatda ham while operatorining sharti yolg‘on qiymat 

qabul qilib, sikl to‘xtatiladi. 

O‘rtacha holat tahlili. O‘rtacha holatni tahlil etishda ikki imkoniyat ko‘rib chiqiladi:maqsad 

elementning ro‘yxatda mavjud bo‘lgan  holat; maqsad elementning ro‘yxatda mavjud 

bo‘lmaslik holati. Birinchi holatda N ta imkoniyat mavjud va ularning barchasi teng kuchli  l/N 

ehtimolga ega. 

 

 

 

 

 

 

 

Variantlar 

---

Quyidagi masalalar yechimini topadigan dastur  tuzilsin: 

 

1. Quyidagi yig’indini hisblash dasturini 

tuzing.

 

3. Quyidagi yig’indini hisblash dasturini 

tuzing.

 

 

2. 

n

 natural soni berilgan  

p

=

(   

 

 

 

)   (   

 

 

 

)       (   

 

 

 

)

      

ko’paytmani topuvchi dastur tuzing. 

4. Quyidagi ko’paytmani hisblash dasturini 

tuzing. 

 

 

g. 

5. 

N

 natural soni berilgan  

S=1∙2+2∙3+3∙4+…+ yig‘indini 

qiymatini hisoblang.