“Fibonachi sonlarni hosil qilishda samarali algoritmlar” mavzusidagi

Fibonachchi usulida qidiruv

Ushbu qidiruv usulida Fibonachchi sonlariga teng positsiyalarda joylashgan elem entlar tahlil qilinadi. Fibonachchi sonlari quyidagi qoidaga ko'ra hosil bo‘ladi: har bir keyingi son oldingi ikkita sonlam ing yig'indisiga teng, masalan

Qidiruv jarayoni ikkita kalitlar orasidagi qidirilayotgan kalit joylashgan oraliq topilgunigacha davom etadi.

2-misol.

dastlabki kalit to'plam berilgan. Qidirilayotgan kalit 42 ga teng bo‘lsin. Qidirilayotgan kalitning taqqoslash ketma-ketligi Fibonachchi sonlariga teng pozitsiyalarda olib boriladi.

Birinchi qadam. К ~ k₁ 42>3=> Qidirilayotgan kalit Fibonachchi sonlariga teng pozitsiyalarda joylashgan kalit bilan taqqoslanadi.

Ikkinchi qadam. К ~ k₂ 42>5=> Qidiruv jarayoni Fibonachchining keyingi sonining pozitsiyasiga teng kalit bilan taqqoslanadi.

Uchinchi qadam. К ~ k₃. 42>8=> Taqqoslash davom ettiriladi.