розділ 2.1),
масив, що підлягає адресному сортуванню, можу бути розділено на m підмасивів
(2 Ј m Ј n), що обробляються паралельними гілками (значення m визначається
кількістю наявних апаратних засобів). Окрема гілка послідовно здійснює вставки
елементів j-го підмасиву (j = 1, 2, …, m) у вихідний масив. Породження
відповідної ПРС алгоритму здійснюється із використанням ГСП та розподілених
гіперсхем. Для їх отримання у наведених вище ГСП G2 і РГС R2 потрібно замінити
гілку ВСТАВ(j) на складений оператор послідовної обробки j-го підмасиву, а
параметр n замінити на m.
2.2.3 Алгоритм адресного пошуку
За допомогою адресного сортування вхідний масив переводиться у вихідний масив М
із зворотною адресацією, за якої кожному номеру елемента масиву М ставиться у
взаємно однозначну відповідність номер цього ж елемента , що він мав у вхідному
масиві . Номери заносяться у масив індексів . Алгоритм пошуку ґрунтується на
умові локалізації мінімальних елементів дискретної числової послідовності,
заданої в масиві . Дана умова (нижче умова локалізації) використовує масив
вхідних індексів відсортованих елементів, отриманий в результаті сортування .
Локально мінімальним вважається елемент масиву, не більший попереднього і
наступного, але менший хоча б одного з цих двох елементів. Умова локалізації
має вигляд:
, (2.1)
де , – елементи масиву індексів , отриманого на виході сортування масиву ; ; .
Якщо умова (2.1) не виконується для деякого елемента хоча б при одному із
наведених значень , то це означає, що елемент = [1 Тут у квадратних дужках
зазначені індекси елементів масивів.] відсортованого масиву М не є локально
мінімальним елементом числової послідовності . Навпаки, істинність даної умови
для елемента при усіх означає, що елемент є локальним мінімумом.
За допомогою умови локалізації в масиві може здійснюватися пошук мінімальних і
заданих елементів довільного типу. Зокрема, пошук заданого числа здійснюється
як локалізація нуля в масиві, складеному з модулів почленних різниць між
елементами вхідного масиву і шуканим числом. Відзначимо, що при знаходженні
елементів за умовою локалізації в ланцюжку рівних елементів локально
мінімальним виявляється тільки перший елемент. Для знаходження послідовно
повторюваних із довільною кратністю елементів потрібно брати . Даний варіант
використовується в алгоритмі пошуку, наведеному нижче.
Подамо за допомогою засобів САА оснований на адресному сортуванні і умові
локалізації алгоритм пошуку заданого числа в цілочисленому масиві . Початкова
розмітка масиву буде такою:
,
де – вказівник; , – маркери, що відзначають початок і кінець . На вхід
алгоритму адресного сортування АДРСОРТ?П(М0, М, n) подається масив , складений
з модулів почленних різниць елементів масиву і шуканого числа . Його розмітка
буде такою:
,
де , ; – вказівник; , – маркери. Результат сортування масиву заноситься у масив
М:
,
де – вказівник, Н і К – маркери. Масив індексів відсортованих елементів у
вхідному масиві має вигляд:
,
де , – вказівники; , – маркери. У процесі пошуку вказівник оглядає кожний
елемент , , з умови локалізації (2.1). Елемент, що оглядається, знаходиться
безпосередньо справа від вказівника (даний елемент позначається ). Вказівник
оглядає елементи , з (2.1). У процесі сортування в розмітки масивів , М та
вводяться також вказівники, розглянуті в підрозділі 4.2. Регулярна схема
алгоритму пошуку буде такою:
ПОШУК?А
ЗНАЙТИ_ЧИСЛА * ФІН,
ЗНАЙТИ_ЧИСЛА
де АБС – функція, що повертає модуль числа; – елемент масиву , розташований
безпосередньо справа від вказівника ; – установка вказівника на ; – зсув на 1
елемент вліво; – умова, істинна, якщо для елементів і масиву умова (2.1) не
виконана; – оператор обробки знайденого у масиві елемента по ; – зсув
вказівника на елементів вправо.
Сутність наведеного алгоритму полягає в наступному. Спочатку виконується
сканування вказівника по масиву , а вказівника по масиву із занесенням модулів
в елементи по . Далі за допомогою оператора сортується масив модулів різниць .
Потім здійснюється пошук входжень числа q в масиві за допомогою складеного
оператора ЗНАЙТИ_ЧИСЛА. При цьому вказівники і сканують у напрямку зліва
направо по масиву М і масиву індексів відповідно. Для кожного з елементів по
здійснюється перевірка умови . Для цього вказівник зміщується на 2 елементи
вліво від позиції вказівника і далі в циклі зміщується в напрямку до початку
масиву . Цикл виконується доти, поки не досягне початку масиву або виконається
умова (елемент масиву М не є локально мінімальним елементом послідовності ).
Якщо після виходу із циклу умова не є істинною, і елемент по в масиві М
дорівнює нулю, то шуканий елемент знайдено. Його індекс у вхідному масиві
дорівнює значенню елемента по в масиві індексів. Для обробки знайденого
елемента вказівник зміщується від початку масиву на елементів вправо, після
чого елемент обробляється за допомогою оператора . Далі вказівник зміщується на
елемент вправо по масиву М, а – по масиву з продовженням пошуку інших елементів
масиву , рівних . Відзначимо, що при заміні в схемі умови на в масиві буде
здійснюватися пошук елементів, що відрізняються від заданого не більше ніж на
.
2.2.4 Застосування адресного сортування
Крім розглянутого в попередньому пункті пошуку, адресне сортування може
застосовуватися для знаходження наближених значень коренів многочлена і при
розв’язанні задач розпізнавання [79, 80]. Для знаходження коренів многочлена на
вхід сортування подається послідовність значень модуля даного многочлена на
рівномірній сітці. За допомогою умови локалізації визначаються всі мінімуми
сер
- Київ+380960830922