Interpolatsion qidiruv - Pedagogika - Slaydlar

Dokument ma'lumotlari

Narxi	3000UZS
Hajmi	272.4KB
Xaridlar	0
Yuklab olingan sana	07 Noyabr 2026
Kengaytma	pptx
Bo'lim	Slaydlar
Fan	Pedagogika

Interpolatsion qidiruv

Sotib olish

“ A LGOR I TM VA M A’ L UM OTL A R STR UK TUR A SI ” FA N I DA N
“ I N TER POL ATSI ON QI DI R UV ” M AV ZUSI DA TAY Y OR L AGA N
KURS I SHI

Mu n da ri j a
I
K i r i sh ....................................................................................................
......3
I I A sosi y
qi si m ..............................................................................................4
2.1 I n t er pol a t si on qi di r u v
t u sh u n c h a si . .............................................4
2.2 C++ da da st u r
k o` r i n i sh i ..............................................................14
2.3 I k k i l i k qi di r u v da j oy l a sh i sh n i
a n i ql a sh ...... ..... .............................18
I I I
X u l osa ..................................................................................................
..27
I V Foy da l a n i l ga n
a da bi y ot l a r ...................................................................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 kitobning boshidan izlamaymiz, chunki “o” harfi
alfavitning o`rtasida joylashgani uchun, olma so`zini topish
uchun kitobning o`rtasini ochamiz va o harfidan boshlangan
so`zlar orasidan qidirib topamiz. Bunda olma so`zini kitobning
boshidan ohirigacha izlamaymiz balki o harfi qatnashgan
so`zlar orasidan oson topamiz. Bundan ko`rinib turibdiki
boshq sohalarda ham interpolatsion qidiruv dan foydalanami.
Interpolatsion so`zining ma’nosini tushinib oldik. Endi bu
interpolatsion qidiruvni algaritim va malumotlar strukturasida
qo`llanishini ko`rib chiqamiz.

I n t er pol a t si on qi di r u v t u sh u n ch a si
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 qiyin bo'lmaydi, chunki, masalan, biz
"U" harfi bilan boshlanadigan familiyasi bo'lgan obunachini
qidirayotgan bo'lsak, unda qidirish uchun ma'lumotnomaning
oxiriga o'tish maqsadga muvofiq bo'ladi. Hisoblangan qiymat
kattaroq bo'lsa, qidiruv maydonining o'ng chegarasi, agar u
kamroq bo'lsa, chap tomonga siljiydi.

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
yangilanishi mumkin . Biroq, diskda ma'lum
tartiblangan, lekin indekslanmagan ma'lumotlar
to'plamini qidirishga majbur bo'lganda,
interpolyatsiya qidiruvi foydali bo'lishi mumkin.

C++ da da st u r k o` r i n i sh i
#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.

I k k i l i k qi di r u v da j oy l a sh i shn i a ni ql a sh
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.

A l gor i t m
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 m a' l u m ot l a r n i 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
top ing.
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'yxatda n qidiring.
7-qadam – Natija chiqgancha takrorlang.

X ul osa
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
i nt er pol a t si on qi di r uv da massiv elementlari
bir necha guruhlarga bo`linadi va
qidirilayotgan element yo`g`i o`chiriladi. Bir
necha takrorlanishdan so`ng qidiruv natijasi
elon qilinadi.

Foy da l a n i l ga n a da bi y ot l a r
1. M.O‘.Ashurov, Sh.A.Sattarova, Sh.U.Usmonqulov. A l gor i t m i a г. -T.: «Fan va
texnologiya», 2018,244 bet.
2. Polatov A.M. A l gor i t m l a r v a C++ t i l i da da st u r l a sh a sosl a r i . Toshkent.
“Universitet” - 2017. 123 bet
3. Madraximov Sh.F., Ikramov A.M., Babajanov M.R. C++ t i l i da progra m m a l a sh
bo’ y i c h a m a sa l a l a r t o’pl a m i . O’quv qo’llanma. T., O’zbekiston Milliy universiteti,
“Universitet” nashriyoti, 2014. - 160 b
4. Holmatov TX, Toyloqov NI A m a l i y, da st u r l a sh v a k om py u t er n i n g m a t em a t i k a
t a 'm i n ot i . 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 internet saytlar
7. wikipedia
8. h t t ps:/ / n eerc .i f m o.r u / w i k i / i n dex .ph p? t i
9. https://e-maxx.ru/algo

Interpolatsion qidiruv

Sotib olish