|
O‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi farg‘ona davlat universiteti
|
| bet | 5/12 | | Sana | 21.05.2024 | | Hajmi | 117,25 Kb. | | #248931 |
Bog'liq 1-kurs kurs ishi(2)Jump Search (Sekish izlash): O'lkalar orasida sekinchalar bilan topish. Bu algoritm to'plamni to'g'ridan to'g'ri solishtiradi, ammo uning davri o'lchamli to'plamlarda yaxshi ishlaydi.
Jump Search (Sekish izlash) algoritmi o'lchamli tartiblangan to'plamda (masalan, massivda yoki ro'yxatda) bir qiymatni qidirish uchun ishlatiladi. Bu algoritm ma'lum bir qadam oraliqida to'plamni sekinchalar bilan tekshirish va qidirishni amalga oshiradi. Sekish izlash algoritmi binar izlash (binary search)ga o'xshash bo'lgan lekin uning o'zgaruvchilardan biri o'lchami va o'lchamdagi qadami (jump step)dan foydalanadi.
Sekish izlash algoritmi quyidagi tartibda bajariladi:
Boshlang'ich qadam (jump step)ni aniqlash. Bu odatda √n bo'lgan qiymatni o'z ichiga oladi, burada n to'plamdagi elementlar sonini ifodalaydi.
To'plamni qadam qadam bilan sekinchalar orqali tekshirish. Agar tekshiruvdagi element kichik yoki teng bo'lsa, yoki qidirilayotgan qiymatga yetib kelganda, ushbu qismni ichidagi to'plamni sekishsiz izlash algoritmi orqali bajarish.
Agar tekshiruvdagi element katta bo'lsa, sekinchalar orqali qidiruvni davom ettirish va birinchi qadamni keyingi sekinchadan boshlash.
Agar qidirilayotgan qiymat topilmasa, to'plamni tekshiruvdagi sekinchadan oxirigacha davom ettirish.
Sekish izlashning asosiy afzalliklari:
Sekish izlash algoritmi o'lchamli tartiblangan to'plamlarda yaxshi ishlaydi.
O'lchamdagi qadamni aniqlash sababi bilan, sekish izlash algoritmi binar izlashdan tez ishlash uchun idealdir.
Qidirilayotgan qiymat topilmasa ham, algoritmda aholi sonini kamaytirish bilan yordam beradi.
Ushbu algoritmalar C++ dasturlash tilida amalga oshirilishi mumkin. Har birining o'zlariga xos afzalliklari va chegaralariga ega. Tanlangan algoritm qanday holatlar uchun eng yaxshi bo'lishini aniqlash uchun ma'lumotlar to'plami turlariga, o'lchamiga va topilmaydigan elementlar soniga qarab tanlash kerak.
Jump Search – massivda ma’lum bosqichlardan o‘tish orqali tartiblangan massivda ma’lum qiymatni topish algoritmidir. Bosqichlar massiv uzunligining sqrt bilan belgilanadi. Bu yerda sakrab qidiruv uchun bosqichma-bosqich algoritm: Massiv uzunligi n kvadratini olib, qadam o'lchamini m aniqlang. Massivning birinchi elementidan boshlang va ushbu pozitsiyadagi qiymat maqsadli qiymatdan kattaroq bo'lguncha m qadamini qo'ying. Maqsaddan kattaroq qiymat topilsa, oldingi bosqichdan maqsad topilmaguncha yoki maqsad massivda yo'qligi aniq bo'lguncha chiziqli qidiruvni bajaring.
Agar maqsad topilsa, uning indeksini qaytaring. Agar yo'q bo'lsa, maqsad massivda topilmaganligini ko'rsatish uchun -1 ni qaytaring.
1-misol:
// C++ program to implement Jump Search
#include
using namespace std;
int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);
// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] < x)
{ prev = step;
step += sqrt(n);
if (prev >= n)
return -1; }
// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++;
// If we reached next block or end of
// array, element is not present.
if (prev == min(step, n))
return -1; } // If element is found
if (arr[prev] == x)
return prev;
return -1;
}
// Driver program to test function
int main()
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610 };
int x = 55;
int n = sizeof(arr) / sizeof(arr[0]); // Find the index of 'x' using Jump Search
int index = jumpSearch(arr, x, n);
// Print the index where 'x' is located
cout << "\nNumber " << x << " is at index " << index;
return 0;
}
// Contributed by nuclode
|
| |
