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

Матеріал з Фізмат Вікіпедії
Перейти до: навігація, пошук

Конспект підготувала студентка групи МІ-53 Гуменна Марія

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

Девіз: «Учень ніколи не підніметься до знань учителя, якщо постійно відчуватиме його перевагу. Лише в процесі спільного пошуку формуються справжні знання».

Обладнання: картки, слайди на ПК.

Тип уроку: урок пояснення нового матеріалу

ХІД УРОКУ

І. Перевірка домашнього завдання

Метод «Мікрофон»

(Учні по черзі пропонують свої ситуаційні задачі і складені до них алгоритми.)

ІІ. Мотивація навчальної діяльності учнів

Учитель пропонує учням сформулювати алгоритм «Ранок школяра». Спільними зусиллями, учні формулюють орієнтований алгоритм.

1. Прокинутись.

2. Прибрати постіль.

3. Умитися

4. Поснідати

5. Одягнутися по погоді.

6. Піти до школи.

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

III. Оголошення теми та очікуваних навчальних результатів

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


Після цього уроку ви зможете:

• називати основні базові структури;

• пояснювати призначення різних базових структур;

• наводити приклади різних типів алгоритмів;

IV. Подання нового матеріалу

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

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

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

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

Слідування.jpg

2. Розвилка, яка також називається, «як-що-то-інакше», означає вибір одного з двох варіантів залежно від значення певного логічного виразу

а) повне розгалуження

Повне розгалуження.jpg

б) неповне розгалуження

Неповне розгалуження.jpg

3. Цикли. Розрізняють два типи циклів — цикл-ПОКИ і цикл-ДО.

а) У структурі цикл-ПОКИ для виконання вказівки спочатку треба визначити, істинне чи хибне твердження Р. Якщо Р істинне, ТО виконується вказівка S, і знову повертаються до визначення істинності твердження Р. Якщо ж твердження Р хибне, то виконання вказівки вважається закінченим. Цикл означає повторне виконання тієї самої дії або блока дій, що мають назву тіла циклу, доти, доки певний логічний вираз залишається істинним.

Поки.jpg

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

До.jpg

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

Лінійний алгоритм — алгоритм, у якому використовується тільки структура «слідування».

Алгоритм із розгалуженням — алгоритм, в основі якого лежить структура «розгалуження». Циклічний алгоритм — алгоритм, в основі якого лежить структура «повторення».

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

Розглянемо виконання методу покрокової деталізації для побудови алгоритму обчислення площі повної поверхні піраміди, в основі якої лежить квадрат зі стороною а, а бічні ребра мають довжини b, c, d, k.

Площа повної поверхні піраміди складається із площі повної бічної поверхні і площі основи.

Загальний вигляд алгоритму буде таким:

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

2. Знайти площу грані (a, b, c).

3. Знайти площу грані (а, с, к).

4. Знайти площу грані (а, d, к).

5. Знайти площу грані (а, к, b).

Площа піраміди = площа грані (а, b, с) + площа грані (а, с, d) + площа грані (а, d, к) + площу грані (а, к, b) +а . Вивести площу піраміди.

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

Наш основний алгоритм набере вигляду:

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

2. Площа (a, b, c, S)

3. Площа (а, с,d S ).

4. Площа (a, d, k, S ).

5. Площа (а, к, b, S )

6. Площа

7. Вивести площу

Побудуємо допоміжний алгоритм обчислення площі трикутника за формулою Герона.


V. Інтерактивна вправа

Метод «Коло ідей»

У малих групах (спікер, секретар, посередник, доповідач) відповісти на такі запитання:

1) визначити ті алгоритми, в основу яких покладено структуру слідування;

2) визначити ті алгоритми, в основу яких покладено структуру з повним розгалуженням;

3) визначити ті алгоритми, в основу яких покладено структуру повторення;

4) визначити ті алгоритми, в основу яких покладено структуру з неповним розгалуженням;

5) визначити ті алгоритми, які подані у словесній формі.

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

Завдання1.jpg Завдання2.jpg

Завдання3.jpg Завдання4.jpg


Завдання 5

1. Закип'ятити воду.

2. У чашку покласти 1 чайну ложку кави.

3. Залити окропом.

4. Дати настоятися.


VI. Підбиття підсумків інтерактивної вправи

Учитель повідомляє, що для побудови різноманітних алгоритмів використовуються комбінації різних базових структур. Це можливо через те, що кожна базова структура має один вхід і один вихід. Отже, з'єднуючи в один ланцюжок різні базові структури, ми виконуємо конструювання алгоритмів. Такі алгоритми будуть змішаними. Так, дійсно, зранку ми контролюємо свій стан здоров'я, погоду, розклад уроків (коли збираємо речі), свій одяг тощо. Коли ми снідаємо, повторюємо одну й ту саму послідовність дій (зачерпнути ложкою їжу, піднести до рота, взяти в рот, прожувати, проковтнути, зачерпнути ложкою їжу, піднести до рота і т. д.), коли миємо посуд, то теж повторюємо одну й ту саму послідовність дій. Навіть коли йдемо, ми повторюємо визначені дії. Учні сідають у коло. Для підбиття підсумків учитель пропонує їм взяти участь у бліцдиспуті. Для його проведення учням треба роз¬дати по одній картці з хибним або істинними твердженнями. Вони почергово звертаються до свого сусіда праворуч (наприклад: «Прошу бути моїм опонентом Миколу») та оголошують своє твердження з картки. «Опонент» повинен висловитися з приводу істинності твердження: «Так, дійсно….» або «Ні, це неправильно».

Свою думку «опонент» висловлює за методом ПРЕС: «Явважаю, що...»; «Тому що...»; «Наприклад, ...»; «Отже (тому), я вважаю ...».


Зміст карток

Картка 1. Прошу бути моїм опонентом__________ .

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

Картка 2. Прошу бути моїм опонентом__________.

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

Картка 3. Прошу бути моїм опонентом__________.

Я стверджую, що до базових структур алгоритмів відносять такі конструкції: дискретний алгоритм, масовий алгоритм, формальний алгоритм.

Картка 4. Прошу бути моїм опонентом___________.

Я стверджую, що особливістю базових структур є те, що кожна з них має один вхід і один вихід.

Картка 5. Прошу бути моїм опонентом____________ .

Я стверджую, що алгоритм можна зобразити тільки графічно у вигляді деякої схеми.

Картка 6. Прошу бути моїм опонентом______.

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

Картка 7. Прошу бути моїм опонентом______.

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

Картка 8. Прошу бути моїм опонентом_______.

Я стверджую, що коли виконавець виконує алгоритм, він спочатку творчо опрацьовує команду, а потім її виконує.

Картка 9. Прошу бути моїм опонентом_______.

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

Картка 10. Прошу бути моїм опонентом________.

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

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

Учитель пропонує учням відповісти на запитання:

• Чи досягли ми мети, яку поставили перед собою на початку уроку? Завдяки чому? Що допомогло у засвоєнні матеріалу уроку?

• Що було легко, а що — складно?

• Що найбільше запам'яталося на сьогоднішньому уроці?

• Які ви знаєте базові структури алгоритмів?

• Які ви засвоїли форми подання алгоритмів?

• Від чого залежить форма подання алгоритмів?

• Що таке конструювання алгоритмів?

• Хто визначає, якою саме базовою структурою треба скористатися в тому чи іншому алгоритмі?

VIII. Домашнє завдання

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