Основи програмування на С ++ для початківців

інтерполюються пошук

Вгадайте, яке найулюбленіше заняття багатьох викладачів? підказую: Відмовити в своїх класних кімнатах страшно академічні слівця, щоб у студентів волосся стало дибки від мегаулетності його сенсея. Одне з таких підступних словечок, валить молодих людей в шок – інтерполяція. Пропоную оглянути це чудо математичної думки з самого найпростішого ракурсу і використовуючи мінімум коду, щоб не муляли очі тоннами операторів, заплутуючи себе в теорії.

Итак, для начала – що ж це за слово таке “інтерполяція”? інтерполяція – це (якщо говорити мовою студента) визначення області пошуку, шляхом обчислення подібності відстаней між шуканим значенням і всією областю. Пам'ятайте по геометрії подобу трикутників? вони, у яких однакові за значенням кути, але пропорції різні. Тут практично той же принцип. Обчислюється довжина області пошуку, і довжина від початку області до якогось числа (скажімо до центрального елемента в масиві). Обчислення це проводиться як з номерами елемента, так і з їх значеннями, після чого отримана довжина області множиться на довжину між значеннями, і результат доданий до значення з початку області дає шукане.

Складно відразу зрозуміти на словах, тому спробую показати картинкою:

інтерполюються пошук в с ++, c ++ для початківців, алгоритм пошуку доповідь, курсова робота

Формула досить проста – обчислюється довжина між номерами першого елемента і шуканого (задається точніше). Така ж довжина вважається між першим і останнім номерами. Довжини між собою діляться, як раз і отримуючи обчислення подібності. Те ж саме відбувається зі значеннями елементів – так само обчислюється відстань між граничними значеннями в масиві. Спеціально виділяю кольором поняття і пов'язані з ними частини формули.

Отримана довжина номерів елементів масиву множиться на довжину значень в цих (межують) елементах і додається значення в першій клітинці масиву.

Получается: 1 + (20-1)/(100-1) * (200-5) = 38 з копійками.

Результат і є те саме шукане. Тобто,. при таких значеннях як на картинці в осередку №20 буде стояти 38. Ось і весь сенс інтерполяції – складання подібності між номерами елементів і між значеннями елементів.

На С ++ це виглядає так:

Таким чином сам цикл просто обчислює за формулою область масиву, де може перебувати шукане використовуючи цей самий принцип інтерполяції в С ++, підбираючи подібності так би мовити. Якщо обчислене не дорівнює шуканого, значить потрібно зрушити кордону області, де проходить обчислення.

Якщо обчислене більше – зсувається права межа області пошуку, якщо менше – ліва. так відрізаючи (як в бінарному пошуку) шматок масиву за шматком поступово досягається потрібна комірка масиву, ну або кордону області пошуку звужуються до таких величин, в межах якого вже шукати нічого, коли дистанція між кордонами дорівнює 1 (т.е. між точкою А і В немає більше елементів для обчислення) рішення говорить про те, що значення в масиві, не знайдено.

Як бачите сам цикл не настільки вже й складний і жахливий. Вся сіль то прихована в його форумі. А решта – просто перевірки: знайшли або далі шукати. Ось така от вона… інтерполяція в C ++

Інтерполяційний пошук в чомусь нагадує двоичный. Тільки в ньому область пошуку не ділиться на дві рівні частини. Замість цього проводиться оцінка нової області пошуку по відстані між поточним значенням елемента і ключем пошуку. Швидкість роботи інтерполюючого пошуку перевершує швидкість довічного. Ще одна вагома відмінність інтерполюючого пошуку від довічного – можливість шукати текстову інформацію, а не тільки числові значення.

6 думки про "інтерполюються пошук

  1. У коді помилка : для масиву { 52,26,64 ,53, 46, 53, 39, 54, 41, 40, 38 ,53, 38, 45, 32, 29 ,40, 41 } неправильно знаходить індекс числа 45. виправляється легко.

  2. Трохи поліпшив ваш код, так як алгоритм не працював з масивом [0…9] например, тоесть коли a = 0, b = колічество_елементов – 1.
    Потрібно просто додати код
    else if (MyArray[x] == WhatFind)
    cout << WhatFind << " знайдено в елементі " << x << endl;
    в потрібне місце.
    змінено:
    #include
    #include
    using namespace std;
    #визначити N 10
    int main()
    {
    int MyArray[N] = {0,1,2,3,4,5,6,7,8,10};
    /*for (int i = 0; i < N; i )
    {
    MyArray[i] = i;
    }*/
    INT х = 0;
    int a = 0;
    int b = N-1;
    int WhatFind = 10;
    bool знайдено;
    for (знайдено = брехня; (MyArray[a] WhatFind) && !знайдений; )
    {
    x = a + ((WhatFind – MyArray[a]) * (b – a)) / (MyArray[b] – MyArray[a]);
    if (MyArray[x] WhatFind)
    б = х – 1;
    else
    знайдено = правда;
    }
    if (MyArray[a] == WhatFind)
    cout << WhatFind << " знайдено в елементі " << a << endl;
    else if (MyArray[b] == WhatFind)
    cout << WhatFind << " знайдено в елементі " << b << endl;
    else if (MyArray[x] == WhatFind)
    cout << WhatFind << " знайдено в елементі " << x << endl;
    else
    cout << "Sorry. Не знайдено" << endl;
    return 0;
    }

  3. В загальному, пошук працює тільки у відсортованому масиві, як у випадку і з бінарним пошуком. Було б добре, якби подібна інформація вказувалася, але всеодно – дякую за інфу.

залишити коментар

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *