|
Satrlarda qismiy satrlarni izlash algoritmi Boyer-Mur algoritmini keltiring
Boyer – Mur satrlarni qidirish algoritmi samarali satrlarni qidirish algoritmi bu amaliy qidiruv adabiyoti uchun standart mezon.[1] U tomonidan ishlab chiqilgan Robert S. Boyer va J Strother Mur 1977 yilda.[2] Asl qog'ozda naqsh o'zgarishini hisoblash uchun statik jadvallar mavjud bo'lib, ularni qanday ishlab chiqarish kerakligi tushuntirilmagan. Jadvallarni ishlab chiqarish algoritmi keyingi qog'ozda nashr etildi; ushbu qog'ozda keyinchalik tuzatilgan xatolar mavjud edi Vojsex Rytter 1980 yilda.[3][4] The algoritm oldindan ishlov berish The mag'lubiyat qidirilmoqda (naqsh), lekin qidirilayotgan qator (matn) emas. Shunday qilib, naqsh matndan ancha qisqa bo'lgan yoki bir nechta qidiruvlarda saqlanib turadigan ilovalar uchun juda mos keladi. Boyer-Mur algoritmi matnni qismlarini o'tkazib yuborish uchun oldindan ishlov berish bosqichida to'plangan ma'lumotlardan foydalanadi, natijada boshqa ko'plab qator qidirish algoritmlariga qaraganda past koeffitsient paydo bo'ladi. Umuman olganda, algoritm naqsh uzunligi oshgani sayin tezroq ishlaydi. Algoritmning asosiy xususiyatlari shundan iboratki, naqshning boshiga emas, balki dumiga mos kelish va matndagi har bir belgini qidirishdan ko'ra, bir nechta belgidan sakrab o'tishda matn bo'ylab o'tish.Entsiklopediya site:uz.wikicsu.ru Boyer-Mur algoritmi paydo bo'lishlarni qidiradi P yilda T turli xil hizalamalarda aniq belgilar taqqoslashlarini amalga oshirish orqali. A o'rniga qo'pol kuch bilan qidirish barcha hizalamalar (ular mavjud ), Boyer-Mur oldindan qayta ishlash natijasida olingan ma'lumotlardan foydalanadi P imkon qadar ko'proq hizalamaları o'tish uchun. Ushbu algoritmni joriy etishdan avval matn ichida izlashning odatiy usuli naqshning har bir belgisini naqshning birinchi belgisi uchun tekshirish edi. Bu topilgandan so'ng matnning keyingi belgilarini naqsh belgilariga solishtirish mumkin edi. Agar hech qanday mos kelmasa, matni yana bir belgi bo'yicha tekshirilib, moslikni topish uchun. Shunday qilib, matndagi deyarli har bir belgi tekshirilishi kerak. Ushbu algoritmning asosiy tushunchasi shundan iboratki, agar naqshning oxiri matn bilan taqqoslansa, unda matnning har bir belgisini tekshirishdan ko'ra, matn bo'ylab sakrash mumkin. Ushbu ishning sababi shundan iboratki, naqshni naqshga bir qatorga qo'yishda naqshning oxirgi belgisi matndagi belgi bilan taqqoslanadi. Agar belgilar mos kelmasa, matn bo'ylab orqaga qarab qidirishni davom ettirishning hojati yo'q. Agar matndagi belgi naqshdagi biron bir belgiga to'g'ri kelmasa, unda tekshiriladigan keyingi belgi joylashgan bo'ladi n matn bo'ylab joylashgan belgilar, qaerda n naqshning uzunligi. Agar matndagi belgi bo'lsa bu naqshda, keyin mos keladigan belgi bo'ylab bir qatorga kelish uchun naqshning qisman siljishi amalga oshiriladi va jarayon takrorlanadi. Matndagi har bir belgini tekshirishdan ko'ra, taqqoslash uchun matn bo'ylab sakrash, taqqoslashlar sonini kamaytiradi, bu algoritm samaradorligining kalitidir. Rasmiy ravishda, algoritm tekislashdan boshlanadi , shuning uchun boshlanishi P ning boshlanishiga to'g'ri keladi T. Belgilar P va T keyin indeksdan boshlab taqqoslanadi n yilda P va k yilda Torqaga qarab harakatlanmoqda. Iplar oxiridan mos keladi P boshlanishiga qadar P. Taqqoslashlar boshlanishiga qadar davom etadi P erishilgan (bu mos keladigan o'yin degan ma'noni anglatadi) yoki bir nechta qoidalar tomonidan ruxsat etilgan maksimal qiymatga muvofiq hizalanish oldinga (o'ngga) siljigan holda nomuvofiqlik paydo bo'ladi. Taqqoslashlar yana yangi hizalamada amalga oshiriladi va jarayon hizalama oxiridan o'tguncha takrorlanadi T, bu boshqa o'yinlar topilmasligini anglatadi.
81.A[n] massivni Shell usulida saralash algoritmini yozing.
1959-yilda D.Shell tomonidan to’g’ridan-to’g’ri qo’yish usuli yordamida saralashning mukammallashtirilgan usulini taklif qildi. Dastlab saralanayotgan har 4 ta pozitsiyadagi elementlar alohida guruhlanadi va saralanadi. Bu jarayon to’rttalik saralash deb nomlanadi.Elementlar bir marta to’liq ko’rib chiqilgandan keyin ular yana qayta guruhlanadi- ya’ni saralanayotgan har 2 ta pozitsiyadagi elementlar alohida guruhlanadi va saralanadi (ikkitalik saralash).Uchinchi to’liq ko’rib chiqilishda oddiy saralash jarayoni bo’ladi.Har bir to’liq qarab chiqishda barcha elementlarni ishga tushirish mashinadan katta resurs talab qiladigandek ko’rinadi, lekin har bir to’liq qarab chiqishda kam elementlar saralanadi yoki yaxshi saralangan bo’lsa, ularni shunchaki taqqoslab chiqish yetarli bo’ladi.Bu usul natijasida massiv saralangan bo’ladi va har bir to’liq qarab chiqish avvalgisiga nisbatan yaxshiroq bo’ladi. (chunki har bir i-saralash 2i-saralashda saralangan 2 ta guruhni birlashtiradi).Shell saralash usulining C dagi algoritmlari
#define _CRT_SECURE_NO_WARNINGS // scanf() to’g’ri ishlashi uchun #include
// Shell saralash funksiyasi void shellSort(int *num, int size) { int increment = 3; // saralashning dastlabki orttirishi while (increment > 0) // toki inkrement mavjud { for (int i = 0; i < size; i++) // massivning barcha elementlari uchun { int j = i; // indeksi va elementini saqlaymiz int temp = num[i];
// j-elementdan inkrement kattaligi bo’yicha orqada qolgan barcha elementlarni ko’rib chiqamiz while ((j >= increment) && (num[j - increment] > temp)) { // toki ortda qolayotgan element joriy elementdan katta num[j] = num[j - increment]; // uni joriy pozitsiyaga ko’chiramiz j = j - increment; // keyingi ortda qolayotgan elementga o’tamiz } num[j] = temp; // saqlangan elementni aniqlangan joyga qo’yamiz } if (increment > 1) // inkrementni 2 ga bo’lamiz increment = increment / 2; else if (increment == 1) // oxirgi ko’rib chiqish tugadi,break; // sikldan chiqamiz }}
int main(){
int m[10]; // massiv elementlarini kiritamiz for (int i = 0; i<10; i++) { printf("m[%d]=", i);
scanf("%d", &m[i]); } shellSort(m, 10); // saralash funksiyasini chaqiramiz // saralangan massiv elementlarini chiqaramiz for (int i = 0; i<10; i++) printf("%.2d ", m[i]); getchar(); getchar(); return 0;} Natija:
82. Sizga bir oʻlchamli butun sonlardan iborat massiv berilgan.
Sizning vazifangiz bu massiv elementlarini modullari jihatdan
kamaymaslik tartibida saralaydigan dastur tuzish. Agar modul jihatdan
teng musbat va manfiy sonlar mavjud boʻlsa manfiy son oldinroq
joylashtirilsin:
Masalan:
9 8 -9 2 -4 3
2 3 -4 8 -9 9
Do'stlaringiz bilan baham: |
