Interpolatsion qidiruv - Информатика и ИТ - Презентации

Информация о документе

Цена	3000UZS
Размер	236.9KB
Покупки	0
Дата загрузки	28 Март 2023
Расширение	pptx
Раздел	Презентации
Предмет	Информатика и ИТ

Interpolatsion qidiruv

Купить

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

Mundarija I Kirish ..........................................................................................................3 II Asosiy qisim ..............................................................................................4 2.1 Interpolatsion qidiruv tushunchasi . .............................................4 2.2 C++ da dastur ko`rinishi ..............................................................14 2.3 Ikkilik qidiruvda joylashishni aniqlash ........................................18 III Xulosa ....................................................................................................27 IV Foydalanilgan adabiyotlar ...................................................................28

Kirish Interpolatsion qidiruvning mazmuni shundan iboratki bizga malum bir tartiblangan ma’lumotlar berilgan bo‘lsin. Misol uchun (massiv yoki kitob). Endi men shu malumotlar orasidan bitta qiymat yoki sozni izlab topishim kerak. Buni men interpolatsion qidiruv orqali amalga oshiraman. Ammo ikkilik qidiruvdan farqli o'laroq, interpolyatsiya qidiruvi ketma-ketlikni ikkita teng qismga ajratmaydi, balki elementning talab qilinadigan va joriy qiymati o'rtasidagi masofaga e'tibor qaratgan holda kalitning (kerakli element) taxminiy joylashishini hisoblab chiqadi. Lug`at kitobda so`zlar alfavit (alifbo) tarzida tartiblangan bo`ladi, yani kitobning boshidagi so`zlar “a” harfidan boshlansa, oxiridagi so`zlar “z” harfi bilan tugaydi. Bizga kerakli so`z “olma” bo`lsin. Olma so`zini kitobn

Interpolatsion qidiruv tushunchasi Interpolyatsiya – bu ma'lum qiymatlarning mavjud diskret to'plamidan miqdorning oraliq qiymatlarini topishdir. Interpolatsiya qidiruvi faqat tartiblangan massivlar bilan ishlaydi. U binarga o'xshaydi, ya'ni har bir qadamda ma'lum bir qidiruv maydoni hisoblab chiqiladi, algoritm bajarilganda u torayadi.Ammo ikkilik qidiruvdan farqli o'laroq, interpolyatsiya qidiruvi ketma-ketlikni ikkita teng qismga ajratmaydi, balki elementning talab qilinadigan va joriy qiymati o'rtasidagi masofaga e'tibor qaratgan holda kalitning (kerakli elementini) taxminiy joylashishini hisoblab chiqadi.Algoritm g'oyasi telefon raqamini qidirishni eslatadi: abonent nomlari ro'yxati tartiblangan, shuning uchun kerakli telefon raqamini topish qiy

Foydalanish paytida katta ma'lumotlar n uchun interpolatsion qidiruv algoritm ishlash O (n); ammo interpolatsiya uchun ishlatiladigan chiziqli shkala bo'yicha ma'lumotlar teng taqsimlangan deb faraz qilsak, unumdorlik O (log log n) sifatida ko'rsatilishi mumkin. Interpolyatsiyani qidirishning amaliy samaradorligiga qarab sonining kamayishi har bir takrorlash uchun zarur bo'lgan murakkabroq hisob-kitoblardan ustun bo'ladimi-yo'qligiga bog'liq. Bu diskdagi katta tartiblangan fayldagi yozuvni topish uchun foydali bo'lishi mumkin. B- daraxtlar kabi indeks tuzilmalari diskka kirishni ham kamaytiradi va ko'pincha diskdagi ma'lumotlarni qisman indekslash uchun ishlatiladi, chunki ular ko'p turdagi ma'lumotlarni indekslashi va onlayn ravishda yan

C++ da dastur ko`rinishi #include <iostream> using namespace std; int main() { int MyArray [] { 1, 2, 4, 6, 7, 89, 123, 231, 1000, 1235 }; int x = 0; int a = 0; int b = 9; int WhatFind = 123; bool found; for (found = false; (MyArray[a] < WhatFind) && (MyArray[b] > WhatFind) && !found; ) { x = a + ((WhatFind - MyArray[a]) * (b - a)) / (MyArray[b] - MyArray[a]);

