Материал: 252_337

Якщо продовжити хід міркувань далі, то можна дійти вис­ новку, що бажано намагатися перетворити таблицю елементів усіх п пристроїв керування таким чином, щоб у кожному пристрої керування лише один елемент дорівнював 1, а решта були 0. Причому всі ці одиничні елементи були на різних по­ зиціях, тобто а\ = 1, а^ = 0 для і, k = 1, 2, ..., п. Цей запис озна­ чає, що задану таблицю пристроїв керування можна звести до такого вигляду, коли всі елементи матимуть значення «0» і ли­ ше елементи головної діагоналі дорівнюватимуть «1»:

1 0 0 . . . 0

0 1 0 . . . 0

0 0 1 ...0

0 0 0 . . . 1 При цьому результативність використання перетворених

пристроїв керування буде такою самою, як і заданих. А як ско­ ристатися новою системою пристроїв керування? Оскільки тепер кожний із перетворених пристроїв керування впливає лише на один із елементів заданого пристрою, то залишається вибрати тільки ті з них, що виконають перетворення не­ обхідних елементів заданого пристрою.

Розглянемо наведений на початку приклад. Якщо з початко­ вого стану 0,1,1,0,1 необхідно перейти у кінцевий стан 0,0,1,1,0, то нескладно помітити, що при цьому змінилися тільки стани другого, четвертого та п'ятого елементів. Тому з перетвореної матриці пристроїв керування необхідно вибрати лише ті, що мають у цих позиціях значення 1 і таким чином після застосування змінять значення необхідних елементів за­ даного пристрою.

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

Традиційно розглянемо покрокове виконання описаного алго­ ритму на прикладі. Спочатку займемося зведенням таблиці еле­ ментів пристроїв керування до трикутного вигляду (мал. 178).

Домовимося про такі позначення. У стовпцях «Ознаки засто­ сування ПК (пристроїв керування)» визначатимемо рівень ви­ користання і-го пристрою керування: «+» - ПК використо-

322

Мал. 178

вується для перетворення таблиці на поточному кроці; «X» - ПК уже використовувався для перетворення таблиці; «/» - ПК, над яким виконується перетворення на поточному кроці. У стовпцях «Стан елементів ПК» у кожному і-му рядку містять­ ся значення елементів і-го пристрою керування на момент ви­ конання поточного кроку перетворення. У стовпцях «Послідов­ ність застосування ПК» міститься інформація про використан­ ня пристроїв керування для перетворення таблиці на поточному кроці: у-й елемент і-го рядка містить інформацію про загальну кількість використання j-то пристрою керування для перетво­ рення таблиці на момент виконання поточного кроку.

Розглянемо перший крок (мал. 178, а). Стан елементів ПК збігається з початковим їх станом. На першому кроці викону­ ватиметься перетворення перших елементів пристроїв керу­ вання (стовпець виділений сірим кольором).

Який із пристроїв керування взяти? Оскільки ми нама­ гаємося отримати у цьому стовпці лише одне значення «1», то і шуканий рядок має містити у першому стовпці значення «1». Таких рядків у нашому випадку є два: третій і п'ятий. З них можна взяти будь-який, але логічно зупинитися на першому з них зверху. Саме він позначений символом «+».

А до яких рядків цей пристрій керування буде застосова­ ний? Зрозуміло, що до тих наступних, у яких перший елемент дорівнює «1». Саме це дасть змогу перетворити їх значення на «0». Такий рядок на першому кроці виконання алгоритму є ли­ ше один, і він розташований на п'ятій позиції та позначений символом «/».

У стовпцях, що визначають послідовність застосування ПК, поки що визначені лише самі ці пристрої: для першого при­ строю лічильник застосування цього пристрою встановлений на 1, для другого пристрою значення 1 стоїть у позиції 2, для третього - у позиції 3 і т. д. Результат виконання першого кро­ ку зображений на малюнку 178, б: у першому стовпці для всіх пристроїв керування, окрім третього, значення перетворилися

323

на «О». Це означає, що для того щоб перетворити значення пер­ шого елемента заданого пристрою на протилежне, необхідно скористатися лише третім пристроєм керування, решта при­ строїв керування ніяких змін не дасть.

Перейдемо до другого кроку (мал. 178, б). Спочатку позначи­ мо 3-й пристрій символом «X», що означає подальшу заборону використання цього пристрою для перетворення значень інших пристроїв. У результаті застосування 3-го пристрою до 5-го пристрою значення останнього з послідовності 1,0,1,1,0 перетворяться на 0,0,1,0,1 (див. 5-й рядок мал. 178, б). Змі­ ниться і послідовність застосування пристроїв керування до 5-го ПК: для його перетворення на попередньому кроці був за­ стосований 3-й пристрій, тому значення третього елемента цієї послідовності збільшиться на 1, і ця послідовність набуде ви­ гляду 001 0 1.

