3. Типи циклів та перевірка умов закінчення циклів двійкового пошуку на мові асемблера

При обробці таблиць з використанням доступу за прямою адресою ключові поля пошуку звичайно не використовуються, а використовуються лише прямі адреси, номери або покажчики елементів. Шаблони розв’язання задач комп’ю­тер­но­го практикуму spLb1 включають відповідні заголовки та реалізації таких функцій. Базовою підпрограмою для всіх цих функцій є підпрограма вибірки, до якої звертаються при виконанні всіх підпрограм комплексу.

Завдання на підготовку до роботи з комп’ютерного практикуму

Завдання на підготовку до роботи на комп’ютері:

Відношення подібності

При пошуку помилково підготовлених слів в текстових ре­дакторах та процесорах часто виникає потреба в визначенні схо­жості ключів пошуку. Такі дії часто виконуються в текстовому про­це­сорі MS Word. Вони можуть будуватися на підрахунку кіль­кості однакових n_e, схожих літер n_si за i-м типом схожості, а також літер, які не мають відповідника в іншому ключі і можуть спиратися на аб­солютні і відносні формульні критерії схожості. Схожість літер може визначатися залежно від випадку аналізу за схожістю напи­сан­ня літер в різних алфавітах n_s1, за близькістю комп’ю­тер­них кодів n_s2 та за близькістю розташування на клавіатурі n_s3, а також з урахуванням кількості літер n_s4, які не мають відповідників в обох ключах.

При створенні програм порівняння за мірою близькості треба побудувати загальний критерій близькості як монотонну функцію f(n_s1, n_s2, n_s3, n_s4) в одному напрямку від n_s1, n_s2 і n_s3 та в іншому напрямку від n_s4. Крім того, попередньо необхідно організувати підрахунок n_s1, n_s2, n_s3 і n_s4, при порівняльному перегляді ключів, які порівнюються. Результат пошуку за таким критерієм може бути неоднозначним, навіть за умови вимоги однозначності ключів. На алгоритм лінійного пошуку це практичного не впливає, а у випадку базового двійкового пошуку доцільно починати пошук навколо найближчого ключа, знайденого за відношенням порядку.

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

Таблиця 8.1

Варіанти завдань для виконання порівняння ключів з використанням міри схожості

№ вар.	Тип функції порівняння за мірою схожості
1	Спiвпадіння максимуму початкових літер у ключі.
2	Спiвпадіння максимальної кількості літер без урахування їх послідовності у ключі.
3	Спiвпадiння максимальної кількості літер з врахуванням послідовності їх входження у ключі.
4	Спiвпадіння максимуму початкових літер без врахування регістрів великих i маленьких літер.
5	Співпадіння максимальної кількості літер без врахування регістрів i їх послідовності в ключі.
6	Співпадіння максимальної кількості літер з врахуванням їх послідовності без врахування регістрів літер.
7	Співпадіння максимуму початкових літер, включаючи літери латинського i слов'янського алфавіту, що співпадають за написанням.
8	Співпадіння максимальної кількості літер, включаючи літери латинського i слов'янського алфавіту, що співпадають за написанням.
9	Співпадіння максимуму початкових літер, включаючи літери латинського i слов'янського алфавіту, що співпадають за написанням інваріантно до регістру літер.
10	Спiвпадiння максимальної кількості літер, включаючи літери латинського i слов'янського алфавіту, що співпадають за написанням iнварiантно до регістру літер.

Завдання на самостійну роботу: повторити матеріал лекції; вивчити основні поняття.

/ В.І.Пустоваров /