Налагодження програм 3 страница

4. º Що називається логічною константою?

5. ·Як утворюються складені висловлення? Наведіть приклади

6. · Що таке заперечення? Наведіть приклади.

7. º Для чого використовують таблиці істинності?

8. · Наведіть таблицю істинності заперечення

9. · Що таке кон’юнкція? Наведіть приклади.

10. · Наведіть таблицю істинності кон’юнкції.

11. · Що таке диз’юнкція? Наведіть приклади.

12. · Наведіть таблицю істинності диз’юнкції.

13. º Яка змінна називається логічною?

14. *Чим логічна змінна відрізняється від логічного висловлення?

15. · З чого складаються логічні вирази? Які значення вони можуть набувати?

16. º Назвіть пріоритет логічних операцій.

17. · Наведіть алгоритм складання та заповнення таблиці істинності логічного виразу.

18. ·Які логічні вирази називаються рівними? Що таке логічна формула?

Виконайте завдання

1. · Побудуйте заперечення висловлень та з’ясуйте їх істинність:

а) Число 3 є дільником числа 545.

б) Автомобіль не має права їхати на червоне світло

в) Існують паралелограми з прямими кутами

г) Рівняння 2х² – 3х + 1 = 0 має цілий корінь

є) Не існує натурального числа, що поділяється на 2

ж) Існує ціле число, яке ділиться на всі цілі числа

2. · Серед наступних складених висловлень знайдіть кон’юнкції та диз’юнкції та визначте їх істинність:

а) “Число 27 кратне 3 та кратне 9”

б) “17 < 42 < 18”

в) “Число 2 просте або парне”

г) “∆ АВС є гострокутним, прямокутним або тупокутним”

д) “Діагоналі будь-якого паралелограму перпендикулярні та точкою перетину поділяються навпіл”

є) “7² = 49 і (-7)² = 49”

ж) “Якщо трикутник рівнобедрений, то він рівносторонній”

з) “21 ≤ 21”

и) “21 ≤ 18”.

3. · Визначте істинність або хибність складених висловлень для наведених значень змінних:

1. «x > 0 і y > 0 або x < 0 і y < 0»

2. «x > 0 і не y < 0 або x < 0 та y > 0»

Значення змінних:

а) х = 5, у = 8

б) х = 5, у = -8

в) х = -5, у = 8

г) х = -5, у = -8.

4. (ДЗ) · Нехай А = "Іванов вивчає англійську мову", В = "Іванов має оцінку 8 з інформатики". Сформулюйте висловлення:

а) А /\`B б)`А \/ B в) A \/ `A /\ B г) `A \/ `B /\ А

5. º Вкажіть порядок виконання операції у логічних виразах:

а) A \/ `A /\ B

б) `A \/ `B /\ А

в) ( A \/`B ) /\ (`A \/ `B )

г) `A /\`B \/ C /\ D

6. · Побудуйте таблиці істинності логічних виразів:

а) A \/ A /\ B

б) A \/ `A /\ B

в) A /\ B \/`B

г) (ДЗ) ( A \/`B ) /\ (`A \/ `B )

д) (ДЗ) `A \/ `B

е) (ДЗ) A /\`B \/`A /\ B

7. Доведіть логічні формули:

a. A /\ A = A

b. =

c. A /\ (B \/ C) = (A /\ B) \/ (A /\ C)

d. (ДЗ) A \/ (B /\ C) = (A \/ B) /\ (A \/ C)

e. (ДЗ) A /\ (A \/ B) º A

2.8. Розгалуження в алгоритмах і програмах

Пригадайте!

1. Що таке алгоритм? Назвіть основні блоки блок-схеми алгоритму і поясніть їх призначення.

2. Які алгоритми (фрагменти алгоритмів) називаються лінійними? У чому полягає їх характерна особливість?

3. Які вирази називаються логічними? Які значення вони можуть набувати?

4. Назвіть логічні операції, наведіть означення кожної з них.

5. Назвіть логічні функції табличного процесора Excel 2007. Чому дорівнюють їхні значення залежно від значень аргументів.

Алгоритми з розгалуженням

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

Задача 1. Обчислити значення виразу (a – b) / (c – d), де a, b, c, d – дійсні числа.

Звернемо увагу на те, що значення цього виразу можна обчислити не для будь-якого набору значень змінних a, b, c, d. Адже цей вираз містить дію ділення на вираз зі змінними, значення якого може дорівнювати нулю. Тобто якщо значення різниці c – d дорівнює нулю, то значення виразу (a – b) / (c – d) обчислити не можна, а якщо не дорівнює – то можна.

Це означає, що система команд виконавця повинна містити команду порівняння двох чисел, наприклад таку: «s=t?», де s і t – або числа, або змінні чи вирази, які мають певні числові значення. Така команда є прикладом команди перевірки умови. Результатом виконання команди перевірки умови може бути або істина (умова виконується), або хиба (умова не виконується).

З іншого боку, ви вже знаєте, що порівняння «s=t?» можна розглядати як висловлення або як простий логічний вираз, який набуватиме значення true або false залежно від конкретних значень змінних s і t. І тоді команду перевірки умови можна інтерпретувати як команду обчислення значення логічного виразу.

Алгоритм розв’язування задачі 1 виглядатиме так:

