Вгадайте, яке найулюбленіше заняття багатьох викладачів? підказую: Відмовити в своїх класних кімнатах страшно академічні слівця, щоб у студентів волосся стало дибки від мегаулетності його сенсея. Одне з таких підступних словечок, валить молодих людей в шок – інтерполяція. Пропоную оглянути це чудо математичної думки з самого найпростішого ракурсу і використовуючи мінімум коду, щоб не муляли очі тоннами операторів, заплутуючи себе в теорії.
Итак, для начала – що ж це за слово таке “інтерполяція”? інтерполяція – це (якщо говорити мовою студента) визначення області пошуку, шляхом обчислення подібності відстаней між шуканим значенням і всією областю. Пам'ятайте по геометрії подобу трикутників? вони, у яких однакові за значенням кути, але пропорції різні. Тут практично той же принцип. Обчислюється довжина області пошуку, і довжина від початку області до якогось числа (скажімо до центрального елемента в масиві). Обчислення це проводиться як з номерами елемента, так і з їх значеннями, після чого отримана довжина області множиться на довжину між значеннями, і результат доданий до значення з початку області дає шукане.
Складно відразу зрозуміти на словах, тому спробую показати картинкою:
Формула досить проста – обчислюється довжина між номерами першого елемента і шуканого (задається точніше). Така ж довжина вважається між першим і останнім номерами. Довжини між собою діляться, як раз і отримуючи обчислення подібності. Те ж саме відбувається зі значеннями елементів – так само обчислюється відстань між граничними значеннями в масиві. Спеціально виділяю кольором поняття і пов'язані з ними частини формули.
Отримана довжина номерів елементів масиву множиться на довжину значень в цих (межують) елементах і додається значення в першій клітинці масиву.
Получается: 1 + (20-1)/(100-1) * (200-5) = 38 з копійками.
Результат і є те саме шукане. Тобто,. при таких значеннях як на картинці в осередку №20 буде стояти 38. Ось і весь сенс інтерполяції – складання подібності між номерами елементів і між значеннями елементів.
На С ++ це виглядає так:
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 | #include <iostream> using namespace std; int main() { //Массив значений в котором пойдет поиск int MyArray[] { 1, 2, 4, 6, 7, 89, 123, 231, 1000, 1235 }; int x = 0; //Текущая позиция массива, с которым сравнивается искомое int a = 0; //Левая граница области, где ведется поиск int b = 9; //Правая граница области, где ведется поиск int WhatFind = 123; //Значение, которое нужно найти bool found; //Переменка-флаг, принимающая True если искомое найдено /************ Начало интерполяции *******************************/ //Цикл поиска по массиву, пока искомое не найдено //или пределы поиска еще существуют for (found = false; (MyArray[a] < WhatFind) && (MyArray[b] > WhatFind) && !found; ) { //Вычисление интерполяцией следующего элемента, который будет сравниваться с искомым x = a + ((WhatFind - MyArray[a]) * (b - a)) / (MyArray[b] - MyArray[a]); //Получение новых границ области, если искомое не найдено if (MyArray[x] < WhatFind) a = x + 1; else if (MyArray[x] > WhatFind) b = x - 1; else found = true; } /************** Конец интерполяции ***************************/ //Если искомое найдено на границах области поиска, показать на какой границе оно if (MyArray[a] == WhatFind) cout << WhatFind << " founded in element " << a << endl; else if (MyArray[b] == WhatFind) cout << WhatFind << " founded in element " << b << endl; else cout << "Sorry. Not found" << endl; return 0; } |
Таким чином сам цикл просто обчислює за формулою область масиву, де може перебувати шукане використовуючи цей самий принцип інтерполяції в С ++, підбираючи подібності так би мовити. Якщо обчислене не дорівнює шуканого, значить потрібно зрушити кордону області, де проходить обчислення.
Якщо обчислене більше – зсувається права межа області пошуку, якщо менше – ліва. так відрізаючи (як в бінарному пошуку) шматок масиву за шматком поступово досягається потрібна комірка масиву, ну або кордону області пошуку звужуються до таких величин, в межах якого вже шукати нічого, коли дистанція між кордонами дорівнює 1 (т.е. між точкою А і В немає більше елементів для обчислення) рішення говорить про те, що значення в масиві, не знайдено.
Як бачите сам цикл не настільки вже й складний і жахливий. Вся сіль то прихована в його форумі. А решта – просто перевірки: знайшли або далі шукати. Ось така от вона… інтерполяція в C ++
Інтерполяційний пошук в чомусь нагадує двоичный. Тільки в ньому область пошуку не ділиться на дві рівні частини. Замість цього проводиться оцінка нової області пошуку по відстані між поточним значенням елемента і ключем пошуку. Швидкість роботи інтерполюючого пошуку перевершує швидкість довічного. Ще одна вагома відмінність інтерполюючого пошуку від довічного – можливість шукати текстову інформацію, а не тільки числові значення.
Думаю це одна з тих тем, яка на практиці простіше ніж на словах)
У коді помилка : для масиву { 52,26,64 ,53, 46, 53, 39, 54, 41, 40, 38 ,53, 38, 45, 32, 29 ,40, 41 } неправильно знаходить індекс числа 45. виправляється легко.
природно, якщо масив спочатку впорядкувати за зростанням.
Двійковий пошук прекрасно шукає текстову інформацію.