logo
Русский O'zbekcha
  1. Главная страница
  2. Рефераты
  3. Общий
  4. HAQIQIY IKKILIK QIDIRUV

HAQIQIY IKKILIK QIDIRUV

Загружено в:

08.08.2023

Скачано:

0

Размер:

567.0 KB
Условия скачивания
“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN “HAQIQIY IKKILIK QIDIRUV” MAVZUSIDA TAYYORLAGAN KURS ISHI Mundarija Kirish…………………………………………………………………………….3 I.Asosiy qism 1.1.Graflar va ularning tasvirlanishi…………………………………………..4 1.2.Daraxt va ularni turlari………………………………………………….…11 1.3.Haqiqiy ikkilik qidruv algoritimi……………………………………...…..15 II. Dasturlashga oid 2.1.C++ dasturlash tilida ikkilik qidiruv algoritmi……………………………28 III.Xulosa………………………………………………………………………...34 IV.Foydalanilgan adabiyotlar……………………………………..………….…35 2 Kirish Qidiruv vazifasi dasturlashda eng keng tarqalgan vazifalardan biridir. Shuningdek, u ko'rib chiqilayotgan narsaning qo'llanilishini namoyish qilish uchun ajoyib imkoniyatdir. Qidiruv tizimi hamma sohada ishlatilishi sababli ma'lumotlar tuzilmalari kompyuterda bajarish ancha oson bo’ladi. Kompyuterda ma’lumotlarni topish maqsadida maxsus kod kiritilgan kompyuterga shu bilan bir qatorda global qidiruv tizimida ham huddi shu maqsadda va shunga o’xshash kod kiritilgan. Qidiruv mavzusida bir nechta asosiy o'zgarishlar mavjud va bu yerda % bilan ko'plab algoritmlar ishlab chiqilgan. Biz qiladigan asosiy taxmin quyidagi ma'lumotlar to'plami bo'lib, unda % qidiriladi. Berilgan qiymat belgilangan. Biz bu N elementlar to'plami deb faraz qilamiz massiv bilan ifodalanadi, deylik element Ob'ektlar odatda yozuvlar bo'lib, ularning maydonlaridan biri rol o'ynaydi kalit. Keyin vazifa kalit maydoni teng bo'lgan elementni topishdir berilgan x qiymati, shuningdek, qidiruv argumenti deb ataladi. Topilgan shartini qanoatlantiruvchi i indeksi boshqasiga murojaat qilishimizga imkon beradi. topilgan elementning maydonlari. Bizni faqat% ni topish muammosi qiziqtirgani uchun lekin qidiruv qilingan ma'lumotlar emas, biz buni taxmin qilamiz Element turi faqat kalitdan iborat, ya'ni uning o'zi kalit. Lineer qidiruv Agar ma'lumotlar haqida qo'shimcha ma'lumot bo'lmasa, unda aniq yechim% nie - qiymatni bosqichma-bosqich oshirib, massivdan ketma-ket o'ting massivning kerakli qiymat aniq bo'lmagan qismi. Bu yechim ma'lum% Stno chiziqli qidiruv sifatida. Qidiruv ikkita shartdan birida to'xtatiladi: 1. Element topildi, ya'ni ai = x. 2. Butun massiv skanerdan o‘tkazildi, lekin element topilmadi. 3 Asosiy qism Graflar va ularning tasvirlanishi Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha davrda to‘rtta , , va qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yichayagona ilmiy ish bo‘lib keldi. XIX asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo‘ldi. “Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda uchraydi. Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo. Grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar. Avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa ba’zi sodda tushunchalarni keltiramiz. qandaydir bo‘shmas to‘plam bo‘lsin. 4 Uning va elementlaridan tuzilgan ko‘rinishdagi barcha juftliklar (kortejlar) to‘plamini (to‘plamning o‘z-o‘ziga Dekart ko‘paytmasini) bilan belgilaymiz. Bundan buyon grafni belgilashda yozuv o‘rniga yozuvdan foydalanamiz. Grafning tashkil etuvchilarini ko‘rsatish muhim bo‘lmasa, u holda uni lotin alifbosining bitta harfi, masalan, bilan belgilaymiz. graf berilgan bo‘lsin. to‘plamning elementlariga grafning uchlari , to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi. Graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun , bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz. grafning ta’rifiga ko‘ra, bo‘sh kortej bo‘lishi ham mumkin. Agar bo‘sh bo‘lmasa, u holda bu kortej ( , ) ko‘rinishdagi juftliklardan 2 tashkil topadi, bunda bo‘lishi hamda ixtiyoriy juftlik kortejda istalgancha marta qatnashishi mumkin. juftlikni tashkil etuvchi va uchlarning joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin. Agar juftlik uchun uni tashkil etuvchilarning joylashishya’ni bo‘lsa, juftlikka yo‘naltirilmagan ( oriyentirlanmagan ) qirra (yoki, qisqacha, qirra ) deyiladi. Agar bu tartib muhim, ya’ni bo‘lsa, u holda juftlikka yoy yoki yo‘naltirilgan ( oriyentirlangan ) qirra deyiladi. kortejning tarkibiga qarab, uni yo grafning qirralari korteji , yo yoylari korteji , yoki qirralari va yoylari korteji deb ataymiz.Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi. graf elementlarining soni ( )ga tengdir, bu yerda grafning uchlari soni va bilan uning qirralari (yoylari) soni belgilangan. Grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida , yoki , yoki ko‘rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi: masalan, yoy uchun yoki , qirra uchun , yoy yoki qirra uchun (ya’ni uchlari ko‘rsatilmasdan bitta harf vositasida) ko‘rinishda. Graf yoyi uchun uning chetki uchlarini ko‘rsatish tartibi muhim ekanligini ta’kidlaymiz, ya’ni va yozuvlar 5 bir-biridan farq qiluvchi yoylarni ifodalaydi. Agar yoy ko‘rinishda ifodalangan bo‘lsa, u holda uning boshlang‘ich uchi , esa oxirgi uchi deb ataladi. Bundan tashqari, yoy ko‘rinishda yozilsa, u haqida uchdan chiquvchi ( boshlanuvchi ) va uchga kiruvchi ( uchda tugovchi ) yoy deb aytish ham odat tusiga kirgan. Qirra uchun uning yozuvidagi harflar joylashish tartibi muhim rol o‘ynamaydi va va elementlar qirraning uchlari yoki chetlari deb ataladi. Agar grafda yo qirra, yo yoy, yoki yoy topillsa, u holda va uchlar tutashtirilgan deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy bor bo‘lsa, u holda ular qo‘shni uchlar deb, aks holda esa, qo‘shni bo‘lmagan uchlar deb aytiladi. Grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlarni tutashtiruvchi qirraga ( yoyga ) insident , o‘z navbatida, qirra yoki yoy bu uchlarga insident deyiladi. Grafda ikkita qirra (yoy) umumiy chetga ega bo‘lsa, ular qo‘shni qirralar ( yoylar ) deyiladi. Shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi. Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni va qirralar ( yoylar ) soni ga qarab belgilanadi va bu holda grafni -graf deb ataydilar. Agar grafda kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan ( oriyentirlanmagan ) va faqat yo‘naltirilgan (oriyentirlangan) qirralardan (ya’ni, yoylardan) tashkil topgan bo‘lsa, u holda u yo‘naltirilgan ( oriyentirlangan ) graf deb ataladi. Oriyentirlangan graf, qisqacha, orgraf deb ham ataladi. Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar deb ataladi. Agar grafning (orgrafning) korteji tarkibida to‘plamdan olingan takrorlanuvchi elementlar bo‘lsa, u holda ular karrali yoki parallel 6 qirralar ( yoylar ) deb ataladi. Karrali qirralari yoki yoylari bo‘lgan graf multigraf deyiladi. Ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy), ya’ni grafning elementi sirtmoq deb ataladi. Sirtmoq, odatda, yo‘naltirilmagan deb hisoblanadi. Qirralari (yoylari) orasida sirtmoqlari bo‘lgan graf psevdograf deyiladi. Umumiy holda uchlar to‘plami va (yoki) qirralar (yoylar, qirra va yoylar) korteji cheksiz ko‘p elementli bo‘lishi mumkin. Bundan keyin to‘plam va kortej faqat chekli bo‘lgan graflarni qaraymiz. Bunday graflar chekli graflar deb ataladi.Hech qanaqa qirra (yoy) bilan bog‘lanmagan uch yakkalangan ( ajralgan , xolis , yalong‘och ) uch deb ataladi. Faqat yakkalangan uchlardan tashkil topgan graf (ya’ni, grafda qirralar va yoylar bo‘lmasa) nolgraf yoki bo‘sh graf deb ataladi. Uchlari soni ga teng bo‘lgan bo‘sh grafni yoki kabi belgilash qabul qilingan. Istalgan ikkita uchlari qo‘shni bo‘lgan sirtmoqsiz va karrali qirralarsiz oriyentirlanmagan graf graf deb ataladi. Uchlari soni ga teng bo‘lgan to‘la graf bilan belgilanadi. Ravshanki , grafning qirralar soni bo ‘ ladi . Agar orgrafning istalgan ikkita uchini har bir yo ‘ nalishda tutashtiruvchi faqat bittadan yoy mavjud bo ‘ lsa , u holda unga to ‘ la orgraf deb ataladi . Ravshanki, to‘la grafdagi qirralarning har birini ikkita (yo‘nalishlari bir-biriga qarama-qarshi bo‘lgan) yoylarga almashtirilsa, natijada to‘la orgraf hosil bo‘ladi. Shuning uchun, to‘la orgrafdagi yoylar soni oriyentirlanmagan to‘la grafdagi qirralar sonidan ikki baravar ko‘pdir, ya’ni uchlari ta bo‘lgan to‘la orgrafdagi yoylar soni bo‘ladi. Agar grafning uchlariga qandaydir belgilar, masalan, sonlari mos qo‘yilgan bo‘lsa, u belgilangan graf deb ataladi. Agar va graflarning uchlari to‘plamlari, ya’ni va to‘plamlar orasida uchlarning qo‘shnilik munosabatini saqlaydigan o‘zaro bir qiymatli moslik o‘rnatish mumkin bo‘lsa, u holda va graflar izomorf graflar deb ataladi. Bu ta’rifni quyidagicha ham ifodalash mumkin: agar va ularga mos bo‘lgan ( 7 , ) uchun ( , ) bo‘lsa, u holda va graflar izomorfdir. Agar izomorf graflardan biri oriyentirlangan bo‘lsa, u holda ikkinchisi ham, albatta, oriyentirlangan bo‘lishi va ulardagi mos yoylarning yo‘nalishlari ham bir-birlariga mos bo‘lishlari shart. Graf uchiga insident qirralar soni shu uchning lokal darajasi , yoki, qisqacha, darajasi , yoki valentligi deb ataladi. Grafdagi uchning darajasini bilan belgilaymiz. Sirtmoqqa insident bo‘lgan uchning darajasini aniqlashda shuni e’tiborga olish kerakki, qaralayotgan masalaga bog‘liq holda sirtmoqni bitta qirra deb ham, ikkita qirra deb ham hisoblash mumkin. Ravshanki, ajralgan uchning darajasi nolga teng. Darajasi birga teng uch chetki (yoki osilgan ) uch deb ataladi. Chetki (osilgan) uchga insident qirra ham chetki (yoki osilgan ) qirra deb ataladi. Agar grafning barcha uchlari bir xil darajaga ega bo‘lsa, u holda bunday graf darajali regulyar graf deb ataladi. Uch darajali regulyar graf kubik (yoki uch valentli ) graf deb ataladi. graf nol darajali regulyar graf ekanligini, esa () darajali regulyar graf ekanligini ta’kidlaymiz. Ko‘rinib turibdiki , oriyentirlanmagan grafda barcha uchlar darajalarining yig‘indisi qirralar sonining ikki baravariga teng juft son bo‘ladi, chunki qirralarni sanaganda har bir qirra hisobda ikki marta qatnashadi. Shunday qilib, XVIII asrdayoq L. Eyler tomonidan isbotlangan quyidagi tasdiq o‘rinlidir. 1- lemma (“ko‘rishishlar” haqida). Ixtiyoriy oriyentirlanmagan grafda barcha uchlar darajalari yig‘indisi qirralar sonining ikki baravariga teng. Agar grafning uchlar to‘plamini o‘zaro kesishmaydigan shunday ikkita qism to‘plamlarga (bo‘laklarga) ajratish mumkin bo‘lsaki, grafning ixtiyoriy qirrasi bu to‘plamlarning biridan olingan qandaydir uchni ikkinchi to‘plamdan olingan biror uch bilan tutashtiradigan bo‘lsa, u holda bunday graf ikki bo‘lakli graf ( bixromatik yoki Kyonig grafi ) deb ataladi. Ta’rifdan ko‘rinib turibdiki, ikki bo‘lakli grafning har bir bo‘lagidagi ixtiyoriy ikkita uchlar qo‘shni bo‘la olmaydi. Biror bo‘lagida faqat bitta uch bo‘lgan to‘la ikki bo‘lakli graf yulduz deb ataladi. Agar ikki bo‘lakli grafning turli bo‘laklariga tegishli istalgan ikkita uchi qo‘shni 8 bo‘lsa, u holda bu graf to‘la ikki bo‘lakli graf deb ataladi. To‘la ikki bo‘lakli grafni bilan belgilaymiz, bu yerda va bilan grafning bo‘laklaridagi uchlar sonlari belgilangan. graf uchun va bo‘lishi ravshan, bu yerda – grafning uchlari soni, – uning qirralari soni. Grafning ikki bo‘lakli graf bo‘lishi haqidagi ba’zi qo‘shimcha ma’lumotlar (Kyonig teoremasi) ushbu bobning 4- paragrafida keltirilgan. Graflar ustida amallar . Graflar ustida turli amallar bajarish mumkin. Masalan, graflarning birlashtirish, biriktirish, ko’paytirish, grafni qismlarga ajratishva hokazo. Eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini keltirsa bo’ladi. Bu amalni qo’llash berilgan grafning uchlari to’plamidan biror element yo’qotishni anglatadi.Natijada uchlari soni 1 taga kam yangi graf paydo bo’ladi. Bu amalni uchlari soni ikkitadan kam bo’lmagan graflarga qo’llash mumkin bo’lib, uni bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu uchga intsident bo’lgan barcha qirralar ham olib tashlanadi.Eng sodda amallar qatoriga grafdan qirrani olib tashlash amalini kiritish mumkin. Bu amalga ko’ra, berilgan grafning qirralari to’plamidan birorta element olib tashlanadi. Berilgan grafda qirralarini olib tashlashda shu qirraga intsident uchlarni grafda qoldirish ham, yo’qotish ham mumkin. Agar va grafning barcha qirralari grafning ham qirralari bo’lsa bo’lsa, u holda graf grafning qism grafi deyiladi. Agar graf karrali qirralarga ega bo’lmasa u holda uchlari grafning barcha uchlaridan iborat bo’lgan shunday yagona graf mavjudki , grafdagi barcha juft uchlar faqat va faqat grafda qo’shni bo’lmagandagina qo’shnidir. Bunday graf berilgan grafning to’ldiruvchi grafi deyiladi. Berilgan graf uchun to’ldiruvchi grafni qurish jarayonini ham graflar ustida bajariladigan amallar qatoriga qo’shish mumkin. graf uchun to’ldiruvchi grafni qurish amalini qo’llash natijasida graf hosil bo’ladi.munosabatni isbotlash mumkin. Graflar ustida shunday amallarni bajarish mumkin, ular elementlari soni berilgan grafdagidan ko’proq bo’lgan boshqa graflarning hosil bo’lishiga olib keladi. Bunday amallar qatoriga uchni qo’shish amali yoki qirrani qo’shish amalini kiritish mumkin. 9 Grafga yangi uchni qo’shishni turli usul bilan amalga oshirish mumkin. Masalan, yangi uchni berilgan grafda qo’shish shu grafning va uchlariga intsident bo’lgan qandaydir qirrasiga qo’shish orqali quyidagicha 2 bosqichda bajarilishi mumkin qirra berilgan grafdan olib tashlanadi. 1.Hosil bo’lgan grafga ikkita yangi qirralar va uchlarida intsident qirra hamda va uchlarga intsident qirra qo’shiladi. Bu jarayon grafda qirraga darajasi ikki bo’lgan yangi uchni qo’shish yoki qirrani 2 ga bo’lish amali deb ataladi. 2.Agar graf grafdan qirrani ikkiga bo’lish amali chekli marta ketma- ket qo’llash vositasida hosil qilingan bo’lsa, u holda graf grafning bo’linish grafi deyiladi. Bo’linish graflari izomorf bo’lgan graflar gomeomorf graflar deyiladi. Ushbu shaklda tasvirlangan graflar izomorf emas, lekin ular gomeomorf, chunki bu graflarning har biri ushbu Shaklda tasvirlangan bo’linish grafga ega. Bizga va graflar berilgan bo’lsin. Uchlari to’plami va qirralari korteji kabi aniqlangan grafga va graflarning birlashmasi (uyushmasi) deyiladi va kabi belgilanadi. Misol: uchlari to’plamlari kesishadigan graflarning birlashmasi quyidagi chhizmada tasvirlangan Agar birlashtirilayotgan graflarning uchlari to’plamlari kesishmasa, u holda bu graflarning birlashmasi dizyunkt birlashma deyiladi. Graflarni biriktirish amalini qaraymiz. Bizga va graflar berilgan bo’lsin va graflar 10 birlashtirilishi hamda grafning har bir uchi grafning har bir uchi bilan qirra vositasida tutashtirilishi natijasida hosil bo’lgan graf va graflarning birikmasi (tutashmasi) deyiladi va kabi belgilanadi. Agar uchlari to’plamlari kesishmasi bo’sh bo’lmagan graflarni birlashtirish zarur bo’lsa , u holda hal qilinayotgam masala xossalarini e’tiborga olish kerak. Graflarni ko’paytirish amali. Bizga va graflar berilgan bo’lsin. Uchlari to’plami bo’lgan grafning qirralari kortejini quyidagicha aniqlaymiz: agar va yoki va bo’lsa , u holda bo’ladi, bu yerda va bunday usul bilan hosil bo’lgan graf graflarning ko’paytmasi deyiladi va kabi belgilanadi. Graflarning ko’paytmasi ta’rifigaasosan, berilgan va graflarning ko’paytmasihisoblangan grafdagi uchlari yoki ko’rinishdagi juftliklardan iborat, bu yerda uchlar faqat va faqat shu holda qo’shni bo’ladiki, qachonki bu uchlarni (juftliklarni) tashkil qiluvchi elementlarning biri unga mos element bilan ustma-ust tushgan holda boshqa elementlarda o’z grafiga qo’shni bo’lishsa, bu yerda munosabatlardanva bo’lishi kelib chiqadi. Dekart ko’paytmalar bilan bog’liq tuzilmalar ustida bajariladigan amallar boshqalardan o’ziga xosligi bilan ajralib turadi. Bu o’ziga xoslik graflarni ko’paytirish amalida namoyon bo’ladi. Graflar ko’paytmasida qatnashgan bironta grafning qirralari katreji bo’sh bo’lsada, ko’paytirish amalini qo’llash natijasida hosil bo’lgan grafning qirralari kotreji bo’sh bo’lmasligi ham mumkin. Xaqiqatan ham, yuqorida keltirilgan graflarningko’paytmasi ta’rifidan kelib chiqadiki, agar graf va graflarning ko’paytmasi, ya’ni bo’lsa, u holda bo’ladi va kortej elementlari bilan birlashma elementlari orasida bir qiymatli moslik mavjud. Graflarni ko’paytirish amalini qayta takror qo’llash usuli bilan graflar nazariyasining muhim sinfini tashkil etuvchi o’lchovli kublarni aniqlash mumkin. o’lchovli kubuchlari soni ikkiga teng bo’lgan to’la graf yordamida quyidagi rekkurent formula bilan aniqlanadi. 1.2 Daraxt va ularni turlari Ikkilik qidiruv daraxti ( BST ), shuningdek, buyurdi yoki saralangan ikkilik daraxt , a ildiz otgan ikkilik daraxt uning ichki tugunlari har birida tugmachaning 11 chap pastki daraxtidagi barcha tugmachalardan kattaroq va uning o'ng pastki daraxtidagi tugmachalardan kichikroq kalit saqlanadi. Ikkilik daraxt - bu bir turi ma'lumotlar tuzilishi raqamlar kabi ma'lumotlarni uyushgan ravishda saqlash uchun. Ikkilik qidiruv daraxtlari imkon beradi ikkilik qidirish tezkor qidirish, ma'lumotlar elementlarini qo'shish va olib tashlash uchun va amalga oshirish uchun ishlatilishi mumkin dinamik to'plamlar va qidiruv jadvallari . BST-dagi tugunlarning tartibi shuni anglatadiki, har bir taqqoslash qolgan daraxtning yarmini o'tkazib yuboradi, shuning uchun butun izlanish talab etiladi vaqt bilan mutanosib The ikkilik logarifma daraxtda saqlanadigan narsalar sonidan. Bu juda yaxshi chiziqli vaqt (saralanmagan) qatorda kalitlarga ko'ra elementlarni topish uchun talab qilinadi, ammo tegishli operatsiyalardan sekinroq xash jadvallar . Ikkilik qidiruv daraxti - bu ildiz otgan ikkilik daraxt ichki tugunlari har birida kalitni (va ixtiyoriy ravishda bog'liq qiymatni) saqlaydi va har birida odatda belgilangan ikkita taniqli pastki daraxtlar mavjud chap va to'g'ri . Daraxt qo'shimcha ravishda qoniqtiradi ikkilik qidirish xususiyati: har bir tugundagi kalit chap pastki daraxtda saqlangan har qanday tugmachadan kattaroq yoki teng, o'ng pastki daraxtda saqlangan har qanday tugmachadan kichik yoki teng. [1] :287 Daraxtning barglarida (yakuniy tugunlarida) hech qanday kalit yo'q va ularni bir-biridan ajratib turadigan tuzilishga ega emas. Ildizida 8 dona bo ' lgan 9 va chuqurlik 3 o ' lchamdagi ikkilik qidiruv daraxti Barglari chizilmaydi . Ko'pincha, har bir tugun tomonidan ko'rsatilgan ma'lumot bitta ma'lumot elementi emas, balki yozuvdir. Biroq, ketma-ketlik maqsadida tugunlar o'zlarining tegishli yozuvlarining biron bir qismiga emas, balki ularning kalitlariga qarab taqqoslanadi. Ikkilik qidiruv daraxtlarining boshqa ma'lumotlar tuzilmalaridan ustunligi shu bilan bog'liqdir algoritmlarni saralash va qidirish algoritmlari kabi tartibda o'tish juda samarali bo'lishi mumkin. Ikkilik daraxtda odatdagi ikkilik qidiruv daraxtini qanday kiritish mumkinligi C ++ : bekor kiritmoq ( Tugun *& ildiz , int kalit , int qiymat ) { agar ( ! ildiz ) ildiz = yangi Tugun ( kalit , qiymat ); boshqa agar ( kalit == ildiz -> kalit ) ildiz -> qiymat = 12 qiymat ; boshqa agar ( kalit < ildiz -> kalit ) kiritmoq ( ildiz -> chap , kalit , qiymat ); boshqa // key> root-> key kiritmoq ( ildiz -> to'g'ri , kalit , qiymat );} Shu bilan bir qatorda, rekursiv bo'lmagan versiya shu kabi qo'llanilishi mumkin. Qaerdan kelganligimizni kuzatish uchun ko'rsatgichdan-ko'rsatkichga foydalanish kodni daraxtning ildiziga tugunni kiritishi kerak bo'lgan holatni aniq tekshirish va ko'rib chiqishdan qochishga imkon beradi: [3] bekor kiritmoq ( Tugun ** ildiz , int kalit , int qiymat ) { Tugun ** yurish = ildiz ; esa ( * yurish ) { int kurka = ( * yurish ) -> kalit ; agar ( kurka == kalit ) { ( * yurish ) -> qiymat = qiymat ; qaytish ; } agar ( kalit > kurka ) yurish = & ( * yurish ) -> to'g'ri ; boshqa yurish = & ( * yurish ) -> chap ; } * yurish = yangi Tugun ( kalit , qiymat );} Yuqorisida, yuqoridagi halokatli protsessual variant daraxtni joyida o'zgartiradi. U faqat doimiy yig'ma bo'shliqdan foydalanadi (va takrorlanadigan versiya ham doimiy stack maydonidan foydalanadi), lekin daraxtning oldingi versiyasi yo'qoladi. Shu bilan bir qatorda, quyidagi kabi Python Masalan, biz kiritilgan tugunning barcha ajdodlarini qayta tiklashimiz mumkin; asl daraxt ildiziga har qanday havola haqiqiy bo'lib qoladi va bu daraxtni a qiladi doimiy ma'lumotlar tuzilishi : def binary_tree_insert ( tugun , kalit , qiymat ): agar tugun == Yo'q : qaytish NodeTree ( Yo'q , kalit , qiymat , Yo'q ) agar kalit == tugun . kalit : qaytish NodeTree ( tugun . chap , kalit , qiymat , tugun . to'g'ri ) agar kalit < tugun . kalit : qaytish NodeTree ( binary_tree_insert ( tugun . chap , kalit , qiymat ), tugun . kalit , tugun . qiymat , tugun . to'g'ri ) qaytish NodeTree ( tugun . chap , tugun . kalit , tugun . qiymat , binary_tree_insert ( tugun . to'g'ri , kalit , qiymat )) Qayta qurilgan qismdan foydalaniladi O (log n ) o'rtacha holatda bo'sh joy va O ( n ) eng yomon holatda. Ikkala versiyada ham ushbu operatsiya eng yomon holatda daraxt balandligi bilan mutanosib vaqt talab qiladi, ya'ni O (log n ) barcha daraxtlar bo'yicha o'rtacha holatda vaqt, lekin O ( n ) eng yomon holatda vaqt. Ikkilik qidirish daraxtlari asosiy hisoblanadi ma'lumotlar tuzilishi kabi mavhum ma'lumotlar tuzilmalarini qurish uchun foydalaniladi to'plamlar , multisets va assotsiativ massivlar . 13 Ikkilik qidirish buyurtma munosabatini talab qiladi, unga ko'ra har bir element (element) a ma'nosida boshqa elementlar bilan taqqoslanishi mumkin jami oldindan buyurtma . Elementning taqqoslashda samarali bo'lgan qismi uning kalit deb ataladi . Ikki nusxada bo'ladimi, ya'ni. e. daraxtda bir xil kalitga ega bo'lgan turli xil elementlarga ruxsat beriladi yoki yo'q, buyurtma munosabatlariga bog'liq emas, balki faqat dasturga bog'liq. B daraxtining ta'rifi B- da r a xt - bu m uv oz an at l i M - y o' l d ar a xt i va u m u vo za na t l i na vl i da r a xt s i f at i d a ha m t an i l g an . B u t u gu nl ar i nor der t r a ve r s al as os i d a t as hk i l e t i l g an i kk i l i k q i d i r u v dar ax t i ga o' xs ha yd i . B da r a xt i ni ng k os m i k m ur a kk ab l i gi O ( n) di r . Ki r i t i sh va o' ch i r i sh va qt i n i n g m ur ak ka bl i g i O ( l o g n) . B d ar a xt i uc hu n t o' g' r i b o' l i sh i k er a k bo 'l ga n b a' zi sh ar t l ar m av j u d:  Daraxtning balandligi iloji boricha minimal bo'lishi kerak.  Daraxt barglari ustida hech qanday bo'sh daraxt bo'lmasligi kerak.  Daraxtning barglari bir xil darajada bo'lishi kerak.  Barcha tugunlarda ta'til tugunlaridan tashqari eng kam bola bo'lishi kerak. M tartibidagi B daraxtining xususiyatlari  Har bir tugunda maksimal M bolalar soni va minimal M / 2 bolalar soni yoki 2 dan maksimalgacha bo'lgan har qanday son bo'lishi mumkin.  Har bir tugunda maksimal M-1 tugmachalari bo'lgan bolalarga qaraganda bitta tugmacha kam.  Klavishlarning joylashishi tugunlar ichida ma'lum bir tartibda. Kalitning chap tomonida joylashgan subtree-dagi barcha tugmachalar kalitning oldingilari va kalitning o'ng tomonida joylashganlari vorislar deb ataladi.  To'liq tugunni kiritish paytida daraxt ikki qismga bo'linadi va ota-ona tuguniga o'rtacha qiymati bo'lgan kalit qo'yiladi.  Birlashtirish jarayoni tugunlar o'chirilganda amalga oshiriladi. B d ar a xt i i k ki l i k va i kk i l i k qi di r uv d ar ax t l ar i u st i d a i sh l a t i l a di , bu ni ng as os i y sa ba bi CP U pr ot se s so r y uq or i o' t k az uv ch an l i k ka na l l ar i 14 bi l a n k es hg a u l a ng an xo t i r a i ye r ar xi ya si di r , pr o t s es s or di sk ka p as t o' t k az uv ch an l i k k an al i or qa l i u l a na di . Ikkilik daraxtning ta'rifi . I kk i l i k d ar a xt - b u dar ax t t u gu nl ar i u ch un en g ko 'p i k ki t a ko 'r sa t g i c hg a e ga bo 'l ga n da r a xt t u zi l i s hi . Bu s hu ni an gl at ad i k i , t ug un ni ng e ng y uq or i d ar aj as i 2 g a t en g va u e r d a no l yo ki bi r da r a j a l i t ug un h am b o' l i sh i m um k i n . Ikkilik qidiruv ishlaydi logaritmik vaqt ichida eng yomon holat , qilish taqqoslashlar, qaerda - bu massivdagi elementlar soni. Ikkilik qidiruv tezroq chiziqli qidiruv kichik massivlardan tashqari. Biroq, ikkilik qidiruvni amalga oshirish uchun birinchi navbatda qatorni saralash kerak. Ixtisoslashgan ma'lumotlar tuzilmalari kabi tezkor qidiruv uchun mo'ljallangan xash jadvallar , ikkilik qidiruvdan ko'ra samaraliroq qidirish mumkin. Shu bilan birga, ikkilik qidiruv yanada kengroq muammolarni hal qilish uchun ishlatilishi mumkin, masalan, qatorda yo'q bo'lsa ham, maqsadga nisbatan massivda keyingi eng kichik yoki eng katta elementni topish. Ikkilik qidiruv algoritmi Ikki tomonlama qidiruv algoritimining vizualizatsiyasi, bu yerda 7 maqsad qiymatidir Sinf Qidiruvalgoritmi  Ma’lumotlar tarkibi Array  Eng yomon ishlash O(log n)  Eng yaxshi holati ishlash O(1)  O’rtacha ishlash O(log n)  Eng yomoni kosmik murakkablik O(1) 15 1.3.Haqiqiy ikkilik qidruv algoritmi Haqiqiy ikkilik qidiruv (inglizcha Bisection usuli ) - monotonik haqiqiy funktsiyaning berilgan qiymati uchun argumentni topish algoritmi. Keling, ikkilik qidiruv g'oyasini qo'llaymiz . Funktsiyaning qiymati berilgan qiymatdan aynan katta va to'liq kichik bo'lgan shunday chegaralarni tanlaylik. Keling, ushbu segmentning o'rtasida qiymat tanlaylik. Agar u belgilanganidan kamroq bo'lsa, biz chap chegarani segmentning o'rtasiga o'tkazamiz. Aks holda, biz o'ng chegarani o'zgartiramiz. Keyinchalik, chegaralarni toraytirish jarayonini takrorlaymiz. Qachon to'xtash kerak degan savol tug'iladi. Buning bir necha usullari mavjud. Qidiruv uchun segment chegarasini tanlash. Birinchidan, chap chegarani topamiz, ixtiyoriy salbiy nuqtani tanlang (masalan 1-bitta ). Undagi qiymat belgilangan qiymatdan kattaroq ekan, biz uni ikki barobarga oshiramiz. To'g'ri chegarani topish uchun o'zboshimchalik bilan ijobiy nuqtani tanlang (masalan bitta bitta ). Funktsiyaning bu nuqtadagi qiymati berilgan qiymatdan kichik bo'lsa, biz uni ikki barobarga oshiramiz. double findLeftBoard (C: double ): x = -1 esa f (x)> C x = x * 2 x qaytaring double findRightBoard (C: double ): x = 1 esa f (x) <C 16 x = x * 2 x qaytaring double binSearch (C: double ): chap = chap taxtani topish (C) o'ng = findRightBoard (C) while o'ng - chap <eps // Bu erda boshqa chiqish shartidan foydalanish mumkin o'rta = (chap + o'ng) / 2 agar f (o'rtada) <C chap = o'rta boshqa o'ng = o'rta qaytish (chap + o'ng) / 2 Keling, bizga monotonlik beraylik ff va ma'nosi CC ... Biz ikkita boshlang'ich nuqtani tanlaymiz va f(xbitta) < Cf(xbitta)<C , a f(x2) > Cf(x2)>C ... Ular orqali to‘g‘ri chiziqni kesib o‘tuvchi to‘g‘ri chiziq o‘tkazamiz y= Cy=C nuqtada (x3, C) (x3,C) ... Endi nuqta o'rniga xbittaxbitta va x2x2 ochkolarni olaylik x3x3 va x2x2 , va xuddi shu amalni bajaring va hokazo, ballarni oling xn + 1xn+bitta va xnxn , xayr | xn - 1-xn| >e|xn-bitta-xn|>e ... Biz har bir keyingi qiymatni hisoblaymiz xn + 1xn+bitta formuladan foydalanib: xn + 1=xn - 1+( C- f(xn) ) ⋅ (xn-xn - 1)f(xn) - f(xn - 1)xn+bitta=xn-bitta+(C- f(xn)) ⋅ (xn-xn-bitta)f(xn)-f(xn-bitta) Funksiyaning nollarini topish ( C= 0 )(C=0) : xn + 1=xn - 1-f(xn) ⋅ (xn-xn - 1)f(xn) - f(xn - 1)xn+bitta=xn-bitta-f(xn) ⋅ (xn-xn- bitta)f(xn)-f(xn-bitta) 17 qo'sh qidiruv (a: double , b: double , eps: double ): // Bu erda a chap chegara, b o'ng esa | a - b | > eps a = b - (b - a) * f (b) / (f (b) - f (a)) b = a - (a - b) * f (a) / (f (a) - f (b)) qaytish b Ma lumotlar tuzilmasi va algoritmlarda ikkilik qidirish haqidaʼ Ikkilik qidirish — Ο (log n) vaqti murakkabligi bilan tezkor qidiruv algoritmi. Ushbu qidirish algoritmi bo linish (divide) va yengish (conque) prinsipi asosida ʻ ishlaydi. Ushbu algoritm to g ri ishlashi uchun ma lumotlar to planishi tartiblangan ʻ ʻ ʼ ʻ shaklda bo lishi kerak. ʻ Ikkilik qidirish to plamning ko p qismini o rtasini ʻ ʻ ʻ taqqoslash orqali ma lum bir narsani qidiradi. Agar mos kelsa, unda element indeksi ʼ qaytariladi. Agar o rta qism elementdan kattaroq bo lsa, u holda ushbu element ʻ ʻ o rta qismning chap tomonidagi pastki qatorda qidiriladi. ʻ Aks holda, element o rta ʻ elementning pastki qismidagi pastki qatorda qidiriladi. Ushbu jarayon pastki massivda, shuningdek sub-massivning kattaligi nolga tushguncha davom etadi. Ikkilik qidirsh qanday ishlaydi? Ikkilik qidirish ishlashi uchun maqsad qatorini tartiblash kerak. Ikkilik qidirish jarayonini tasvirli misol yordamida bilib olamiz. Quyidagi tartiblangan massivimiz bo lib, ikkilik qidirishdan foydalanib, 31 ʻ qiymatni qidirish kerakligini taxmin qilaylik. Birinchidan, ushbu formuladan foydalanib, massivning yarmini aniqlaymiz: mid = low + (high - low) / 2 18 Bu yerda, 0 + (9 - 0 ) / 2 = 4 (4.5 ning butun qiymati). Shunday qilib, 4 qatorning o rtasida.ʻ Endi biz 4-chi joyda saqlangan qiymatni, ya ni qidirilayotgan qiymat bilan ʼ taqqoslaymiz, ya ni 31-chi joyda 27-ning qiymati mos kelmasligini aniqladik. ʼ Qiymat 27 dan katta bo lsa va bizda tartiblangan qator mavjud bo lsa, biz shuni ʻ ʻ ham bilamizki, maqsad qiymati massivning yuqori qismida bo lishi kerak. ʻ Biz pastligimizni + 1 o rtasiga o zgartiramiz va yana yangi o rtacha qiymatni ʻ ʻ ʻ topamiz. low = mid + 1 mid = low + (high - low) / 2 Bizning yangi o rtamiz endi 7 ga chiqdi. Biz 7-joyda saqlangan qiymatni ʻ maqsadli qiymatimiz 31 bilan taqqoslaymiz. 7-joyda saqlangan qiymat mos kelmaydi, aksincha biz qidirayotgan narsadan ko proqdir. Shunday qilib, qiymat ushbu joyning pastki qismida bo lishi kerak. ʻ ʻ 19 Shunday qilib, biz yana o rtani hisoblaymiz. Bu safar 5 ga.ʻ Biz 5-chi joyda saqlangan qiymatni maqsadli qiymatimiz bilan taqqoslaymiz. Bu match ekanligini aniqladik. 31 maqsadli qiymat 5 manzilda saqlanadi degan xulosaga keldik. Ikkilik qidirish qidiriladigan qismlarni ikki baravar qisqartiradi va shu bilan juda kam sonlar uchun taqqoslash sonini kamaytiradi. Ikkilik qidirish algoritmlarining kodi quyidagicha ko rinishi kerak: ʻ Procedure binary_search A ← sorted array n ← size of array x ← value to be searched Set lowerBound = 1 Set upperBound = n while x not found if upperBound < lowerBound EXIT: x does not exists. set midPoint = lowerBound + ( upperBound - lowerBound ) / 2 if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x set upperBound = midPoint - 1 20 if A[midPoint] = x EXIT: x found at location midPoint end while end procedure "Bo'lib tashla va hukmronlik qil" nimani anglatadi Dasturlashda, bo'lib tashla va hukmronlik qil — bu algoritmik paradigma bo'lib, bu paradigmaning asosiy g'oyasi algoritmik masalalarni bosh masalaga o'xshash kichik qismlarga bo'lib tashlab, ularni rekursiv hal qilishdan iborat. Bu paradigmada masala qismlarga bo'linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo'lishi va bu bo'linish to'xtashi uchun asos holat bo'lishi kerak (Rekursiya esingizga tushib ketmadimi?). Barcha turdagi bo'lib tashla va hukmronlik qil algoritmlari 3 ta bosqich dan iborat bo'ladi: 1. Bo'lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o'xshash kichikroq masalalarga bo'lib chiqiladi. 2.Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi. 3.Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo'ladi. Shu sababli, bo'lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab qolish mumkin: bo'lib tashla, hukmronlik qil, birlashtir. Boshida tushunish ozroq qiyin bo'lishi tabiiy, shuning uchun bu paradigma g'oyasini tasvirlab berishga harakat qilamiz. Oddiy, bittagina qadamdan iborat bo'lib tashla va hukmronlik qil algoritmi qanday ishlashini ko'raylik: 21 Agar biz qadamlar sonini oshiradigan bo'lsak, paradigma tasviri quyidagicha ko'rinish oladi: Bo'lib tashla va hukmronlik qil paradigmasi asosiy masalalari Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi: 1. Ikkilik qidirish ( Binary Search ) 2. Merge Sort 22 3. Quick Sort 4. Eng yaqin ikki nuqta ( Closest two points ) 5. Strassen ko'paytirishi ( Strassen multiplication ) 6. Karatsuba algoritmi ( Karatsuba algorithm ) 7. Cooley-Tukey algoritmi ( Cooley-Tukey Algorithm ) Bo'lib tashla va hukmronlik qil paradigmasi afzalliklari  qiyin masalalarni osonlik bilan yechishga imkon beradi  bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko'ra tezroq ishlaydi. Masalan: oddiy saralash bo'lgan Bubble Sortning tezligi O(n²) bo'lsa, MergeSortniki O(n*logn)  bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday o'zgarishsiz ishlatish mumkin  bunday algoritmlarni qo'llashda xotira keshidan unumli foydalanish mumkin. Chunki masalalar bo'linish jarayonida shunday kichik qismlarga ajraladiki, ularni keshni o'zida turib yechish mumkin bo'ladi.  haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan, ko'paytirish algoritmlarida) Algoritm qadamlari.Algoritm qanday ishlashini tushundingiz degan umiddaman. Endi uning qadamlariga o'tadigan bo'lsak. Eslatma: Ikkilik qidirish algoritmi to'g'ri ishlashi uchun array saralangan bo'lishi shart! Bizda n ta elementli saralangan massiv bor va biz undan x elementni qidirmoqdamiz. Biz qidirish chegarasini belgilash uchun l (left) va r (right) ko'rsatkichlardan foydalanamiz. Ular array indekslarini ko'rsatib 23 turadi. mid o'zgaruvchi bizda qidirilayotgan sohaning o'rtadagi elementi indeksini ko'rsatadi 1. Avvaliga l = 0 va r=n-1 bo'ladi (butun boshli array) 2. O'rtadagi element indeksi hisoblanadi: mid = (l + r)/2; 3. O'rtadagi element indeksi bilan qidirilayotgan son x solishtirib ko'riladi 4. Agar son mos kelsa, algoritm shu joyida to'xtaydi. 5. Agar x o'rtadagi sondan katta bo'lsa, left ko'rsatkichni o'rtadan bitta keyingi elementga suramiz: l=mid + 1; 6. Agar x o'rtadagi sondan kichik bo'lsa, right ko'rsatkichni o'rtadan bitta oldingi elementga suramiz: r=mid — 1; 7. 2-qadamga qaytiladi. Ikkilik qidirish algoritmi har bir qadamda n ni ikki baravarga kamaytirgani uchun algoritm ishlash tezligi O(logn) hisoblanadi. Ketma-ket qidiruv algoritmi. Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz yoki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda ma’lumotlar butun jadval bo’yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma-ket qarab chiqiladi. Massivda ketma-ket qidiruv (search o’zgaruvchi topilgan element tartib raqamini saqlaydi). Ketma-ket qidiruv algoritmi C++ tilida quyidagicha bo’ladi: int qidiruv(int key) { for (int i=0;i<n;i++)< p=""></n;i++)<> if (k[i]==key) { search = i;return search;} search = -1; 24 return search; }} Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. M min = 1, M max = n. Agar ma’lumotlar massiv yacheykasida bir xil ehtimollik bilan taqsimlangan bo’lsa, u holda M o’rt  (n + 1)/2 bo’ladi. Agar kerakli element jadvalda yo’q bo’lib, uni jadvalga qo’shish lozim bo’lsa, u holda yuqorida keltirilgan algoritmdagi oxirgi ikkita operator quyidagicha almashtiriladi . n=n+1; k[n-1]:=key; r[n-1]:=rec; search:=n-1; return search; Agar ma’lumotlar jadvali bir bog’lamli ro’yhat ko’rinishida berilgan bo’lsa , u holda ketma-ket qidiruv ro’yhatda amalga oshiriladi. Chiziqli bir bog’lamli ro’yhatdan key kalitga mos elementni ketma-ket qidiruv usuli yordamida izlab topish dasturi. Node *q=NULL; Node *p=lst; 25 while (p !=NULL){ if (p->k == key){ search = p; return search; } q = p; p = p->nxt; } Node *s=new Node;; s->k=key; s->r=rec; s->nxt= NULL; if (q == NULL){ s->nxt=lst; lst = s; } else q->nxt = s; search= s; return search; Ro’yhatli tuzilmaning afzalligi shundan iboratki , ro’yhatga elementni qo’shish yoki o’chirish tez amalga oshadi, bunda qo’shish yoki o’chirish element soniga bog’liq bo’lmaydi, massivda esa elementni qo’shish yoki o’chirish o’rta hisobda barcha elementlarning yarmini siljitishni talab qiladi. Ro’yhatda qidiruvning samaradorligi taxminan massivniki bilan bir xil bo’ladi. Teng bo’lish orqali qidiruv (ikkilik qidiruv) algoritmi . Faraz qilaylik, o’sish tartibida tartiblangan sonlar massivi berilgan bo’lsin. Ushbu usulning asosiy g’oyasi shundan iboratki , tasodifiy qandaydir A M element olinadi va u X qidiruv argumenti bilan taqqoslanadi. Agar A M =X bo’lsa, u holda qidiruv yakunlanadi; agar A M >X bo’lsa, u holda indekslari M dan katta bo’lgan barcha elementlar kelgusi qidiruvdan chiqarib yuboriladi. 26 M ixtiyoriy tanlanganda ham taklif qilinayotgan algoritm korrekt ishlaydi. Shu sababali M ni shunday tanlash lozimki, tadqiq qilinayotgan algoritm samaraliroq natija bersin , ya’ni uni shunday tanlaylikki, iloji boricha kelgusi jarayonlarda ishtirok etuvchi elementlar soni kam bo’lsin. Agar biz o’rtacha elementni, ya’ni massiv o’rtasini tanlasak yechim mukammal bo’ladi. Misol uchun butun sonlardan iborat, o’sish bo’yicha tartiblangan massivdan ikkilik qidiruv usuli yordamida key kalitga mos elementni izlash dasturini ko’rib chiqamiz. Dastur kodi: #include <iostream> using namespace std ; int main(){ int n;cout<<"n=";cin>>n; int k[n]; for(int i=0;i>k[i]; int key, search; cout<<"qidirilayotgan elementni kiriting=";cin>>key; int low = 0; while (low <= hi){ int mid = (low + hi) / 2;j++; if (key == k[mid]){ search = mid; cout<<"qidirilayotgan element "<<search+1<<" o’rinda="" turibdi="" va="" u="" "<<j<<"="" ta="" solishtirishda="" toplidi\n";<="" p=""></search+1<<"> system("pause"); 27 exit(0); } if (key < k[mid]) hi = mid - 1; else low = mid + 1; } search=-1; cout<<j<<" ta="" solishtirish="" amalga="" oshirildi="" va="" qidirilayotgan="" element="" topilmadi\n";<="" p=""></j<<"> system("pause"); } Dastur natijasi n=6 1 2 3 4 5 6 qidirilayotgan elementni kiriting=6 qidirilayotgan element 6 o'rinda turibdi va u 3 ta solishtirishda toplidi Qidiruv jadvalini qayta tartibga keltirish Umuman olganda, jadvalda har bir elementni qidirish ehtimolligini qandaydir bir qiymat bilan izohlash mumkin. Faraz qilaylik jadvalda qidirilayotgan element mavjud. U holda qidiruv amalga oshirilayotgan jadvalni diskret holatga ega tizim sifatida qarash mumkin hamda unda qidirilayotgan elementni topish ehtimolligi – bu tizim i-chi holati ehtimolligi p(i) deb olish mumkin. Dasturlashga oid 2.1. С ++ dasturlash tilida ikkilik qidruv Dasturlash tillari asosan maxsus so'z va gaplarning mantiqiy konstruktsiyasidan foydalanib dasturlar yaratish imkoniyatini beradi. Ob'ektga yo'naltirilgan yondashuvlar bir kunda o'ylab topilgan emas. Uning paydo bo'lishi dasturiy ta'minotning tabiiy rivojidagi navbatdagi pog’ona, xolos. Vaqt o'tishi bilan qanday uslublar ishlash uchun qulay, qaysinisi noqulay ekanini aniqlash oson bo'lib bordi. Eng muvaffaqiyatli, vaqt sinovidan o'tgan uslublarni o'zida mujassam etadi. 28 Dastlab dasturlash anchayin boshqotirma ixtiro bo'lib, u dasturchilarga dasturlarni kommutatsiya bloki orqali kompyuterning asosiy xotirasiga to'g’ridan- to'g’ri kiritish imkonini berdi. Dasturlar mashina tillarida ikkilik tasavvurda yozilar edi. Dasturlarni mashina tilid a yozishda tez-tez xatolarga yo'l qo'yilar, kodni kuzatib borish amalda deyarli mumkin emas edi. Bundan tashqari, mashina kodlaridagi dastur tushunish uchun g’oyat murakkab edi. Vaqt o'tishi bilan kompyuterlar tobora kengroq qo'llana boshlandi hamda yuqoriroq darajadagi protsedura tillari paydo bo'ldi. Bularning dastlabkisi FORTRAN tili edi. Biroq ob'ektga mo'ljallangan yondashuv rivojiga asosiy ta'sir keyinroq paydo bo'lgan. Protsedura tillari dasturchiga axborotga ishlov berish dasturini pastroq darajadagi bir nechta protseduraga bo'lib tashlash imkonini beradi. Keyinchalik ob'ektga yo'naltirilgan dasturlash yo'nalishiga asos solindi. Ushbu kurs ishi mavzusi “Sinflar orasidagi munosabatlar” bo'lib, unda nazariy ma'lumotlar va Jawa muhitida dasturiy vosita yaratiladi. Yaratilgan dastur “Kutubxona” va “Kitob” asosida sinflar ishlab chiqish va ular orasidagi munosabatlarni o'rnatishdan iborat. “Kitob” sinfi yordamida har bir Kitob ob'ektlari tashkil etiladi va ularning qiymatlari kiritilib natijalari olinadi. Bu yerda oqimdan qiymat qabul qiluvchi o‘zgaruvchining nomi. int n; cout << ” n = ”; cin >> n; Butun turdagi n o‘zgaruvchisi kiritilgan qiymatni o‘zlashtiradi [3, Bir paytning o‘zida probel vositasida bir nechta va har xil turdagi qiymatlarni oqimdan kiritish mumkin. Qiymat kiritish “Enter” tugmasini bosish bilan tugaydi. Agar kiritilgan qiymatlar soni o‘zgaruvchilar sonidan ko‘p bo‘lsa, «ortiqcha» qiymatlar bufer xotirada saqlanib qoladi. int x, y; float z; cin >> x >> y >> z; Shuni qayd etish kerakki, oqimga qiymat kiritishda probel ajratuvchi hisoblanadi. Haqiqiy sonning butun va kasr qismlari ‘.’ belgisi bilan ajratiladi. “Prefiks” yoki “postfiks” amal tushunchasi faqat qiymat berish bilan bog‘liq ifodalarda o‘rinli. x = 5; y = ++x; Ushbu misolda x ning qiymati besh. y ga x ning qiymatini yuklashdan oldin pre-inkrement amali qo‘llaniladi, x ning qiymati oltiga 29 o‘zgaradi, so‘ngra y o‘zgaruvchisiga olti yuklanadi. Natijada, x ning qiymati ham, y ning qiymati ham oltiga teng bo‘ladi. x = 5; y = x++; Ushbu misolda x ning qiymati besh. y ga x ning qiymatini yuklash jarayonida post-inkrement amali qo‘llaniladi, x ning qiymati y o‘zgaruvchisiga yuklanadi, so‘ngra x ning qiymati bittaga oshiriladi. Natijada, x ning qiymati - olti, y ning qiymati - beshga teng bo‘ladi. Inkrement va dekrement amallarini murakkab ifodaning ichida ham ishlatish mumkin. Faqat bunda tushunarli bo‘lishi uchun inkrement va dekrement amallarini qavs ichiga olish maqsadga muvofiq. a = 5; b = 2 + (++a); Birinchi ifodada a o‘zgaruvchisiga besh soni yuklanadi. Keyin esa, 2 + (++a) ifodani bajarish jarayonida avval a o‘zgaruvchisining qiymati bittaga oshiriladi, so‘ngra uning qiymatiga ikki sonini qo‘shib, natija b o‘zgaruvchisiga yuklanadi. Natijada, a ning qiymati - olti, b ning qiymati - sakkizga teng bo‘ladi. a = 5; b = 2 + (a--); Birinchi ifodada a o‘zgaruvchisiga besh soni yuklanadi. Keyin esa, 2 + (a--) ifodani bajarish jarayonida, avval, a o‘zgaruvchisining qiymati ifodaga qo‘yib hisoblanib, natija b o‘zgaruvchisiga yuklanadi, so‘ngra uning qiymati bittaga kamaytiriladi. Natijada, a ning qiymati to‘rt, b ning qiymati esa yettiga teng bo‘ladi. Jadvalga n ta talaba FIO va adreslarini kiritamiz. 2. Binar qidiruvni jadvalning birorta maydonida amalga oshirish uchun jadvalni shu maydoni bo’yicha tartiblab olish kerak. Shuning uchun masalaning qo’yilishida adresi TTJ bo’lgan talabalarni topish kerakligi sababli jadval ma’lumotlarini adres maydoni bo’yicha saralab olamiz. Masalani yechishda to’g’ridan-to’g’ri tanlash orqali saralashdan foydalanilgan. 3. key kalitga mos elementni izlash chegaralarini aniqlab olamiz. Dastlab u [0,n] oralig’ida, ya’ni low=0,hi=n. 4. Agar low<=hi bo’lsa, oraliq o’rtasini hisoblaymiz. mid=(low+hi)/2 5. Agar mid o’rnida turgan talaba adresi TTJ bo’lsa, element topildi, search=mid va 7-qadamga o’tiladi, aks holda keyingi qadamga o’tiladi. 6. Agar “TTJ” so’zi alifbo bo’yicha mid o’rnida turgan talaba adresi qiymatidan kichik bo’lsa, izlash quyi chegarasi o’zgaradi, ya’ni mid o’rnida turgan elementdan bitta oldingi elementgacha olinadi, ya’ni hi=mid-1. Aks holda, yuqori chegara o’zgaradi – mid dan keyingi elementdan to oxirgi elementlar oralig’i olinadi, ya’ni low=mid+1. 4-qadamga o’tiladi. 7. Agar topilgan elementdan oldin 30 turgan elementning (mid-1) ham adres maydoni TTJ bo’lsa, search--, ya’ni bitta oldingi elementga o’tamiz va shu qadamni boshidan bajaramiz. Aks holda keyingi qadamga o’tiladi. 8. Joriy (search ko’rsatayotgan) elementdan boshlab adresi “TTJ” ga teng bo’lgan talaba ma’lumotlarini ekranga chiqaramiz. Agar adresi “TTJ” dan farq qiladigan talaba chiqib qolsa, algoritm tugallanadi. Misol:Faqat lotin xarflaridan tuzilganlar ichida ekranga “r” xarfi chiquvchi chiziqli qidiruv algoritmi tuzilsin va natijalar taxlil qilinsin. // C++ tilida rekursiyali Binar Qidiruv # include <stdio.h> // Rekursiyali qidiruv funksiyasi. U massivdan // x qaysi o'rinda turganini qaytaradi, // yoki -1 int binarqidiruv ( int arr[], 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 (arr[mid] == x) return mid; // Agar element x dan katta bo'lsa, // u faqat chap qismni oladi if (arr[mid] > x) return binarqidiruv(arr, l, mid-1, x); 31 // Yoki u faqat o'ng qismni oladi return binarqidiruv(arr, mid+1, r, x); } // Bu yerga yetib keladi, qachonki // x soni massiv ichidan topilmasa return -1; } int main ( void ) { int arr[] = {2, 3, 4, 10, 40}; //massiv ni elementlar sonini topib olayabmiz int n = sizeof (arr)/ sizeof (arr[0]); int x = 10; int natija = binarqidiruv(arr, 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 <stdio.h> // Interative binar qidiruv funksiyasi. U massivdan 32 // x qaysi o'rinda turganini qaytaradi, // yoki -1 int binarqidiruv ( int arr[], int l, int r, int x) { while (l <= r) { int m = l + (r-l)/2; // X o'rtadagi elementga tengmi yo'qmi tekshiramiz if (arr[m] == x) return m; // Agar x katta bo'lsa, chapni hisobga olmaymiz if (arr[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 (arr)/ sizeof (arr[0]); int x = 10; int natija = binarqidiruv(arr, 0, n-1, x); (natija == -1)? printf ("X soni massiv ichida topilmadi.") : printf ("X soni massivning %d o'rnida.", natija); return 0; 33 } III.XULOSA Xulosa qilib aytganda malumotlarni qidirish orqali ko’p masalalarni hal qilsa bo’ladi. Katta-katta hajmdagi ma’lumotlar orasidan xohlagan ma’lumotlarni izlab topish mumkin bo’lar ekan. Bu kurs ishi orqali qidiruv tizimining qanchlik qiziqarli va samarali mavzu ekanligini bildim. Bundan tashqari juda ko’p yangi usillar orqali malumotlarni qidirish bilan turli xil chiroyli va qiziqarli ma’lumotlarni qidirib topish, va shu kabi malumotlarni tez qidirish qobilyatini xosil qildim. Bu kurs ishi orqali men mustaqil oddiy ma’lumotlarni qidira oladigan dasturlar tuza olish qobilyatiga ega bo’ldim. O’ylaymanki bu kurs ishi dasturlash olamiga kirib borishimga katta fundament vazifasini o’tab beradi . Ikkilik qidirish to plamningʻ ko p qismini o rtasini taqqoslash orqali ma lum bir narsani qidiradi. Agar mos ʻ ʻ ʼ kelsa, unda element indeksi qaytariladi. Agar o rta qism elementdan kattaroq bo lsa, ʻ ʻ u holda ushbu element o rta qismning chap tomonidagi pastki qatorda qidiriladi. ʻ Aks holda, element o rta elementning pastki qismidagi pastki qatorda ʻ qidiriladi. Xulasa qilib har bir dasturning dastlab algaritmni yaratib olgan maqul. Agar biz dasturimizning ketma ketligini bilmasak, u dastur biz oylagandan koprak hajmni egallash mumkin ekan.Ikkilik qidiruv va dasturlash tillari bo’yicha yazilgan bir necha kitoblar bilan taniship chiqdim va ulardan o’zimga kerakli malumotlarni oldim . Kurs ishimda malumotlar qidiruv tizilmasi, programmalash texnalogiyalari masalalari,qidiruv tizimi, ularning xossalari, tasvirlash usullari va tipik algoritmlarga blok sxemalar tuzish masalalari qaralgandir. 34 Foydalaningan adabiyotlar 1. Cormen, Tomas H. va boshqalar. Algoritmlarga kirish. Kembrij, Massachusets shtati: MIT Press, 2009. Chop etish 2. Xayneman, Jorj T. va boshq. Algoritmlar yamoqqa. Sebastopol, Kaliforniya: ko'rishReilly Media, 2016. Chop etish 3. Mahmud, Xosam M. Saralash: taqsimot nazariyasi. Xoboken, Nyu- Jersi: Jon Vili va Sons, 2011 yil. Chop etish 4. Tasvirkrediti:https://upload.wikimedia.org/wikipedia/commons/ thumb/e/e6/Merge_sort_algorithm_diagram.svg/500px- M erge_sort_algorithm_diagram.svg.png 5. Tasvirkrediti:https://en.wikipedia.org/wiki/Quicksort#/media/ File:Quicksort-diagram.svg 6. http:\\ziyonet.uz 7. http:\\dastur.uz 8. http:\\Algoritmlash asoslari 9. https :// www . tutorialspoint . com / data _ structures _ algorithms / binary _ search _ algorithm . htm 35

“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN “HAQIQIY IKKILIK QIDIRUV” MAVZUSIDA TAYYORLAGAN KURS ISHI

Mundarija Kirish…………………………………………………………………………….3 I.Asosiy qism 1.1.Graflar va ularning tasvirlanishi…………………………………………..4 1.2.Daraxt va ularni turlari………………………………………………….…11 1.3.Haqiqiy ikkilik qidruv algoritimi……………………………………...…..15 II. Dasturlashga oid 2.1.C++ dasturlash tilida ikkilik qidiruv algoritmi……………………………28 III.Xulosa………………………………………………………………………...34 IV.Foydalanilgan adabiyotlar……………………………………..………….…35 2

Kirish Qidiruv vazifasi dasturlashda eng keng tarqalgan vazifalardan biridir. Shuningdek, u ko'rib chiqilayotgan narsaning qo'llanilishini namoyish qilish uchun ajoyib imkoniyatdir. Qidiruv tizimi hamma sohada ishlatilishi sababli ma'lumotlar tuzilmalari kompyuterda bajarish ancha oson bo’ladi. Kompyuterda ma’lumotlarni topish maqsadida maxsus kod kiritilgan kompyuterga shu bilan bir qatorda global qidiruv tizimida ham huddi shu maqsadda va shunga o’xshash kod kiritilgan. Qidiruv mavzusida bir nechta asosiy o'zgarishlar mavjud va bu yerda % bilan ko'plab algoritmlar ishlab chiqilgan. Biz qiladigan asosiy taxmin quyidagi ma'lumotlar to'plami bo'lib, unda % qidiriladi. Berilgan qiymat belgilangan. Biz bu N elementlar to'plami deb faraz qilamiz massiv bilan ifodalanadi, deylik element Ob'ektlar odatda yozuvlar bo'lib, ularning maydonlaridan biri rol o'ynaydi kalit. Keyin vazifa kalit maydoni teng bo'lgan elementni topishdir berilgan x qiymati, shuningdek, qidiruv argumenti deb ataladi. Topilgan shartini qanoatlantiruvchi i indeksi boshqasiga murojaat qilishimizga imkon beradi. topilgan elementning maydonlari. Bizni faqat% ni topish muammosi qiziqtirgani uchun lekin qidiruv qilingan ma'lumotlar emas, biz buni taxmin qilamiz Element turi faqat kalitdan iborat, ya'ni uning o'zi kalit. Lineer qidiruv Agar ma'lumotlar haqida qo'shimcha ma'lumot bo'lmasa, unda aniq yechim% nie - qiymatni bosqichma-bosqich oshirib, massivdan ketma-ket o'ting massivning kerakli qiymat aniq bo'lmagan qismi. Bu yechim ma'lum% Stno chiziqli qidiruv sifatida. Qidiruv ikkita shartdan birida to'xtatiladi: 1. Element topildi, ya'ni ai = x. 2. Butun massiv skanerdan o‘tkazildi, lekin element topilmadi. 3

Asosiy qism Graflar va ularning tasvirlanishi Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. Pregel daryosi Kyonigsberg shahrini o‘sha davrda to‘rtta , , va qismlarga bo‘lgan. Shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? Kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. L. Eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yichayagona ilmiy ish bo‘lib keldi. XIX asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar G. Kirxgof va A. Keli ishlarida paydo bo‘ldi. “Graf” iborasi D. Kyonig tomonidan 1936 yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda uchraydi. Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir: boshqotirmalarni hal qilish; qiziqarli o‘yinlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtomatlar, blok-sxemalar va komp’yuter uchun programmalarni tadqiq qilish va hokazo. Grafning abstrakt ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar. Avvalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifini va boshqa ba’zi sodda tushunchalarni keltiramiz. qandaydir bo‘shmas to‘plam bo‘lsin. 4

Загрузите документ, чтобы увидеть его полностью.

Похожие

HAQIQIY IKKILIK QIDIRUV
Haqiqiy ikkilik qidiruv
Butun sonli ikkilik qidiruv algoritmi
INTERPOLATSION QIDIRUV
Qidiruv algoritmlari