ПЛАН ЗАНЯТТЯ No2
Дата: група: Дисципліна: Алгоритми та структури даних. Тема: Правила створювання алгоритмів. Мета:
Методична: закріпити методику проведення лекційного заняття. Дидактична: розглянути загальні правила алгоритмічної мови, команди галуження, команди повторення. Виховна: зміцнювати бажання вивчення дисципліни.
Вид заняття: лекційне заняття. Форми та методи проведення заняття: інформаційно- рецептивні, фронтальне опитування, викладання нового матеріалу.
Міжпредметні зв’язки:
- Дисципліни, що забезпечують: математичний аналіз, лінійна алгебра та аналітична геометрія.
- Дисципліни, що забезпечуються: алгоритмічні мови та програмування, об'єктно-орієнтоване програмування.
Науково-методичне забезпечення:
- Алтухов Е.В., Рыбалко Л.А., Савченко В.С. Основы информатики и
вычислительной техники: Учеб. пособие для учащ. средн. спец. уч. заведений. – М.: Высш. шк., 1992. – 303 с. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное
пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.
ХІД ЗАНЯТТЯ.
- Організаційний момент: перевірка відсутніх, зовнішнього вигляду, готовності
аудиторії. 2. Повідомлення теми, формування мети та основних завдань. 3. План викладання нового матеріалу: надано в конспекті лекції. 4. Актуалізація опорних знань:
- Дати визначення похідної;
- Дати визначення первісної, невизначеного інтегралу;
- Дати визначення диференціалу;
- Визначити зв’язок неперервності та диференційованості;
- Необхідні умови інтегрованості функції;
- Таблиця похідних, таблиця інтегралів основних елементарних функцій. 5. Вивчення нового матеріалу: Тема лекції: Правила створювання алгоритмів.
- Мотивація вивчення матеріалу: диференціальні рівняння – це основний сучасний засіб розв’язання прикладних задач, який дає змогу описати математичну модель на зрозумілій мові. Тому, сучасному студенту необхідно вміти не тільки розв’язувати основні типи звичайних диференціальних рівнянь, але моделювати за допомогою диференціальних рівнянь текстові задачі.
- План вивчення нового матеріалу: надається в конспекті лекції. 6. Виклад нового матеріалу: конспект лекції надається. 7. Закріплення нового матеріалу: обговорення окремих питань алгоритмів. 8. Підведення підсумків заняття. 9. Домашнє завдання:
Викладач М.П.Леверя
Лекція No2 Тема: Алгоритмічна мова.
План 1. Загальні правила алгоритмічної мови. 2. Команди галуження. 3. Команда повторення.
- Загальні правила алгоритмічної мови.
Алгоритмічна мова — це сукупність визначних знаків, слів і правил, що встановлюють, як за допомогою цих знаків описувати алгоритми.
Загальні правила алгоритмічної мови. Запис алгоритму на алгоритмічній мові складається із заголовка і власне алгоритму — послідовності команд. Заголовок включає назву алгоритму, списки вихідних даних (аргументів) і результатів. Алгоритм, записаний на алгоритмічній мові, має наступну форму:
алг назва алгоритму
арг список аргументів рез список результатів поч
послідовність команд алгоритму кін Якщо умова завдання повністю визначена і вихідні дані відсутні, то службове слово арг не пишеться. Допускається також відсутність списку результатів. В цьому випадку результатом виконання алгоритму буде досягнення поставленої мети. Як, наприклад, в алгоритмах приготування настою шипшини або переходу вулиці.
Команди алгоритму записуються послідовно. Якщо команда не поміщається на одному рядку, то її можна продовжувати на наступних рядках. Якщо декілька команд записуються на одному рядку, то між ними ставиться крапка з комою. Всі команди повинні входити в систему команд виконавця.
П р и к л а д 1.1. А л г о р и т м п р и г о т у в а н н я н а с т о ю ш и п ш и н и .
алг приготування настою шипшини поч
Столову ложку сушених плодів шипшини подрібнити в ступці Залити стаканом киплячої води Кип'ятити 10 хвилин на слабкому вогні Охолодити; Процідити кін
Команди алгоритмічної мови діляться на прості і складені. Проста команда не вимагає попередньої перевірки яких-небудь умов. Простою командою є команда привласнення, команди введення, виводу і ін. Приведений вище алгоритм складається з п'яти простих команд.
Міра деталізації команд при записі алгоритму залежить від виконавця. Так, алгоритм у = (5х - 2)(х + 4) можна записати двома способами:
алг формула, спосіб 1 алг формула, спосіб 2
арг х арг х рез у рез у поч поч
R1: = 5х у = (5х - 2)(х + 4) R2: = R1— 2 кін R3: = x + 4 у = R2∙R3 кін
У складених командах алгоритмічної мови перевіряється яка-небудь умова. До складених відносяться команди галуження і повторення.
- Команди галуження.
Команди галуження таким чином:
якщо умова якщо умова то серія 1 або то серія
інакше серія 2 все все
Терміном «серія» тут позначена послідовність будь-яких команд алгоритмічної мови (у тому числі що полягає і з однієї команди).
Перша форма запису команди називається повною, друга — скороченою. Команда галуження використовується в ситуації, коли потрібно вибрати один з двох варіантів дій залежно від деякій умови. При дотриманні цієї умови необхідно виконувати дії, визначені серією 1 (тобто всі команди серії 1). При недотриманні умови виконується серія 2. Це для повної форми команди галуження.
Якщо спожита скорочена форма, то в разі дотримання умови виконавець зобов'язаний виконати серію команд, записану після службового слова то. При недотриманні ж умови виконавцеві потрібно приступити до виконання наступної команди.
На мал. 1.1 змальовані схеми, відповідні повній і скороченій формам команди галуження.
Якщо в алгоритмі використовується декілька команд галуження, то для наочності алгоритму слідує відповідні пари службових слів якщо і все з'єднати вертикальною лінією:
так
ні
ні
Мал. 1.1
а) якщо ... ... все ...
якщо ... все
б) якщо...
то якщо...
то інакше .... все все
Проілюструємо на прикладах вживання команди галуження. П р и к л а д 1.2. Скласти алгоритм обчислення значення у за формулою
умова
серія 1 серія 2
так
умова
серія
⎧
x
+
2
y
=
,100
якщо
х = 7 алг формула
арг х рез у поч
якщо х ≠ 7
то
7
│ ⎨
x
-
7
,
якщо
х ≠ 7 │ ⎩
y
:
=
x
+
2
x
- інакше у: = 100 все кін П р и к л а д 1.3. Скласти алгоритм шукання значення більшого з трьох величин а, b, c.
алг більше з трьох
арг а, b, c рез у поч
якщо a>b то у:=а інакше у:=b все якщо c>y то у:=с все кін П р и к л а д 1.3. Записати алгоритм виділення прямої мови у реченні.
алг пряма мова поч
якщо слова автора передують прямій мові то після слів автора ставиться двокрапка інакше якщо пряма мова передує словам автора
то перед словами автора ставиться тире
інакше перед прямою мовою ставиться
двокрапка, а після неї — тире все все кін П р и к л а д 1.4. Записати у вигляді алгоритму інструкцію користування автоматичною камерою сховища. алг автоматична камера схову поч
якщо багаж ставиться в камеру
то Відкрийте дверці вільної камери
Поставте багаж в камеру На внутрішній стороні дверець наберіть задуманий шифр Запам'ятаєте шифр Опустите монету 15 коп.; Закрийте дверці Запам'ятаєте номер камери інакше якщо багаж береться з камери схову
то Знайдіть камеру з вашим багажем
Наберіть необхідний шифр. Опустите 15 коп. Відкрийте дверці; Візьміть багаж все все кін
Команда повторення. При вирішенні деяких задач потрібно багато разів повторювати одні і ті ж дії. Алгоритми, в яких деяка група команд виконується більше одного разу, мають циклічну структуру. Для організації циклів в алгоритмічної мові існує декілька команд повторення. Проста команда повторення має вигляд
повторити число повторень разів
нц
серія кц Виконання цієї команди полягає в тому, що серія команд, що знаходиться між службовими словами нц (початок циклу) і кц (кінець циклу), виконується вказане в команді число разів підряд.
Кількість повторень може бути цілим числом, змінною або вираженням (формулой) алгебри з цілим значенням.
П р и к л а д 1.5. Скласти алгоритм наповнення 10-літрового відра водою, користуючись літровим кухлєм.
алг наповнення відра поч
повторити 10 разів
нц
Наповнити кухоль водою, Вилити воду з кухля у відро кц кін
П р и к л а д 1.6. Є три урни (біла, сіра і смугаста). У смугастій урні знаходяться білі і чорні кульки. Треба всі чорні кульки перекласти в сіру урну,
а білі - в білу. Сортування виробляється так: по черзі виймаються кульки із смугастої урни і залежно від кольору кладуться або в сіру або в білу урну. Скласти алгоритм, що в смугастій урні лежить 50 куль.
алг сортування куль поч
повторити 50 разів
нц
Дістати кулю із смугастої урни, якщо куля біла
то Покласти його в білу урну.
інакше Покласти кулю в чорну урну, все кц кін Інколи зустрічаються завдання, в яких число повторений заздалегідь невідоме. Допустимо, в прикладі 1.5 відро вже частково наповнене водою і потрібно лише долити його по самі вінця. У прикладі 1.6 число куль в смугастій урні могло виявитися заздалегідь невідомим. У таких випадках використовується команда повторення наступного вигляду:
поки умова
нц
серія кц При виконанні цієї команди спочатку перевіряється умова. Якщо воно дотримується, то виконується вказана серія команд циклу. Потім знову перевіряється умова, виконується серія і т. д., поки задана умова дотримується. Як тільки умова порушиться, то повторення припиняються — виконання команди закінчене. Умова завжди перевіряється перед виконанням серії, тому якщо воно не дотримується із самого початку, то серія циклу не виконується жодного разу. Виконання команди повторення «доки» можна пояснити наступною схемою (мал. 1.2).
ні умова
так
серія
Мал. 1.2
П р и к л а д 1.7. Записати алгоритм наповнення відра водою (див. приклад 2.18), використовуючи команду повторення «доки».
алг наповнення відра
поч
поки відро не повне
нц
Наповнити кухоль водою
Вилити воду з кухля у відро кц кін
П р и к л а д 1.8. Використовуючи команду повторення «доки», записати алгоритм сортування куль (див. приклад 1.6).
алг сортування куль
поч
поки смугаста урна не порожня
нц
Дістати кулю із смугастої урни якщо куля біла
то Покласти його в білу урну інакше Покласти кулю в чорну урну все кц кін
П р и к л а д 1.9. Скласти алгоритм переходу улиці, на перехресті зі світлофором.
алг перехід вулиці з двостороннім рухом
поч
Зупинися на тротуарі лицем до вулиці Поглянь наліво
поки зліва є машини, рухомі у бік переходу
нц
Чекай кц Йди до середини вулиці; Зупинися Поглянь направо поки справа є машини, рухомі у бік переходу
нц
Чекай кц
Йди до тротуару протилежної сторони вулиці кін
Контрольні питання
- Чим розрізняються прості і складені команди? Приведіть приклади простих і складених команд.
- Перерахуйте всі службові слова, використовувані: а) в командах галуження; б) у командах повторення.
- Що зробить виконавець алгоритму алг одягнутися по погоді поч
якщо на вулиці температура менша —10 °С
то Надіти шубу все Надіти куртку кін якщо на вулиці: а) —15 °С; б) +20 °С; в) —10 °С? Запишіть алгоритм, враховуючи, що при температурі вище +10 °С куртку одягати не потрібно.
Для перегляду тексту необхідно залогінитись.