Va kommunikatsiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axbarot tehnologiyalari universiteti



Download 288,57 Kb.
Sana29.04.2020
Hajmi288,57 Kb.
#48179
Bog'liq
malumotlar tuzilmasi va algoritmlash

    Bu sahifa navigatsiya:
  • Mavzu

O’ZBEKISTON RESPUBLIKASI AXBAROT TEHNOLOGIYALARI

VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBAROT TEHNOLOGIYALARI UNIVERSITETI

‘’MTA ’’ kafedrasi

‘’ Malumotlar tuzilmasi va algoritmlash’’ fani bo’yicha

MUSTAQIL ish



Mavzu: Qidiruv va uning vazifasi.Indeksli ketma ket qidiruv algoritmi va uning qo’lanilishi;

Bajardi:006-Guruh talabasi

Qilichov S



Tekshirdi: Raxmanov A

Toshkent - 2019

Aytaylik bizga tartiblangan n ta elementdan iborat a[] massiv berilgan bo'lsin, va berilgan x ni a[] ichidan qidirish funksiyasini tuzish sharti qo'yilsin.

Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidir algoritmini ishlatsak bo'ladi.

Binar qidiruv

Qiyinlik darajasi: 5/10.

Eng zo'r ko'rsatkichi(vaqt): O(1)

Eng yomon ko'rsatkichi(vaqt): O(log n)

O'rtacha ko'rsatkichi(vaqt): O( log n)

Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha.



Masalan:

Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi.

1. x ni o'rtadagi element bilan solishtiramiz.

2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.

3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.

4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz.

Quyida Binar qidiruvning rekursiya orqali amalga oshiramiz.

// C++ tilida rekursiyali Binar Qidiruv

#include

// Rekursiyali qidiruv funksiyasi. U massivdan

// x qaysi o'rinda turganini qaytaradi,

// yoki -1



int binarqidiruv(int a[], int l, int r, int x)

{


if (r >= l)

{


int mid = l + (r - l)/2;

// Agar element x ga teng bo'lsa

// o'zi qaytadi

if (a[mid] == x)

return mid;

// Agar element x dan katta bo'lsa,

// u faqat chap qismni oladi

if (a[mid] > x)

return binarqidiruv(a, l, mid-1, x);

// Yoki u faqat o'ng qismni oladi



return binarqidiruv(a, mid+1, r, x);

}


// Bu yerga yetib keladi, qachonki

// x soni massiv ichidan topilmasa



return -1;

}


int main(void)

{


int a[] = {2, 3, 4, 10, 40};

//massiv ni elementlar sonini topib olayabmiz



int n = sizeof(a)/ sizeof(a[0]);

int x = 10;

int natija = binarqidiruv(a, 0, n-1, x);

(natija == -1)? printf("X soni massivni ichidan topilmadi.")

: printf("X soni massivning %d - elementi.",

natija);



return 0;

}

Dastur ishlaganda " X soni massivning 3 - elementi." degan yozuvni qaytaradi. Sababi massiv elementlari 0 dan boshlanadi.

Binar qidiruvning yana bir ko'rinishi Interative (ingliz tilida ) orqali ko'rsatamiz.

// C++ tilida interative binar qidiruv

#include

// Interative binar qidiruv funksiyasi. U massivdan

// x qaysi o'rinda turganini qaytaradi,

// yoki -1



int binarqidiruv(int a[], int l, int r, int x)

{


while (l <= r)

{


int m = l + (r-l)/2;

// X o'rtadagi elementga tengmi yo'qmi tekshiramiz



if (a[m] == x)

return m;

// Agar x katta bo'lsa, chapni hisobga olmaymiz



if (a[m] < x)

l = m + 1;

// Aks holda o'ng tarafni hisobga olmaymiz

else

r = m - 1;

}

// Dastur bu yerga qachonki x element topilmaganda yetib keladi.



return -1;

}


int main(void)

{


int arr[] = {2, 3, 4, 10, 40};

// Elementlar sonini n ga o'zlashtirayabmiz



int n = sizeof(a)/ sizeof(a[0]);

int x = 10;

int natija = binarqidiruv(a, 0, n-1, x);

(natija == -1)? printf("X soni massiv ichida topilmadi.")



: printf("X soni massivning %d o'rnida.", natija);

return 0;


Download 288,57 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish