|
Mustaqil ishi Bajardi: Yusupova Dilorom Qabul: Umurzaqova D. M farg’na 2023 Mavzu
|
| bet | 1/5 | | Sana | 15.11.2023 | | Hajmi | 185,42 Kb. | | #99352 |
Bog'liq malumotlar tuzilmasi va algoritm
O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
FARG‘ONA FILIALI
“Kompyuter injiniringi” fakulteti
Kompyuter injiniringi yo‘nalishi
715-21Yusupova Diloromning
“Ma’lumotlar tuzilmasi va algoritm ” fanidan
Mustaqil ishi
Bajardi: Yusupova Dilorom
Qabul: Umurzaqova D.M
Farg’na 2023
Mavzu: Qidiruv algoritmlari:chiziqli va binary qidituv. Hesh funksiyasi va heshlash algoritmlarini tuzish.Sharalash usullari va ularni qo’llanish.
Reja:
1. Hesh tushunchasi.
2. Hesh turlari va xossalari.
3. Xeshlash(tirish) tushunchasi
4. Hesh-funksiya va uning hossalari
5. Ziddiyatlarning yuzaga kelishi
6. Kolloziya holatini hal etish metodlari
8Hulosa
9.Foydanilgan adabiyotlar
Aytaylik bizga massiv berilgan:
a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan dastur tuzish sharti qo'yilgan.
Ushbu masalani yechishda eng birinchi xayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
Chiziqli qidiruv - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:
func linearSearch(a []int, condidate int) int {
for i := 0; i < len(a); i++ {
if a[i] == condidate {
return i
}
}
return -1
}
Ko'rib turganingizdek, funksiyamiz 2 ta parametr qabul qiladi, birinchisi massivni o'zi, ikkinchisi esa biz qidirayotgan element. Agar uni topa olmasak, "-1" qiymatni qaytaramiz.
Endi bundan optimal bo'lgan usul - binar(ikkilik) qidiruvni ko'rib chiqsak.
Bu usulda ham funksiyaga 2 ta parametr, birinchisi massiv o'zi keyin esa biz qidirayotgan elementni parametr sifatida beriladi. Qidiruv esa quyidagicha:
Dastlab biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz, mening kodimda bu left va right o'zgaruvchilaridur:
left := 0 right := len(a)
so'ngra quyidagi shart bajarilgan holda
left < right
quyidagi ketma-ket operatsiyalarni amalga oshiramiz
left va right index lari markazidagi elementni topamiz (left + right) / 2
topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi.
agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right = mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom etadi.
Shu zaylda qidiruv left < right shart bajarilmagunicha davom etadi, agar bu jarayonda biz qidirgan element topilmasa u xolda -1 javob qaytariladi, quyida dastur kodi keltirilgan:
func binarySearch(a []int, condidate int) int {
left := 0
right := len(a)
|
| |
