загрузка...
загрузка...
На головну

Логічні алгоритми

  1. II. Психологічні аспекти ділового спілкування
  2. IV. 14.2. Фізіологічні основи емоційних станів
  3. V. 16.2. Фізіологічні основи темпераменту
  4. V. 17.2. Фізіологічні основи характеру
  5. А. Неврологічні порушення
  6. Авторитаризм і демократія - психологічні виміри політичних режимів
  7. Акмеологічні дослідження художньо-творчої діяльності

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

1.3.1. Завдання "Пошук шляху в лабіринті"

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

Розглянемо задачу пошуку шляху в лабіринті в загальному випадку.

Уявімо лабіринт у вигляді кінцевої системи майданчиків, від яких розходяться коридори, причому кожен коридор з'єднує два майданчики (будемо називати їх суміжними); Можливе існування таких майданчиків, з яких можна пройти тільки в один коридор (такі майданчики будемо називати тупиками). Геометрично лабіринт можна представити у вигляді системи точок А, В, С, ..., що зображують майданчики, і сукупності відрізків АВ, ВС, ..., що зображують коридори, які з'єднують певні пари даних точок (рис. 1.16). Суміжними є, наприклад, майданчики В і С, К і М і т. Д., А тупиковими - майданчики A, D, I, J.

Мал. 1.16. Геометричне уявлення лабіринту

Будемо говорити, що майданчик Y досяжна з майданчика X, якщо існує шлях від X до Y через проміжні коридори і майданчики. Точніше: або X і Y - суміжні майданчики, або існує послідовність майданчиків Х1, Х2, ..., Хn таких, що X і Х1, Х1 і Х2 ..., і т.д., і, нарешті, Хn і Y є суміжними. Відзначимо, що якщо Y досяжна з X, то вона досяжна і за допомогою простого шляху, тобто такого шляху, в якому кожна майданчик (а тим більше і кожен коридор) проходиться лише один раз. Наприклад, шлях ABCD є простим, а шлях ABCFECD - немає.

Оскільки заздалегідь пристрій лабіринту невідомо, рішення задачі повинно бути представлено у вигляді загального методу пошуку для будь-якого лабіринту і при будь-якому розташуванні майданчиків Х і Y, де Х - початкова майданчик, а Y - кінцева, т. Е. Потрібно побудувати алгоритм пошуку шляху в лабіринті .

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

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

1.3.2. Завдання "Ханойські вежі"

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

А В С

Мал. 1.17. Ханойські вежі

Таблиця 1.5

 крок
А 4-1  4-2  4,3  4,3  4,1  4,1 ? ?  2,1 2,1 ? ?
В ? ?  2,1  2,1 ? ?  4,1  4,1  4,3  4,3  4-2  4-1
С ? ?  3,2  3-1 3-1  3,2 ? 1 ?

У табл. 1.5 наведено результат рішення задачі для випадку чотирьох дисків. Тут А - зайнятий в початковий момент (нульовий крок) стрижень, В - вільний, а З - допоміжний стержень. Цифрами позначений "номер" диска, причому більшого номеру відповідає більший діаметр. Відзначимо, що в середині процесу рішення як допоміжний виступає то стрижень А, то стрижень С.

Видно, що процес переміщення стопки дисків можна розбити на чотири фази:

1-я фаза - кроки 1-8, в результаті якої найнижчий диск виявляється на вільному стрижні;

2-я фаза - кроки 9-12; другий за величиною диск виявляється на вільному стрижні;

3-тя фаза - кроки 13 і 14; переносять передостанній диск на вільний стержень;

і 4-я фаза - крок 15 - заключний етап, в результаті якого диск з найменшим діаметром переноситься на вільний стрижень з уже впорядкованими по спадаючій дисками.

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

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

Як приклад вирішення завдання «Ханойські вежі» можна навести такий НЕ рекурсивний алгоритм. Якщо позначити номери стержнів не буквами а цифрами «0», «1» і «2», пронумерувати диски від нуля до N-1 (N - кількість дисків на зайнятому стрижні), то можна використовувати наступне співвідношення: на i-му ході переноситься диск номер k зі стрижня номер ((-1)N-k* T mod 3) на стрижень номер ((-1)N-k* (T + 1) mod 3). Слідуючи такій послідовності переміщення дисків завдання буде вирішена за 2n-1 Переміщень. При цьому для знаходження чисел t и k скористаємося теоремою: будь-яке натуральне число i єдиним чином представимо у вигляді i = (2t + 1) * 2k, Де t і k - цілі (тобто як твір непарного числа на деяку ступінь двійки). Якщо i - це черговий хід, то відповідно за вказаною формулою для нього визначаються значення цілих чисел t і k. В даному, одному рівнянні присутні два невідомих. Однак користуючись тим, що числа t і k обов'язково цілі і єдині для натурального числа i, неважко побудувати алгоритм для знаходження їх значень.

Відзначимо також, що в залежності від того парних або непарних буде кількість дисків на зайнятому стрижні, як допоміжний і вільного виступатимуть відповідно або стрижні «1», «2» або «2», «1», тобто стопка буде переміщена або на перший або на другий диск. Однак, так чи інакше стопка N дисків буде переміщена відповідно до встановлених правил на один з незайнятих стрижнів (або на перший (B) або на другий стрижень (C)).

висновок

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

2. Для організації розгалужень і циклів можуть бути використані різні оператори; вибір того чи іншого оператора в конкретному випадку залишається за програмістом.

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

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

5. СА може бути представлена ??з різним ступенем подробиці. Так, зумовлений процес, наприклад блок введення / виводу, може включати в себе кілька циклів; візуально фрагмент СА, що включає в себе цей блок, буде виглядати лінійним. Насправді лінійними можуть бути тільки дуже прості алгоритми або їх деякі фрагменти.

6. СА допускають еквівалентні перетворення, що може бути використано для підвищення ефективності алгоритмів. Наприклад, має сенс виносити, якщо це можливо, з тіла циклу всі оператори, які не пов'язані з параметром даного циклу.



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   Наступна

Загальна характеристика етапів вирішення задачі з використанням ЕОМ | Властивості алгоритмів і способи їх завдання | Використовуваних в СА | Принципи структурної алгоритмізації | Базовий набір структур | Лінійні і розгалужуються структури | Цикл із заданим умовою продовження роботи (цикл-ПОКИ) | Цикл із заданим умовою закінчення роботи (цикл-ДО) | Температура повітря | Вибірка елементів масивів |

загрузка...
© um.co.ua - учбові матеріали та реферати