Індексація

У математиці індекс являє собою покажчик, за допомогою якого розрізняють вираження, змінні чи константи в цих вираженнях. Подібну роль грають індекси й у програмуванні. Але ця роль специфічна й обумовлена принципами збереження інформації в пам'яті ЕОМ, особливостями представлення індексованих змінних у різних вираженнях, характером операцій над самими індексами.

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

Виникає ряд складностей. По-перше, називати кожне значення своїм ім'ям і, отже, позначати своїм символом не тільки безглуздо, але і неможливо. Цьому перешкоджає природна обчислювальна процедура. Дані повинні оброблятися на підставі деякого закону, що виражається математичною залежністю, у яку ці дані входять у виді змінної. Але не можна ж при кожнім обчисленні змінювати символ у процедурному вираженні. По-друге, необхідно мати можливість організувати доступ до довільного елемента цієї сукупності. Ця можливість повинна реалізовуватися за допомогою формальних процедур, що дозволяють заздалегідь у програмі передбачити будь-який закон зміни адреси, по якому шукається елемент оброблюваних даних.

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

У псевдомові прийнято використовувати запис індексів подібно їхнього запису в алгоритмічних мовах програмування, де забороняються підрядкові і надрядкові позиції індексів, що в математику є рядовим прийомом індексації.

Основними формами запису індексів можуть бути:

· для одномірних масивів Х (i), Х (4), X(i+2);

· для двовимірного масиву Т (i,k), Т (i, 5), T(6, k).

Тут дані тільки приклади запису змінних з індексами, а не всі припустимі випадки запису індексів. Важливо, що як індекси можуть використовуватися чи символи конкретні числові значення. У дужках, як видно з приклада, можна указати вираження, що використовується для обчислення значення індексу. Потрібно звернути увагу і на те, що кількість індексів у дужках визначає і мірність масиву. Назва "одномірний" говорить про те, що сукупність даних можна перенумерувати (індексувати) натуральним рядом чисел. Це визначає і характер розташування цих даних у пам'яті ЕОМ. Елемент з індексом k = 1 розміщається в осередку з номером N = α, елемент з індексом k = 2 - в осередку з номером N = α + 1 і т.д.

Інакше визначається положення елемента в двовимірному масиві, що є чи таблицею матрицею, що містить рядка і стовпці. Природно, що положення елемента в такій організації масиву повинне визначатися вказівкою номерів рядка і стовпця. Це і відбивається в записі. Перший індекс визначає номер рядка, а другий - номер стовпця.

Масиви можуть бути трьох-, чотирьохмірні і більш, але розглядати будемо, як правило, одне- і двовимірні. При цьому необхідно мати у виді, що всяка обробка масиву обов'язково супроводжується різними операціями і над індексами. У цих операціях не можна допускати появи значень індексів, що виходять за межі, заздалегідь визначені умовами задачі, чи нецілочислені.

Приклади допоможуть виявити ряд цікавих особливостей застосування індексів при обробці різних масивів.

Приклад 3. Дано масив цілих позитивних чисел D, у якому кількість елементів N. Утворити два підмасива числа: парних D_r, і непарних D_n.

Загальна схема рішення задачі досить проста: послідовно перевіряти кожен елемент D_i масиву D і поміщати його в підмасив відповідно D_r чи D_n. Це формулювання містить підказку, що дозволяє визначити характер алгоритму. По-перше, аналізу підлягає кожен елемент D_i масиву і таких процедур повинне бути N. Отже, алгоритм повинний бути циклічним. По-друге, процедура перевірки повинна завершуватися виробленням рішення про віднесення елемента масиву D_i до підмасиву D_r чи D_n. Але це вимагає організації двох галузей і, природно, застосування альтернативного оператора.

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

По-перше, варто звернути увагу на загальний статус алгоритму. Це циклічний алгоритм, у якому вбудовано розгалужений процес. Другий момент стосується операції визначення типу числа. У схемі відзначений тільки логічний оператор, задача якого - визначити цей тип, але як? Відразу відзначимо, що в сучасних ЕОМ, у їхньому програмному забезпеченні є можливості виконання подібної процедури, хоча можна запропонувати в цьому алгоритмі процедуру на базі простих операцій, що і зробимо,

