“Fibonachi sonlarni hosil qilishda samarali algoritmlar” mavzusidagi

Interpolyatsiya usulida qidiruv

Dastlabki to ‘plam o'sish tartibida tartiblangan bo'lishi kerak. Boshlang'ich taqqoslash quyidagi formula orqali aniqlanuvchi d qadamga teng masofada am alga oshiriladi:

bu yerda /- birinchi qaraladigan element tartib raqami; j- oxirgi qaraladigan elem ent tartib raqami; A- qidirilayotgan kalit, Kt,K j-i va j pozitsiyalardagi kalit qiymatlari, [ ] - sonning butun qismi.

Qidiruv usulining g ‘oyasi shundan iboratki, d- qadam yuqorida keltirilgan form ulaning har bir bosqichlarida o ‘zgaradi. (13-chizma).

Algoritm d—0 bo‘lganda to'xtaydi, shu bilan birga qo‘shni elem entlar tahlil qilinadi. Shundan so‘ng qidiruv natijalari bo‘yicha xulosa qilinadi.

Qidiruv algoritmi

Agar to‘plam arifmetik progressiyani tashkil qilsa, ushbu usul samarali natija beradi.

3-misol.

kalit to‘plam berilgan bo‘lsin. Qidirilayotgan kalit 70 ga (K=70) teng bo‘lsin.

Birinchi qadam. Dastlabki kalit to‘plam uchun d qadamni topamiz:

Berilgan to'plam da qidirilayotgan kalit bilan joylashgan 16-tartib raqamda turgan kalitni taqqoslaymiz:

K_l6 ~ K, 70 = 70 kalit topildi.