![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Интерполяционный поиск
Лине́ йная интерполя́ ция — интерполяция алгебраическим двучленом P1(x) = ax + b функции f, заданной в двух точках x0 и x1 отрезка [a, b]. Геометрически это означает замену графика функции f прямой, проходящей через точки (x 0, f (x 0)) и (x 1, f (x 1)). Уравнение такой прямой имеет вид: отсюда для Это и есть формула линейной интерполяции
Отличие интерполяционного поиска от предыдущих методов заключается в том, что выбор очередного ключа Ki для сравнения с аргу- ментом А зависит не только от Q и P, но и от значений ключей KQ и Kp в нижней и верхней границах интервала поиска. Если аргумент поиска А на очередном шаге лежит между KQ и KP, то ключ Ki выбирается на расстоянии (P-Q)(A-KQ)/(KP-KQ) от Q. Алгоритм интерполяционного поиска также аналогичен алгоритму би- нарного поиска. Отличие состоит только в шаге вычисления номе- ра I сравниваемого элемента, который в данном случае имеет вид: I = |_ (P-Q)(A-KQ)/(KP-KQ) _| + Q. Пример. Осуществить интерполяционный поиск аргумента 51 в массиве ключей: 20 25 29 32 37 38 39 51 53 57 61 99. Q=1, KQ=20, P=12, KP=99, i=5, Ki=37: [20 25 29 32 Q=6, KQ=38, P=12, KP=99, i=8, Ki=51: 20 25 29 32 37[38 39 Поиск закончен удачно.
Var Q, P, I, FLAG, A, KP, KQ: integer; Begin FLAG: =0; P: =N; Q: =1; Repeat if P< Q then Begin FLAG: =1; Writeln('Объект не найден'); End Else Begin I: =Trunc((P-Q)*(A-K[Q])/(K[P]-K[Q]))+Q; (меньшее или равное Х, если Х > =0, и большее или равное Х, если X< 0) if A=date[I] then Begin FLAG: =1; Writeln('Объект успешно найден ' + I) End Else if A> date[I] then Q: =I+1 Else P: =I-1; End; until FLAG=1; End; Всего положительных элементов N, date[0]=0.
Недостатки. 1.Нужно вычислять Kp и KQ, что особенно неудобно для файла. 2. Можно применять только для числовых уключей
|