if (MyArray[x] < WhatFind) a = x + 1; else if (MyArray[x] > WhatFind) b = x - 1; else found = true; } if (MyArray[a] == WhatFind) cout << WhatFind << " asos element " << a << endl; else if (MyArray[b] == WhatFind) cout << WhatFind << " asaos element " << b << endl; else cout << "kechirasiz topilmadi" << endl; return 0; }

Natija (1-rasm) 1-rasm.

Ikkilik qidiruvda joylashishni aniqlash Ikkilik qidiruvda, agar kerakli ma'lumotlar topilmasa, qolgan ro'yxat ikki qismga bo'linadi, pastki va yuqori. Ularning har birida qidiruv ishlari olib borilmoqda. Ma'lumotlar tartiblangan bo'lsa ham, ikkilik qidiruv kerakli ma'lumotlarning joylashuvidan foydalanmaydi.

Algoritm Bu mavjud BST algoritmining improvizatsiyasi bo'lganligi sababli, biz joylashishni aniqlash yordamida ma'lumotlar qiymatining "maqsadli" indeksini topish bosqichlarini eslatib o'tamiz 1-qadam - Ro'yxatning o'rtasidan ma'lumotlarni qidirishni boshlang . 2-qadam - Agar u mos keladigan bo'lsa, element indeksini qaytaring va chiqing. 3-qadam - Agar u mos kelmasa, pozitsiyani tekshiring. 4-qadam - Ro'yxatni tekshirish formulasidan foydalanib bo'ling va yangi o'rtani toping. 5-qadam - Agar ma'lumotlar o'rtadan kattaroq bo'lsa, yuqoriroq ro'yxatda qidiring. 6-qadam - Agar ma'lumotlar o'rtadan kichikroq bo'lsa, pastki ro'yxatdan qidiring. 7-qadam – Natija chiqgancha takrorlang.

Xulosa Kur ishini bajarishda men misol tariqasida massiv elementlarini oldim. Massivnig elementini topish uchun interpolatsion qidiruv tizimidan foydalandim. Bunda bizga tartiblangan massiv berilgan bo`lsin. Xulosa qilib shuni aytishimiz mumkinki interpolatsion qidiruvda massiv elementlari bir necha guruhlarga bo`linadi va qidirilayotgan element yo`g`i o`chiriladi. Bir necha takrorlanishdan so`ng qidiruv natijasi elon qilinadi.

Foydalanilgan adabiyotlar 1. M.O‘.Ashurov, Sh.A.Sattarova, Sh.U.Usmonqulov. Algoritmia г. -T.: «Fan va texnologiya», 2018,244 bet. 2. Polatov A.M. Algoritmlar va C++ tilida dasturlash asoslari . Toshkent. “Universitet” - 2017. 123 bet 3. Madraximov Sh.F., Ikramov A.M., Babajanov M.R. C++ tilida programmalash bo’yicha masalalar to’plami. O’quv qo’llanma. T., O’zbekiston Milliy universiteti, “Universitet” nashriyoti, 2014. - 160 b 4. Holmatov TX, Toyloqov NI Amaliy, dasturlash va kompyuterning matematika ta'minoti. T. Mexnat, 2000 y. 5. Akbaraliyev B.B., Yusupova Z.D., “Ma’lumotlar tuzilmasi va algoritimlar”, Toshkent 2013. 6. Xayitmatov O’.T., Inogomjonov E.E., Sharipov B.A., Ro’zmetova N., Rahimboboeva D,” MA'LUMOTLAR TUZILMASI VA ALGORITMLARI”, Toshkent – 2011 Foydalanilgan intern

Купить

Похожие документы
Operatsion tizimlarda journaling file system
I/O scheduling algoritmlari
O‘rta Osiyo kutubxonalarining o‘rganilish masalalari
Funksiyalar va arrow function
Tashkilot xodimlari ma’lumotlarini jamlovchi tizim