1. Увести значення змінних a, b, c, d.

2. х := c – d.

3. Обчислити значення логічного виразу х = 0.

4. Якщо обчислене значення логічного виразуtrue, то повідомити «Вираз значення не має: ділення на нуль», після чого виконати команду 8, якщо false – то виконати команду 5.

5. у := a – b.

6. z := у/х.

7. Повідомити значення змінної z.

8. Закінчити виконання алгоритму.

Команди 1–3 наведеного алгоритму виконуватимуться про будь-якому наборі значень змінних a, b, c, d. Подальше виконання цього алгоритму залежатиме від значення логічного виразу, обчисленого в команді 3. Якщо це значення true, то виконуватимуться команди 5–8, а якщо false, то виконуватимуться команда виведення повідомлення «Вираз значення не має: ділення на нуль» і команда 8.

У блок-схемі алгоритму команди перевірки умови або обчислення значення логічного виразу позначаються блокомРішення . Оскільки результатом виконання цих команд може бути або trueабо false, то з цього блоку є два виходи. Вихід Такозначає, що результатом перевірки умови є true, а вихід Ні – що результатом перевірки умови є false.

Наведемо блок-схему наведеного вище алгоритму розв’язування задачі 1 (рис. 2.46).

Рис. 2.46. Блок-схема алгоритму обчислення значення виразу (a – b) / (c – d)

Розглянемо фрагмент алгоритму на рис. 2.46 від блоку Рішення до блоку Термінатор (не включаючи цей блок).

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

Такий фрагмент алгоритму називається розгалуженням.

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

Звертаємо вашу увагу:

• наведений алгоритм містить як розгалуження, так і лінійні фрагменти;
• у розгалуженнях можна використовувати як прості логічні вирази, так і складені.

В алгоритмах використовують розгалуження двох видів: повне розгалуження (рис. 2.47) і неповне розгалуження (рис. 2.48)

До верстальника: на рис 2.47 і 2.48 у ромбах вставити такі тексти: Перевірка умови (обчислення значення логічного виразу)

Виконання повного розгалуження відбувається так: виконавець виконує команду перевірки умови (команду обчислення значення логічного виразу); якщо результат виконання цієї команди true, то виконавець виконує послідовність команд 1, після чого переходить до виконання першої команди наступного фрагмента алгоритму; якщо ж результат виконання цієї команди false, то виконавець виконує послідовність команд 2, після чого також переходить до виконання першої команди наступного фрагмента алгоритму.

Виконання неповного розгалуження відрізняється від виконання повного розгалуження тим, що при результаті виконання команди перевірки умови false, виконавець одразу переходить до виконання першої команди наступного фрагмента алгоритму.

Усередині розгалуження можуть знаходитися як лінійні фрагменти алгоритму, так і інші розгалуження. Наведемо приклад алгоритму із розгалуженням у розгалуженні.

Задача 2. Дано два числа. Визначити, чи рівні вони. Якщо ні, то яке з них більше.

Блок-схема алгоритму розв’язування цієї задачі виглядатиме так (рис. 2.49):

Наведемо приклад ще однієї задачі, алгоритм розв’язування якої містить розгалуження.

Задача 3. Є дев’ять однакових на вигляд монет, одна з яких фальшива і легша від інших. Двома зважуваннями на терезах без гир визначити фальшиву монету.

Складемо алгоритм для виконавця з такою системою команд:

1. Узяти вказану купку монет.

2. Розділити вказану купку монет на три рівні купки.

3. Покласти на терези вказані купки монет.

4. Перевірити умову «Терези в рівновазі?».

5. Визначити при зважуванні, яка з купок монет легша.

6. Повідомити результат.

Для виконавця із такою системою команд алгоритм розв’язування задачі 3 такий:

1. Узяти дану купку з 9 монет.

2. Розділити взяту купку монет на три рівні купки.

3. Покласти на терези першу і другу купки монет.

4. Перевірити умову «Терези в рівновазі?».

5. Якщо істина, то взяти третю купку монет, якщо хиба, то взяти легшу купку.

6. Розділити взяту купку монет на три рівні купки.

7. Покласти на терези першу і другу купки монет.

8. Перевірити умову «Терези в рівновазі?».

9. Якщо істина, то повідомити: "Фальшивою є монета, що залишилася не покладеною на терези", якщо хиба — повідомити: "Фальшивою є легша монета".

Блок-схема цього алгоритму виглядатиме так (рис. 2.50):

Рис. 2.50. Блок-схема алгоритму розв’язування задачі 3

Верстальнику: замінити після Початок блок-ромб на блок-прямокутник

Звертаємо вашу увагу: в алгоритмі розв’язування задачі 2 виконання або невиконання тих чи інших команд алгоритму залежить від того, в яку купку попаде фальшива монета. Наприклад, якщо при першому зважуванні терези будуть не в рівновазі, то команда «Узяти третю купку монет» не буде виконана. Але якщо монети розподілити на купки по-іншому, то може статися так, що при першому зважуванні терези будуть у рівновазі, і тоді не буде виконана команда «Узяти легшу купку монет».

Розгалуження в Delphi

Команда повного розгалуження в Delphiмає такий загальний вигляд:

If <логічний вираз>