На другому кроці змінюватимемо значення другого стовпця, що відмічений сірим кольором. Перша одиниця у цьому стовпці зустрічається у першому пристрої керування. Виби­ раємо його для наступних перетворень і помічаємо символом «+». Для перетворення визначаємо 2-й та 4-й рядки, де на другій позиції стоять значення «1». їх треба прибрати, зали­ шивши значення «1» тільки у другій позиції 1-го пристрою ке­ рування. Цим буде досягнута можливість впливу на значення 2-го елемента заданого пристрою лише одним із пристроїв ке­ рування, а саме першим. Результат виконання другого кроку зображений на малюнку 179, а.

На третьому кроці (мал. 179, а) відбувається перетворення елементів третього стовпця (сірий колір). Перше значення «1» зустрічається у 1-му пристрої керування, але цей пристрій був уже попередньо використаний для перетворень, тому вико­ нуємо пошук далі. Варто зупинитись і пояснити, чому не мож­ на використати повторно раніше використаний пристрій. Це пояснюється дуже просто: якщо пристрій використовувався, то на попередніх (і - 1)-х кроках один із його елементів 1, 2, ...,

324

(і - 1) може мати значення «1». А це значить, що при повторно­ му використанні цього елемента іншим пристроєм керування його значення буде змінене. Як видно з значень 1-го і 2-го стовпців поточного стану елементів ПК (мал. 179, а), вони вже зведені до необхідного вигляду: у кожному стовпці лише по од­ ному значенню «1».

Проаналізуємо, як змінилися послідовності використання пристроїв керування на третьому кроці. Оскільки на другому кроці до пристроїв 2 і 4 був застосований пристрій 1, то і лічильники першого елемента цих пристроїв збільшені на 1. Послідовність застосуваня пристроїв до пристрою 2 буде мати вигляд 1 1 0 0 0, & до пристрою 4-10010.

Повернемося назад до виконання третього кроку алгоритму. Наступний пристрій, що має для 3-го елемента значення «1» - 5-й пристрій. Помічаємо його символом «+». Шукаємо при­ стрій, до якого його треба застосувати, перетворивши значення «1» у третьому стовпці на значення «0». Таким є пристрій 1: позначимо його символом «X».

Результат виконання третього кроку зображений на малюн­ ку 179, б: перші три стовпці мають значення «1» лише в одній із позицій.

Четвертий (мал. 179, б) і п'ятий (мал. 180, а) кроки ана­ логічні попереднім. Результат виконання всіх п'яти кроків зображений на малюнку 180, б: кожний із пристроїв керування був застосований для перетворення, таблиця стану елементів пристроїв керування зведена до необхідного вигляду (у кож­ ному рядку і стовпці лише один елемент дорівнює 1), а в таблиці послідовностей застосування пристроїв керування до кожного з них міститься інформація про кількість таких застосувань.

Тепер можна переходити до фінального етапу алгоритму: визначення мінімальної кількості пристроїв керування, які необхідно застосувати до заданого пристрою, щоб перевести його з початкового стану 0,1,1,0,1 у кінцевий 0,0,1,1,0. Оскільки необхідні зміни лише 2, 4 і 5 елементів, то слід ско­ ристатися інформацією про перетворені пристрої керування 1,

325

2 і 4, оскільки саме вони у позиціях 2, 4 і 5 мають значення «1», а на решту елементів початкового стану заданого при­ строю не вплинуть. А які пристрої керування і скільки разів були використані для переведення пристроїв 2, 4, 5 у стан, отриманий на. останньому кроці? Ця інформація міститься у таблиці послідовностей застосування ПК (мал. 180, б): перший пристрій був застосований 6 разів (1 + 3 + 2), другий - 3 рази (0 + 2 + 1), третій - 1 (1 + 0 + 0), четвертий - 2 (0 + 1 + 1), п'ятий - 1 (1 + 0 + 0).

Як відомо, парна кількість застосувань одного і того самого пристрою не змінює початковий стан елементів заданого, а непарна переводить у протилежний стан. Скориставшись цією властивістю, отримаємо відповідь, що для переведення задано­ го пристрою керування з початкового стану 0,1,1,0,1 у кінце­ вий 0,0,1,1,0 небхідно застосувати пристрої керування 2, 3, 5.

Перевірка цієї відповіді проста. Можна піти двома шляха­ ми. Застосуємо почергово пристрої керування 2, 3, 5 у їх неперетвореному варіанті до початкового стану заданого пристрою:

01101 0 1 1 1 0 > о о о і і 1 0 0 1 1 , ю о о о 1 0 1 1 0 , о о і ю .

Як бачимо, шуканий результат отримано.

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

о т о 1 0 0 1 1 > і і ю і 1 0 1 1 0 > о ю і і .

Отримано «універсальний» пристрій керування, який замі­ нює всі три пристрої керування 2, 3, 5 і має значення «1» лише у тих позиціях, значення яких необхідно змінити на проти­ лежні у сформульованій задачі.

Останні дві перевірки зроблені лише для того, щоб практично пересвідчитися у справедливості запропонованого алгоритму.

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

forj := 1 to n do

if і = j then s[i, j] := 1 else s[i, j] := 0;

326