Форум программистов, компьютерный форум CyberForum.ru

Какое математическое объяснение можно дать формуле, используемой в интерполяционном поиске? - C++

Восстановить пароль Регистрация
 
Гузель23
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56
24.04.2014, 17:34     Какое математическое объяснение можно дать формуле, используемой в интерполяционном поиске? #1
какое математическое объяснение можно дать формуле, используемой в интерполяционном поиске?
как объяснить ее с математической точки зрения?

C++
1
mid = l + ((k - a[l]) * (r - l)) / (a[r] - a[l]);
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
k-ключ поиска;
int l = 0;//левая граница массива-начало
int r = n - 1;//прав граница-конец массива
int mid;//индекс значения, с которым будем сравнивать k
//цикл интерполирующего поиска
while (a[l] < k && a[r] >= k)
{
//интерполирующий поиск производит оценку новой области поиска
//по расстоянию между ключом поиска и текущим значение элемента
mid = l + ((k - a[l]) * (r - l)) / (a[r] - a[l]);
//если значение в ячейке с индексом mid меньше, то смещаем нижнюю границу
if (a[mid] < k)
l = mid + 1;
//в случае, если значение больше, то смещаем верхнюю границу
else if (a[mid] > k)
r = mid - 1;
//если равны, то возвращаем индекс
else
return mid;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2014, 17:34     Какое математическое объяснение можно дать формуле, используемой в интерполяционном поиске?
Посмотрите здесь:

C++ Какое максимальное количество натуральных чисел можно выбрать чтобы среди них не было отличающихся в два раза
Измерение используемой памяти C++
За какое время можно досканально изучить C++ C++
Отобразить кол-во используемой дин. памяти C++
Сравнить уравнения и вывесети какое больше и какое меньше C++
Можно ли как-то передавать в функцию то поле, какое нужно печатать C++
За какое наименьшее количество взвешиваний можно обнаружить фальшивую монету? C++
Какое консольное mini-приложение можно сделать с использованием классов (для практики)? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 21:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru