Toshkent 2020 Variant №: 15
Download 62.53 Kb.
|
Algoritm MI
- Bu sahifa navigatsiya:
- Toshkent 2020 Variant №:15
- Linear Search
O'ZBEKISTON RESPUBLIKASI AXBOROT TEXNALOGIYALARI VA KOMMUNIKATSIYALARI RIVOJLANTIRISH VAZIRLIGI MUXAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNALOGIYALARI UNIVERSITETI. Algoritmlarni loyihalash fanidan MUSTAQIL ISH MAVZU: Jadvallar ustida qidiruv va boshqa amallar Bajardi: CAL002 -guruh talabasi Hasanov Sarvarbek Toshkent 2020 Variant №:15 Aytaylik bizga jadval berilgan: a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Bizga ushbu jadvaldada 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 {
}
} 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
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) for left < right { mid := (left + right) / 2 if a[mid] == condidate { return mid }
if a[mid] < condidate { left = mid } else { right = mid } }
return -1 }
Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz: funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n) Binar qidiruv( Binary Search )Aytaylik bizga tartiblangan n ta elementdan iborat arr[] massiv berilgan bo'lsin, va berilgan x ni arr[] ichidan qidirish funksiyasini tuzish sharti qo'yilsin. Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidir algoritmini ishlatsak bo'ladi.
Qiyinlik darajasi: 5/10. Eng zo'r ko'rsatkichi(vaqt): O(1) Eng yomon ko'rsatkichi(vaqt): O(log n) O'rtacha ko'rsatkichi(vaqt): O( log n) Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha. Masalan: Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi. 1. x ni o'rtadagi element bilan solishtiramiz. 2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz. 3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda. 4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz. Quyida Binar qidiruvning rekursiya orqali amalga oshiramiz. // C++ tilida rekursiyali Binar Qidiruv #include // 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
// Agar element x dan katta bo'lsa, // u faqat chap qismni oladi
// 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 // Interative binar qidiruv funksiyasi. U massivdan // 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
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);
}
www.texnoman.uz www.uz.wikipedia.org www.geeksforgeeks.org Download 62.53 Kb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling