Farg‘ona davlat universiteti


Ikkilik qidirish algoritmining ishlash prinsipi



Download 4,95 Mb.
bet5/8
Sana01.04.2022
Hajmi4,95 Mb.
#524004
1   2   3   4   5   6   7   8
Bog'liq
ALGORITM JAVOHIR

Ikkilik qidirish algoritmining ishlash prinsipi


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

  1. Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish.

  2. Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o'ylagan sondan katta yoki kichikligini aytadi.

  3. 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(6.4-rasm):

4-rasm. Ikkilik qidirish algoritmini ishlash prinsipi.

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.



5-rasm. Ikkilik qidirish algoritmining ikkinchi qadami.

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.



6-rasm. Ikkilik qidirish algoritmining keyingi qadamlari.

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!


Ikki algoritm uchun umumiy bo’lgan jihatlar, albatta, bu ularning qiladigan ishi va beradigan natijasida. Ya’ni ikki algoritm ham arraydan qandaydir elementni birorta shart asosida tekshiradi va element indeksini javob sifatida qaytaradi.
Bundan tashqari ikkala algoritmda ham ishlashi uchun qo’shimcha xotiradan joy talab qilinmaydi, ya’ni ikki algoritmning hotira bo’yicha murakkabliki O(1) ga teng.
Biz uchun esa hozir ularning farqli tomonlari muhimroq

Download 4,95 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




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