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

Лінійні і розгалужуються структури

  1. Абсолютні і відносні показники зміни структури
  2. Адаптивні і механістичні організаційні структури
  3. адаптивні структури
  4. АДАПТИВНІ СТРУКТУРИ
  5. Адаптивні структури управління
  6. Адхократіческая (органічні) СТРУКТУРИ
  7. Алгебра Жегалкина і лінійні функції

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

Припис «Список даних» містить відомості про імена і типи даних, які обробляються в цьому алгоритмі. Припис «Введення (вихідні дані)» визначає, які вихідні дані і в якому порядку повинні бути введені в ЕОМ. Припис «Висновок (вихідні дані)» дозволяє проконтролювати правильність введення інформації. Приписи 5 і 6 дозволяють отримати необхідні результати і видати їх користувачеві. Розглянутий алгоритм відноситься до лінійних алгоритмів.

Мал. 9. Типовий алгоритм обчислювального процесу

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

Лінійної, наприклад, є послідовність обчислень з якої-небудь формулою за допомогою кишенькового калькулятора. Більш детально слід розглянути запис математичних формул у вигляді конструкції Х: = А; яка читається так: «Перемінної X привласнити значення, рівне А». У цій формулі X - змінна; А може бути будь-яким, як завгодно складним математичним виразом. У процесі виконання завдання на ЕОМ вираз А обчислюється, і його значення присвоюється осередки пам'яті, відведеної для зберігання змінної X. При цьому змінна X втрачає своє значення і набуває нового. Таким чином, символ «: =» вживається при зображенні алгоритмів в значенні «привласнити». Як наслідок цього, безглузде з точки зору алгебри вираз Х: = Х + 5; є широко поширеним в програмуванні і означає, що до поточного значення змінної X додається число 5, після чого X втрачає своє старе значення і набуває нового, яке на 5 більше попереднього.

Лінійні фрагменти використовуються на перших етапах деталізації завдання. Однак тільки в рідкісних випадках все приписи такого алгоритму є елементарними. Так, наприклад, припис 5 на рис. 9 не є елементарним і вимагає подальшої деталізації. Тому призначення блоку 5 передбачає зверху вільне місце для запису координат блоку, в якому буде розкриватися сенс деталізіруемая ділянки.

Часто для подальшої деталізації алгоритму використовуються розгалужені структури (рис. 10).

 
 

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

 Якщо (умова) Тооператори гілки 1; Іначеоператори гілки 2; Кінець-Якщо;  Якщо (умова) Тооператори гілки; Кінець-Якщо;  Якщо (умова) ТоІначеоператори гілки; Кінець-Якщо;

Мал. 10.Структура, що гілкується: а - Стандартна схема; б, в - Окремі випадки розгалуження

Кожна гілка може бути будь-якого ступеня складності, а може взагалі не містити приписів (як це показано на рис. 10, б, в), Тобто бути «вироджених». Вибір тієї чи іншої гілки здійснюється в залежності від результату перевірки умови. У кожному конкретному випадку алгоритм реалізується тільки по одній гілці, а виконання інших виключається. У схемах, наведених на рис. 10, позитивний результат перевірки умови позначений знаком «+» (так, true, істина, «1»), а негативний - знаком «-» (ні, false, брехня, «0»).

При складанні алгоритму у вигляді Псевдокод лінії зв'язку повинні бути слова «Йти» або «Перейти» із зазначенням номера приписи (оператора), яке повинно виконуватися на наступному кроці алгоритму. Горизонтальна лінія, що об'єднує галузі «+» і «-», в Псевдокод має аналог «Кінець-Якщо". Після фрази «Кінець-Якщо" можна вказати номер псевдокоду, в якому записано, що перевіряється умова. Наприклад, після пункту 7 в алгоритмі, представленому на рис. 7, вказується: «Кінець-Якщо 5».

Використання даної конструкції під час запису алгоритму в Псевдокод дозволяє легко визначити місце закінчення розгалуження (продовження основного алгоритму).

Мал. 11.Вибір варіанту: а - Структура вибору варіанта; б, в - умовне позначення

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

У такій структурі (див. Рис. 11) спочатку обчислюється значення виразу, що стоїть в операторі присвоювання. Залежно від значення змінної i потім буде обраний або 1-й, або 2-й, або 3-й, або 4-й оператор. Число обираних операторів в такій структурі не обмежена.

Загальні питання організації розгалужень в алгоритмах

Розглянемо питання організації вибору напрямку в СА докладніше.

