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

Интерполяционный поиск - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.88
hazerot
2 / 2 / 0
Регистрация: 13.05.2012
Сообщений: 46
14.06.2012, 19:41     Интерполяционный поиск #1
Напишите плиз реализацию данного поискать. Сорри если что за повтор темы
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.06.2012, 19:41     Интерполяционный поиск
Посмотрите здесь:

C++ Бинарный и интерполяционный поиск
C++ интерполяционный многочлен Лагранжа
C++ Интерполяционный многочлен Ньютона
C++ Построить интерполяционный многочлен и интерполяционный сплайн
C++ Интерполяционный поиск
C++ Интерполяционный следящий поиск
Интерполяционный поиск C++
Дихотомия и интерполяционный поиск по отсортированному массиву C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
14.06.2012, 19:47     Интерполяционный поиск #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <iomanip>
//прототипы функций
int interpolatingSearch (int[], int, int);
void printArray (int[], int);
using namespace std;
int main()
{
//резервируем память для переменных
const int size = 18;
int array[size] = {2,5,8,12,23,35,36,41,52,54,55,57,63,67,81,83,87,91};
int key, result;
//запрашиваем и сохраняем ключ поиска
cout << "Enter a key of search: ";
cin >> key;
//печатаем массив
printArray (array, size);
//вызываем функцию интерполирующего поиска
//сохраняем, возвращенное ею значение, в переменную result
result = interpolatingSearch (array, size, key);
if (result != -1)
//значение найдено - выводим его индекс
cout << "Value is found in an element with an index " << result << endl;
else
//значение не найдено
cout << "Value is not found" << endl;
return 0;
}
//функция, выполняющая интерполирующий поиск
//в качесте аргументов принимает массив, размер массива и ключ поиска
int interpolatingSearch (int a[], int arraySize, int keyOfSearch)
{
//объявляем необходимые локальные переменные
//изначально устанавливаем нижний индекс на начало массива,
//а верний на конец массива
int low = 0;
int high = arraySize - 1;
int mid;
//цикл интерполирующего поиска
while (a[low] < keyOfSearch && a[high] >= keyOfSearch)
{
//интерполирующий поиск производит оценку новой области поиска
//по расстоянию между ключом поиска и текущим значение элемента
mid = low + ((keyOfSearch - a[low]) * (high - low)) / (a[high] - a[low]);
//если значение в ячейке с индексом mid меньше, то смещаем нижнюю границу
if (a[mid] < keyOfSearch)
low = mid + 1;
//в случае, если значение больше, то смещаем верхнюю границу
else if (a[mid] > keyOfSearch)
high = mid - 1;
//если равны, то возвращаем индекс
else
return mid;
}
//если цикл while не вернул индекс искомого значения,
//то проверяем не находится ли оно в ячейке массива с индексом low,
//иначе возвращаем -1 (значение не найдено)
if (a[low] == keyOfSearch)
return low;
else
return -1;
}
//функция, печатающая массив
void printArray (int b[], int sizeOfArray)
{
cout << "Indexes: " << endl;
for (int i = 0; i < sizeOfArray; i++)
cout << setw(4) << i;
cout << endl;
for (int i = 0; i < sizeOfArray; i++)
cout << "----";
cout << endl;
for (int i = 0; i < sizeOfArray; i++)
cout << setw(4) << b[i];
cout << endl << endl;
}
hazerot
2 / 2 / 0
Регистрация: 13.05.2012
Сообщений: 46
14.06.2012, 19:55  [ТС]     Интерполяционный поиск #3
спасибо боооольшшооое
Yandex
Объявления
14.06.2012, 19:55     Интерполяционный поиск
Ответ Создать тему
Опции темы

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