Конспект урока№8 Ковалевой Евгении

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

Тема уроку: "Базові структури алгоритмів"

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

Тип уроку: лекція.

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

Що називається алгоритмом?

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

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

(Скінченність, масовість, дискретність, елементарність, результативність )

Хто може виступати виконавцем алгоритму?

(Людина, комп'ютер, собака, пральна машина та ін.)


2. Пояснення нового матеріалу:

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

Всього існують чотири базових структури алгоритмів:

лінійні;

розгалужені;

циклічні;

змішані.

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

Які ж команди можна назвати простими?

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

Загальний вигляд лінійного алгоритму, поданий мовою блок-схем, наступний:

Bbb.jpg

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

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

проснутися;

зробити ранковий туалет;

одягнутися;

поснідати;

зібрати речі;

одягнути верхній одяг;

вийти до школи.

Та, навіть, в такому простому алгоритмі ви зразу ж знайдете недоліки.

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

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

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

Мовою блок-схем розгалужений алгоритм подається наступним чином:

Ccc.jpg

Тепер розберемось, що ж таке умова з точки зору виконавця.

Умовою називається таке речення, на яке можна дати відповідь "так" чи "ні".

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

Виходячи з цього, речення "Якого кольору твій піджак?" не можна вважати умовою, а речення "Твоє волосся русяве?" - можна.

Завдання: Придумайте речення, яке можна вважати умовою.

Дуже часто в житті ми змушені враховувати велику кількість найрізноманітніших умов.

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

Такі умови в інформатиці називаються складеними. Вони містять кілька простих умов і об'єднуються між собою словами "або" або "та".

Перше з цих слів ("або") використовується у тих випадках, коли необхідно виконання хоча б однієї з умов, тобто хоча б одна з умов являється істиною.

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

Друге слово ("та"), навпаки, використовується лише в тих випадках, коли тільки одночасне виконання всіх умов призводить до результату.

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

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

В цих випадках нас виручає циклічний алгоритм.

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

Наприклад, в першому класі вчителька дає завдання дітям: "Діти, напишіть, будь ласка, в зошитах десять цифр "1", а потім рядочок цифр "2".

Чим відрізняються ці два завдання?

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

Чому другий випадок не такий точний?

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

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

Завдання: Придумайте ситуації, коли можна визначити кількість повторень, а коли не можна.

Крім того, в циклах з умовою теж можна виділити два різних випадки:

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

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

Мовою блок-схем обидва типи циклів виглядають наступним чином:

Ddd.jpg

Найчастіше ж у житті ми використовуємо змішані алгоритми.

Так, дійсно, зранку ми контролюємо свій стан здоров'я, погоду, розклад уроків (коли збираємо речі), свій одяг і таке інше.

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

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

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

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

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

3. Підсумки уроку.

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

4. Домашнє завдання: вивчити означення (базові структури алгоритмів, що таке складені умови, типи циклів);

придумати будь-який алгоритм на побутову тему (кулінарний, прибирання кімнати, виконання уроків і т.д.), виділивши в ньому базову структуру.