Ситуації, в яких необхідно зробити вибір з кількох альтернатив, описуються складовими логічними операторами, отриманими композицією простих умов (простих предикатів). Складність вибору визначається як безліччю умов, так і безліччю альтернатив. Кожному альтернативного напрямку в СА вибору присвоюється свій десятковий номер, починаючи з 1.

На СА вибір реалізується двійковим деревом, повним або неповним, в кожному вузлі (умовному блоці) якого найпростіший вибір кодується логічним 0, якщо умова не виконується (false), І логічної 1, якщо умова виконується (true).

Якщо скласти позиційний код на виході з блоку вибору за кожним напрямом відповідно до кодів на виходах умовних блоків СА при послідовному проходженні через них зверху вниз, то отримаємо двійковий код десяткового номера альтернативи, зменшеного на 1. Проранжируем зверху вниз умовні блоки (ранг СА вибору - це глибина вузла дерева вибору, збільшена на 1); тоді кількість альтернатив m, Що надаються повним двійковим деревом, визначається його рангом r, m= 2r.

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

Розглянемо побудову СА вибору для повного дерева вибору.

Приклад 1.3. Нехай необхідно організувати вибір з чотирьох альтернатив, використовуючи повне дерево і таблицю альтернатив.

В цьому випадку достатньо двох умов В1 і B2, де В1 і В2 - булеві змінні, причому на другому ранзі умови однакові; кожній парі зі значень 0 (false) І 1 (true) Цих умов можна зіставити свою альтернативу Ni - див. Табл. 1.1, колонка А. Цій таблиці відповідає фрагмент СА, показаний на рис.1.5; тут поруч з номерами альтернатив вказані їх коди (виконавчі уявлення).

 В 1  В 2 А
 N1
 N2
 N3
 N4

Таблиця 1.1

N1 (00) N2 (01) N3 (10) N4 (11)

Мал. 1.5. СА вибору з чотирьох альтернатив

Розглянемо побудову СА вибору при неповному дереві вибору.

Приклад 1.4. Нехай задана логічна функція вибору виду С = В1AВ2, де В1 і В2 - логічні умови (В1, В2 - булеві змінні) і A -операція логічного додавання по mod2. Заповнимо таблицю істинності для функції С (табл. 1.2); тут в колонці для З проставлені її логічні значення F (false) І Т (true), Що визначають вибір з двох шляхів (альтернатив), за якими розгалужується СА для заданої функції. Таким чином, табл. 1.2 представляє собою таблицю альтернатив. На рис. 1.6 наведено фрагмент схеми алгоритму, побудований відповідно до табл. 1.2, причому всі шляхи, що мають однакове логічне значення, об'єднані.

 В 1  В 2 С
F
Т
Т
F

 Таблиця 1.2

r= 1

r= 2

F (00 V 11) T (01 V 10)

Мал. 1.6. СА вибору з об'єднанням шляхів

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

 Рис: 1.7. Окремий випадок вибору:а - Вихідний фрагмент СБб - Спрощення фрагмента
 Якщо в побудованій схемі є зображений на рис. 1.7, а фрагмент, то булева змінна Bi в ньому склеюється, т. Е. BiVuBi = 1; це означає, що умовний блок на ділянці a-b не потрібен, і його можна замінити відрізком прямої (рис 1.7,6).

Приклад 1.5. Нехай вибір з трьох альтернатив N1, N2, N3 визначається трьома простими умовами (булеві змінними) В1, В2, ВЗ відповідно до табл. 1.3. Потрібно синтезувати СА для блоку вибору.

Перебудуємо табл. 1.3, ввівши для кожної альтернативи свою колонку, в якій для вибраної набору uВ1uВ2uВЗ відзначається одиницею той факт, що альтернатива реалізується, а прочерком - що не реалізується (табл. 1.4).

 В 1  В 2  У 3 С
 N1
 N2
 N1
 N3
 N3
 N3
 N3
 N3

Таблиця 1.3 Таблиця 1.4

 В 1  В 2  ВЗ  N1  N2  N3
- -
- -
- -
- -
- -
- -
- -
- -

На рис. 1.8, а приведена початкова схема алгоритму вибору, а на рис. 1.8, б показана мінімізована СА вибору; поруч з кожним альтернативним виходом в дужках записані відповідні їм коди (значення довічних наборів uВ1uВ2uВЗ; X - байдуже значення).

В даному прикладі спрощення фрагментів СА вибору можуть бути отримані чисто схемним шляхом. Дійсно, ділянку а-b може бути замінений прямий (див. рис. 1.7), а ділянки c-d, з-е, з-в можна перетворити з урахуванням законів дистрибутивности і коммутативности як для змінних, так і для відповідних їм умовних блоків. маємо