Але колись розглянемо "допоміжні процедури", з'ясуємо їхню роль і особливості. У задачі потрібно сформувати два самостійних масиви, що містить тільки парні і тільки непарні числа. Для цього щораз необхідно вказувати осередок, куди буде міститися черговий елемент. Це можна зробити за допомогою індексів, збільшуючи їхнє значення на одиницю тільки тоді, коли виявиться відповідний елемент масиву. Тоді допоміжні операції до циклу повинні привласнити індексам підмасивів D_r і D_n початкові значення, а після розміщення елементів у відповідний підмасив допоміжні операції повинні збільшувати значення індексів на одиницю. На мал. 3.4 зображена графа-схема алгоритму з оформленням усіх допоміжних операцій. Зверніть увагу на те, що парний і непарний масиви позначено різними символами (виконана вимога ідентифікації різних змінних різними іменами і символами).

Використання окремого оператора для присвоювання індексу i вихідного значення обумовлено поруч причин, що тут ролі не грають, але в багатьох випадках на це необхідно звертати увагу.

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

На мал. 3.5 показаний блок, що може бути розміщений замість частини алгоритму, виділеної пунктиром на мал. 3.4.

Тут використана спадна покрокова деталізація операторів алгоритму. Потрібно звернути увагу на те, що кожний наступний крок при деталізації не торкається тих елементів, що до цього одержали завершену деталізацію. При розміщенні, наприклад, блоку визначення парності числа (див. мал. 3.5) в основний алгоритм не потрібно змінювати нічого, що знаходиться поза виділеним пунктиром частини (див. мал. 3.4). Це не означає, що в самому процесі синтезу алгоритму не виникне потреби що-небудь змінювати, уточнювати, доповнювати. Адже це творчий процес, у якому метод "проб і помилок" відіграє велику роль. На алгоритмі приклада 3.3 можна помітити одну дуже корисну закономірність. Для цього повернемося до мал. 3.3. Зверніть увагу на оператори i:= 1; i:= i + 1 і логічний оператор i ≤ N. Зміст всіх інших операторів поки не деталізовано, а ці мають чітку визначеність. Це оператори організації циклу. При обробці одномірних масивів із заздалегідь відомою кількістю елементів ці оператори завжди такі і завжди знаходяться в такому взаємозв'язку між собою і з іншими операторами. Між ними можуть бути інші цикли, розгалуження, лінійна послідовність операторів і їхніх комбінацій. Підтвердимо це на прикладі.

Приклад 4. Задано двовимірний масив Х розмірністю М´ N. Визначити кількість елементів масиву, значення яких знаходиться в межах А < Х < B.

Загальна стратегія рішення задачі ясна. Необхідно випробувати кожен елемент масиву на входження його в задані межі. Якщо він у межі входить, то в спеціальному лічильнику додають одиницю. Перша підзадача: - організувати перебір всіх елементів матриці. Для цього надійдемо так. Будемо вважати, що мається деякий масив, елементи якого являють собою рядки, кількість яких дорівнює М. Необхідно яким-небудь чином (поки що неважливо, яким) обробити кожен рядок, як деякий елемент.

Але це одномірний масив, обробка елементів якого вимагає типового циклічного алгоритму. Він зображений на мал. 3.6а.

Друга підзадача вимагає обробки кожного елемента рядка, що також є одномірним масивом. Для цього знову використовуємо циклічний алгоритм (мал. 3.6 б). У цьому виявляється рекуррентність.

Третя підзадача - обробка самого елемента двовимірного масиву. Значення елемента необхідно порівнювати з заданими межами A і B. Дня цього буде потрібно альтернативна процедура, що дозволяє установити відношення між елементом X і межею А. Потім необхідна така ж процедура з'ясування відносин між елементами Х и B. Підалгоритм, що вирішує цю задачу, зображений на мал. 3.6в.

Завдання. Здійсніть збірку всього алгоритму, звертаючи увагу на мітки a, b, с и d. Спробуйте з'ясувати суть допоміжної операції на мал. 3.6а, аналізуючи всі оператори зібраного алгоритму.

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

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

Приклад 5. Ряд спостережень заданий у виді невпорядкованого масиву X розміром N. Упорядкувати його по зростанню значень елементів.

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

