Урок 3                                                     Інформатика 10 (АП)              

Базові алгоритмічні структури

Мета.

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

Розвиваюча. Розвивати логічне мислення, практичні навички складати алгоритм різними способами.

Виховна. Виховувати естетичні смаки, культуру оформлення.

План

1. Актуалізація опорних знань.
2. Вивчення нового матеріалу.
3. Розв’язування задач.
4. Запитання до уроку.
5. Домашня робота.

Хід уроку

І. Актуалізація опорних знань.

Опитування:

1. Щотаке алгоритм?

2. Назвіть і поясніть властивості алгоритмів.

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

4. Чим відрізняється словесне подання алгоритму від блок-схеми алгоритму?

ІІ. Вивчення нового матеріалу

Формальне виконання алгоритму

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

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

Аргументи, результати, проміжні величини

Для роботи багатьох алгоритмів треба задавати початкові значення. Ці значення передаються в алгоритм за допомогою аргументів.

Аргумент - це величина, значення якої необхідно задати для виконання алгоритму.

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

Результат - це величина, значення якої отримується внаслідок виконання алгоритму.

Під час складання багатьох алгоритмів виникає необхід­ність крім аргументів і результатів використовувати ще й до­даткові величини. Введення в алгоритм таких величин задає автор алгоритму.

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

Базові алгоритмічні структури

Базові структури алгоритму — це структури, за допомогою яких створюється алгоритм для розв’язання певної задачі. Існують три основні (базові) алгоритмічні структури: слідування, розгалуження та повторення.

Слідування

Команда подається у вигляді послідовності двох (або більше) виконуваних одна за одною простіших команд.

Приклад. Алгоритм Ранок.

1. Встати о 7-й год.

2. Виконати гімнастичні вправи.

3. Умитися.

4. Поснідати.

5. Піти в школу.

Розглянемо приклад - задачу на обчислення значення арифметичного виразу і складемо алгоритм її розв'язування.

Задача 1. Обчислити значення виразу (a-b)*(c-d), де а, b, с, d- дійсні числа (символом * в інформатиці позначається операція множення).

Розглянемо виконавця, який уміє отримувати значення змінних, ви­конувати арифметичні операції над дійсними числами, запам'ятовувати результати виконання цих операцій і повідомляти ці результати. Переда­вання даних виконавцеві називається введенням даних, а повідомлення виконавцем результатів виконання алгоритму - виведенням даних (результатів).

Запишемо алгоритм розв'язування цієї задачі для такого виконавця в словесній формі.