ділянку c-d - UВ2 & uB3 V B2 & uB3 = uВЗ & (uB2 V B2) = uB3;

ділянку з-е - UВ2 & В3 = ВЗ & uВ2;

ділянку з-в - В2 & ВЗ = ВЗ & В2.

N1 (000 V 010) N2 (001) N3 (011 V 100 V 101 V 110 V 111)

 Розглянемо загальні питання організації розгалужень в СА. Під терміном "організація розгалужень"Розуміється така побудова схеми (блоку) вибору альтернатив, яке адекватно відображає вихідне завдання, і при цьому має мінімальну булево вираз в сенсі ціни по Квайну. Вихідна інформація про складне виборі в деякій задачі повинна бути представлена ??таблицею альтернатив (ТА).

У загальному випадку побудови СА вибору задані m альтернатив N1 ... Nm і n булевих змінних В1 ... Вn. Кожному набору uB1 ... uВn відповідає своя альтернатива, що може бути представлено у вигляді ТА. Перебудуємо ТА таким чином, щоб кожній альтернативі відповідала своя колонка, в якій для вибраної набору uB1 ... uВn відзначається "1" - альтернатива реалізується, а прочерком - не реалізується. Тоді Ni (i=) Можна вважати вихідними змінними схеми вибору, а саму таблицю можна розглядати як таблицю істинності для системи m функцій від n булевих змінних; мінімізувавши таку систему [5], можна побудувати СА вибору.

В ТА в стовпці альтернатив можуть бути однакові альтернативи (одна і та ж альтернатива реалізується при декількох наборах uВ1 ... uBn) або прочерки (в повному обсязі альтернативи використовуються). У першому випадку можна об'єднати кінцеві вузли дерева. Другий випадок відповідає неповного дереву вибору (m<2r); ТА в цьому випадку може бути Довизначивши виходячи з додаткових міркувань. В обох випадках треба мінімізувати логічні вирази і реалізують їх схеми алгоритмів.

Мал. 1.9. Фрагменти СА для умовних операторів типу:

а, б - if; c - case..of

На рис. 1.9 наведені фрагменти СА для умовних операторів виду

а) if <Умова> then S (на схемі умова скорочено позначено I),

б)if<Умова>thenS1elseS2 (на схемі - I);

в)caseNof1: S1; 2: S2; .. K: Skend(На схемі - С).

Тут Si - довільний оператор; він може бути порожнім або складовим, т. е. включати в себе послідовність операторів, в тому числі умовний оператор.

Для простих випадків вибору досить використовувати умовні оператори if(Рис. 1.9,а и б). У більш складних випадках Pascal надає потужний засіб - оператор-перемикач case .. of (Рис. 1.9,в); аналогічне засіб (switch) Є і в мові С.

На закінчення запишемо фрагмент програми для мінімізованої СА вибору (приклад 1.5) Перехід від схеми вибору (рис. 1.8,б) До умовного оператору case N ofнескладний; кожній альтернативі ставиться у відповідність свій десятковий номер (зліва направо в СА вибору), потім за кодами альтернатив записуються логічні формули, які вписуються в якості умов в умовні оператори, і формуються оператори присвоювання параметру N відповідного десяткового номера; далі йде (можливо, після операторів загального вигляду) оператор caseNof.

Таким чином, фрагмент програми для прикладу 1.5 має вигляд

Begin

if(NOT B1) AND (NOT B3) then N: = 1 else

if (NOT B1) AND (NOT B2) AND B3 then N: = 2 else N: = 3;

case N of

1: S1;

2: S2;

3: S3;

End;

End.

Важливо відзначити, що до моменту обчислення N повинні бути визначені значення В1, В2, ВЗ.

В якості ще одного прикладу використання розгалужень розглянемо складання алгоритму для обчислення функції f в залежності від конкретних значень х, а, b:

Перше наближення алгоритму матиме вигляд, показаний на рис. 12.

Мал. 12.Перший етап складання алгоритму

Аналіз цього алгоритму показує, що все його блоки, крім блоку 5, є елементарними. Можливий варіант подальшої деталізації блоку 5 представлений на рис. 13. Всі блоки другого етапу деталізації є елементарними, тому складання алгоритму практично закінчено.

Мал. 13.Другий етап складання алгоритму

На заключному етапі здійснюється складання алгоритму, тобто вміст рис. 13 поміщається на рис. 12 замість блоку 5. Даний етап тут не показаний, при бажанні можна виконати його самостійно.



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

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

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