Algoritmlarni loyihalash Labaratoriya ishi №2

Muhammad Al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti

Fan nomi: Algoritmlarni loyihalash

Labaratoriya ishi №2

Variant №7

Mavzu: Ketma-ket qidiruv usulidan foydalanib, A massivda elementlarni va taqqoslashlar sonini toping



Guruh:CAL016-L2

Bajardi: Mamadaliyev Arabboy

Tekshirdi:Nazarov Azizbek

Toshkent -2020

Variyant № 7

Vazifa: Ketma-ket qidiruv usulidan foydalanib, A massivda elementlarni va taqqoslashlar sonini toping

Python dasturlash tilida yozilgan kodi :

# Ketma-ket qidiruv

x=int(input("Massiv nechta sondan iborat bo'lsin : "))

A=[]

for i in range(x):

i=int(input("son kiriting "))

A.append(i)

print("A = ",A)

y=int(input("Qidirmoqchi bo'lgan sonni kiriting : "))

def qidiruv(A, y):

for i in range(len(A)):

if A[i] == y:

return i

return -1

print("Qidirilayotgan ",y," soni massivda",qidiruv(A,y),"-indexda joylashgan")

print("Taqqoslashlar soni:",qidiruv(A,y)+1)

Visual studioda yozilgan :

# Ketma-ket qidiruv

x=int(input("Massiv nechta sondan iborat bo'lsin : "))

A=[]

for i in range(x):

    i=int(input("son kiriting "))

    A.append(i)

print("A = ",A)

y=int(input("Qidirmoqchi bo'lgan sonni kiriting : "))

def qidiruv(A, y): 

    for i in range(len(A)): 
        if A[i] == y: 

            return i 

    return -1

print("Qidirilayotgan ",y," soni massivda",qidiruv(A,y),"-indexda joylashgan")

print("Taqqoslashlar soni:",qidiruv(A,y)+1)

Dastur natijasi :

1

2

Topshiriq 2. Quyidagi nazariy savollarga javob bering

1. 
   Qidiruvning ahamiyatini ayting
   

Kerakli ma’lumotni topishni osonlashtirishdan iborat bunda qidiruvga ketgan vaqt qisqa bo’lishi kata ahamiyatga ega.

2. 
   Qanday qidiruv algoritmlari bor
   

Chiziqli(ketma-ket) va Binar(ikkilik) qidiruv algoritmlari bor.

3. 
   Ikkilik qidiruv haqida ma’lumot bering
   

Dastlab biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz, mening kodimda bu left va right o'zgaruvchilaridur:

left := 0 right := len(a)

so'ngra quyidagi shart bajarilgan holda

left < right

quyidagi ketma-ket operatsiyalarni amalga oshiramiz

1. 
   left va right index lari markazidagi elementni topamiz (left + right) / 2
   
2. 
   topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
   
3. 
   agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi.
   
4. 
   agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right = mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom etadi.
   

Ikkilik (Binar) qidiruvning ayrim jihatlari:

• 
  funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q
  
• 
  chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n)
  

4. 
   Ketma-ket qidiruv haqida ma’lumot bering
   

Ketma-ket qidiruv eng soda qidiruv algoritmi bo’lib u qidirilayotgan elementni berilgan massiv elementlarini boshidan oxirigacha ketma-ket ravishda mos kelishligini tekshirishdan iborat.Agar qidirilayotgan element massivning boshida joylashgan bo’lsa qidiruvga ko’p vaqt ketmaydi lekin massiv oxirida joylashgan bolsa bu jarayon ko’p vaqt talab etadi va bu ketma-ket qidiruvning asosiy kamchiligi bo’ladi.