1. Увести значення змінних а, b, с, d (у результаті виконання цієї команди виконавець запам'ятовує введені дані як значення відпо­відних змінних).

2. Обчислити значення виразу а-b і результат присвоїти змінній х (запам'ятати як значення цієї змінної).

3. Обчислити значення виразу с-d і результат присвоїти змінній у.

4. Обчислити значення виразу х*у і результат присвоїти змінній z.

5.  Вивести значення змінної z.

У командах 2, 3 і 4 обчислюється значення виразу і результат обчис­лення присвоюється певній змінній (запам'ятовується як значення певної змінної). Такі команди називаються командами присвоювання. Для них зручно використовувати таку форму запису:

2.  х := а - b (читається: змінній х присвоїти значення виразу а - b)

3.  у := с - d

4.  z := х*у

Знак := називається знаком присвоювання і складається з двох симво­лів: двокрапки і дорівнює, які записуються без пропуску між ними.

Завдання. Написати блок-схему цього алгоритму.

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

Такі алгоритми (або фрагменти алгоритму) називаються лі­нійними.

Задача 2. Обчислити значення виразу (а - b) / (с - dі), де а, b, с, dі - дійсні числа (символом / в інформатиці позначається операція ді­лення).

Цей ви­раз містить дію ділення на вираз зі змінними, який може дорівнювати нулю. Тобто якщо значення різниці с - d дорівнює нулю, то значення ви­разу (а - b) / (с - d) обчислити не можна, а якщо не дорівнює, то можна.

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

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

Тоді для нового виконавця алгоритм розв'язування задачі 2 виглядати­ме так:

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

2. х := с - d.

3. Якщо х = 0? - істина, то вивести: «Вираз значення не має: ділення на нуль», після чого виконати команду 7, якщо хиба - то виконати команду 4.

4. у := а-b.

5. z := у/х.

6. Вивести значення змінної z.

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

Завдання. Написати блок-схему цього алгоритму.

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

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

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

Повне розгалуження — це галуження, в якому певні дії визначені й у разі виконання, і в разі невиконання умови.

Неповне галуження — це розгалуження, в якому дії визначені тільки у разі виконання (або у разі невиконання) умови.

Приклад. Алгоритм Вечір.

1. Прийти додому зі школи.

2. Пообідати.

3. Якщо в щоденнику є двійка , то сідати за уроки, інакше можна піти на дискотеку.

4. Лягти спати.

Алгоритм складається з чотирьох команд , третя є командою розгалуження

Повторення

Розрізняють два типи циклів — цикл з передумовою (цикл-ПОКИ)

і  цикл з післяумовою (цикл-ДО).

а) У структурі цикл-Поки для виконання команди спочатку треба ви­значити, істинне чи хибне твердження. Якщо твердження істинне, то виконується вказівка Дія і знову повертаються до визначення істинності твердження. Якщо ж твердження хибне, то виконання команди вважається закінченим.

б) У структурі цикл-ДО спочатку виконується команда, а потім визна­чається істинність твердження. Якщо твердження  хибне, то знову вико­нується команда і визначається істинність твердження. Якщо ж тверд­ження істинне, то виконання команди вважається закінченим.

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

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

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

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

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

4. Виконати перевірку умови Терези в рівновазі?.

5. Указати фальшиву монету.

Для цього виконавця алгоритм розв'язування цієї задачі такий:

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

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

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

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

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

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

7. Якщо Терези в рівновазі? -істина, то фальшивою є монета, що залишилася не покладеною на терези, якщо хиба - фальшивою є легша монета.

Завдання. Написати блок-схему цього алгоритму.

Цикли в алгоритмах

Розглянемо ще одну задачу.

Задача 4. Є порожні діжка і відро, Використовуючи відро, наповнити діжку водою з колодязя.

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

1.     Наповнити відро водою.

2.     Вилити воду з відра в діжку.

3.     Виконати перевірку умови Діжка повна?.

Складемо алгоритм розв'язування цієї задачі для розглянутого виконавця в сло­весній формі.:

1.  Наповнити відро водою.

2.  Вилити воду з відра в діжку.

3. Якщо Діжка повна? - істина, то за­кінчити виконання алгоритму, якщо хиба, то виконати команду 1.

Повторення алгоритм (цикл, структура повторення) — це алгоритм, у якому передбачено повторення деякої серії команд. За допомогою цієї структури описуються однотипні дії, що повторюються декілька разів. Такі алгоритми забезпечують виконання довгої послідовності дій, записаних порівняно короткою послідовністю команд. Саме використання циклів дозволяє у повній мірі реалізувати швидкодію комп’ютерів.

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

Фрагмент алгоритму, що складається з команд, які можуть виконуватися більше одного разу, називається циклом. Алго­ритми, які містять цикли, називаються алгоритмами із цик­лами.

В алгоритмі, що розглядався, цикл складається з трьох команд: двох команд (1 і 2), які утворюють тіло циклу, і команди перевірки умови.

ІІІ Розв’язування задач

Презентація “Лінійні алгоритми”

Задача 1. Записати у вигляді блок-схеми алгоритм переходу вулиці, де не встановлено світлофор. Визначити його тип.

Задача 2. Записати у вигляді блок-схеми алгоритм обчислення значення виразу:(a+b)-c*a . Виконайте його при різних значеннях а, b, с. Підберіть числа так, щоб кожного разу виконання алгоритму відбувалося по-різ­ному.

Задача 3*. Складіть блок-схему алгоритму знаходження х з рівняння ax+b=c. Виконайте його при а=2, b=-8, c=18.

.

IV. Запитання до уроку

1. Який алгоритм (фрагмент алгоритму) називається лінійним?

2. Що може бути результатом виконання команди перевірки умови? Наве­діть приклади.

З. Який блок позначає в блок-схемі команду перевірки умови? Наведіть приклади його використання.

 4. Назвіть характерні риси розгалуження.

5. Чи можуть команди тіла циклу не виконуватися жодного разу? Пояс­ніть свою відповідь. Наведіть приклади.

6. Чи може виконання циклу ніколи не закінчитися? Поясніть свою від­повідь. Наведіть приклади.

V. ДОМАШНЄ ЗАВДАННЯ.

1. Вивчити конспект.

2.    Задача 1. Записати у вигляді блок-схеми алгоритм переходу вулиці, де встановлено світлофор. Визначити його тип.

Задача 2о. Записати у вигляді блок-схеми алгоритм обчислення значення виразу:(a+b)-c/a. Виконайте його при різних значеннях а, b, с. Підберіть числа так, щоб кожного разу виконання алгоритму відбувалося по-різ­ному.

Задача 3*. Складіть блок-схему алгоритму розв’язування квадратного рівняння.

3. Підготуватись до практичної роботи № 2.