![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Фибоначчиев поиск (самостоятельно)
При реализации этого метода для нахождения интервала поиска используются числа Фибоначчи. Числа Фибоначчи получаются по рекуррентной формуле F В методе Фибоначчи, так же как и в однородном бинарном поиске, используются два указателя: i - текущее положение и величина H изменения, но они выбираются в соответствии с числами Фибоначчи. Значение i выбирается равным числу Фибоначчи F Алгоритм Фибоначчиева поиска состоит из предварительного этапа и 4 шагов. Первоначально определяется такое число M> =0, что N + M + 1 = F Структурограмма алгоритма поиска приведена на рис.
Пример 1. 1 4 5 8 9 12 А = 8, N = 6.
P=2; m = 1; 8 > 5; P # 1; I = 4; P=1; m=0; 1 4 5 8 9 12; Удача!
Пример 2 1 4 5 8 9 12 А = 12, N = 6.
1 4 5 8 9 12; I=6; P=1; m = 1; 1 4 5 8 9 12; Удача!
Пример 3 1 4 5 8 9 12 А = 11, N = 6.
1 4 5 8 9 12
I=6; P=1; m = 1; 1 4 5 8 9 12
I = 5; P=1; m=0; 1 4 5 8 9 12; Неудача!
|