Цей прийом, його суть наштовхує на думку, що необхідно використовувати циклічний алгоритм, що, взагалі кажучи, правильно. Але при цьому буде вирішена частина задачі. Переконаємося в цьому, аналізуючи незакінчений алгоритм, показаний на мал. 3.7. Для наочності скористаємося масивом Х= {3; 2; 7; 1}.

Перша пара 3 і 2 вимагає перестановки, що дасть ряд 2; 3; 7; 1. Наступна пара 3 і 7 перестановки не вимагає; остання пара 7 і 1 вимагає перестановки і дасть ряд 2; 3; 1; 7. Цикл завершив роботу, оскільки всі елементи (їхні пари) випробувані і пророблені необхідні перестановки, але ряд виявився неупорядкованим, для програміста виникає дві додаткові підзадачи:

1. як задати в алгоритмі операцію, що визначає, що ряд упорядкований (чи неупорядкований)?

2. як організувати повторення циклу?

Те, що повторення циклу необхідно і може виявитися багаторазовим, показує розглянутий ряд і отриманий перший результат. для результату 2; 3; 1; 7 потрібно ще двічі виконати циклічну процедуру цілком, оскільки після першої процедури буде отриманий результат 2; 1; 3; 7. Ряд знову неупорядкований.

Розглянемо характер роботи алгоритму, якщо ряд упорядкований і являє собою послідовність I; 2; 3; 7. Логічний оператор буде увесь час формувати предикат Р = НЕПРАВДА. Процес буде направлятися по галузі "НІЧОГО НЕ РОБИТИ". Якщо ж у ході обробки ряду виникне ситуація, що вимагає перестановки, то процес пройде по робочій галузі. Це дозволяє доповнити галузь операцій (на мал. 3.7 вона позначена як допоміжна), що буде змінювати стан "індикатора" Інд. Перед початком виконання циклу індикатор Інд повинний одержати значення, наприклад, 0, а при виконанні перестановки - 2 (можна будь-яке число).

Остаточний варіант алгоритму буде мати вид, зображений на мал. 3.8. Основний цикл виявляється вкладеним у цикл ітеративного характеру, де кількість повторень заздалегідь не визначена. Оператор Інд ≠ 0 перевіряє стан індикатора Інд і направляє процес на повторне виконання внутрішнього циклу, відновлюючи вихідне значення індикатора Інд:= 0 і початкове значення індексу ДО:= 1. Зверніть увагу на оператор K < (N-1). Тут не можна використовувати K<N, тому що кількість послідовних пар елементів ряду N-1.

Звернемо увагу на один, на перший погляд другорядний, момент. В алгоритмі (мал. 3.8) є оператор присвоювання А:= X(ДО). Чи потрібний він? Для виконавця - ЕОМ такий оператор обов'язковий. При обміні місцями елементів масиву, що упорядковується, передбачений оператор X(K):=Х(K+1).Після його виконання в двох осередках виявиться значення елемента Х(K+1), а значення елемента Х(ДО) буде стертим. Оператор А:= Х(ДО) створює репродукцію елемента, що міститься оператором Х(K+1):=А на відповідне місце. Подібний прийом використаний і в прикладі алгоритму на мал. 3.5. Там зі значення елемента D(I) варто віднімати двійку для визначення його парності. Але потім цей елемент необхідний при організації підмасива відповідно E(j) і Q (к). Якщо не зробити репродукції, що зберігає значення елемента, то щось потрібно буде поміщати в необхідний підмасив.

При обробці інформації можливі різні ситуації, при яких виникає потреба зберегти значення якої-небудь змінної на час маніпуляцій цим значенням, що можуть його змінити, стерти з пам'яті. У таких випадках завжди передбачаються операції по репродукуванню значення змінної.

Ці кілька прикладів ілюструють не стільки різноманіття задач, скільки одноманітність типів алгоритмів, на базі яких можна створювати необхідні алгоритми. Крім того, цілком очевидні закономірності в послідовності і взаємозв'язку операторів, що забезпечують організацію циклів. Можна помітити визначені закономірності і при організації розвітвлюючихся процесів. Для узагальнення таких закономірностей можна скористаємося аналітичною формою представлення алгоритмів, основи якої були закладені А.А. Ляпуновим і його учнями ще в середині 50-х років [ ].