Muhammad Al-Xorazmiy nomidagi Toshkent Axborot texnologiyalari Universiteti Samarqand filiali ki 21-02-guruh talabasi Abdurahmonov O’ktamning Ma’lumotlar tuzilmasi va Algoritmlash fanidan

Download 184.36 Kb.
Sana	26.05.2023
Hajmi	184.36 Kb.
	#64897

Bog'liq
2-mustaqil ish
Эркаклар жинсий аъзолари. Уруғдон. Уруғдон ортиғи., REFERAT - Abdulla Qahhor ijodi, REFERAT - ABOUT ANIMALS, 9-хафта Маруза Баскетбол №9

n Muhammad Al-Xorazmiy nomidagi
Toshkent Axborot texnologiyalari Universiteti Samarqand filiali
KI 21-02-guruh talabasi
Abdurahmonov O’ktamning
Ma’lumotlar tuzilmasi va Algoritmlash fanidan
2-mustaqil ishi

Reja:

Qisqacha nazariy ma’lumot

2. Ikkilik qidirish algoritmi ishlash prinsipi

Kalit so’zlari:binar daraxt, o’ng va chap qismdaraxtlar, qidiruv daraxti,daraxtdan o’tishlar (daraxtni ko’rib chiqish), binar heap, ikkilik piramida, maxHeap,minHeap.

Qisqacha nazariy ma’lumotBinar daraxt – bu har biri boshqa turlicha binar daraxtlarga ikkitako’rsatkichlarni saqlab turuvchitugunlardan iborat dinamik ma’lumotlar tuzilmasi.Har bir tugunga bitta ko’rsatkich mavjud.Bunday tuzilmani quyidagicha shaklda tavsiflash mumkin:

struct point
{int data;//ma’lumot maydoni
point *left;//chapqism daraxt manzili
point *right;// o’ngqism daraxt manzili};
Boshlang’ich tugun daraxtningildizideyiladi. Qismdaraxtga ega bo’lmagantugunbargdeb nomlanadi. Chiquvchiga ega bo’lgan tugunlarajlodtugun, kiruvchigaega bo’lgan tugunlaravlodtugun deyiladi. Daraxt balandligi uning tugunlarijoylashganbosqichlarisoni bilan aniqlanadi.Agar daraxtning chap qismdaraxtining barcha tugunlari qiymati ildiz tugunqiymatidan kichik, o’ng qismdaraxti barcha tugunlari qiymati katta bo’lsa,qidiruvdaraxtideyiladi. Bir xil qiymatli kalitlarga ruxsat etilmaydi. Qidiruv daraxtidaelementni kaliti bo’yicha qidirish uchun ildizdan chap qismdaraxt yoki o’ngqismdarxtga harakatlanish orqali amalga oshiriladi. Bunda qidirilayotgan kalitqiymatining ildiz qiymatiga nisbatan kichik yoki katta ekanligi e’tiborga olinadi.Kichik bo’lsa, chap qismdarxatdan, aks xolda o’ng qismdaraxtdan qidiriladi. Bunday
qidirish ro’yxatdan qidirishga nisbatan juda ham samarali, chunki, qidiruv vaqtidaraxt tugunlar sonining ikkilik logarifmga proportsional bo’lgan daraxt balandligibilan aniqanadi.Ideal muvozanatlashtirilgan daraxtning chap va o’ng tugunlari soni 1 tadanko’p tugunga farq qilmaydi.Chiziqli ro’yxatni har bir tuguni bitta ko’p bo’lmagan ko’rsatkichli binar daraxtshaklda ifodalash mumkin. Ro’yxat uchun o’rtacha qidirish vaqti ro’yxatuzunligining yarmiga teng bo’ladi.

Ikkilik qidirish algoritmi ishlash prinsipi
Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter bilan o’yin o’ynab ko’ramiz. O’yin shartlari quyidagicha:

Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish.
Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o’ylagan sondan katta yoki kichikligini aytadi.
Agar sizning taxminingiz kompyuter o’ylagan son bilan bir xil bo’lsa, o’yin tugaydi.

Xo’sh, bunda kamroq yo’l tutish uchun nima qilgan bo’lar edingiz?

Albatta, birinchi navbatda o’rtadagi sonni taxmin qilib ko’ramiz, ya’ni 50 ni

Aytaylik kompyuter bizga taxminimiz o’ylangan sondan kichikroq ekanligini aytdi. Demak, endi biz 50 va undan kichik barcha son o’ylangan sondan kichik ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar o’rtasidagi sonni olamiz, ya’ni 75 ni

Kompyuter bizga 75 o’ylangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham o’ylangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz o’ylangan sonni topishimiz mumkin.

Sonlar 100 ta bo’lgan holatda, biz har qanday tahminni ko’pi bilan 7 ta qadamda topishimiz mumkin bo’ladi.
Ikkilik qidirish algoritmi ham huddi shunday prinsipda ishlaydi!

Download 184.36 Kb.