ПЛАН ЗАНЯТТЯ No 13
Дата: група: Дисципліна: Алгоритми та структури даних. Тема: Допоміжні алгоритми. Мета:
Методична: закріпити методику проведення лекційного заняття. Дидактична: систематизувати знання та вміння з побудови алгоритмів. Виховна: зміцнювати бажання вивчення дисципліни.
Вид заняття: лекційне заняття. Форми та методи проведення заняття: інформаційно- рецептивні, фронтальне опитування, викладання нового матеріалу.
Міжпредметні зв’язки:
- Дисципліни, що забезпечують: математичний аналіз, лінійна алгебра та аналітична геометрія.
- Дисципліни, що забезпечуються: алгоритмічні мови та програмування, об'єктно-орієнтоване програмування.
Науково-методичне забезпечення:
- Алтухов Е.В., Рыбалко Л.А., Савченко В.С. Основы информатики и
вычислительной техники: Учеб. пособие для учащ. средн. спец. уч. заведений. – М.: Высш. шк., 1992. – 303 с. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное
пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с
ХІД ЗАНЯТТЯ.
- Організаційний момент: перевірка відсутніх, зовнішнього вигляду,
готовності аудиторії. 2. Повідомлення теми, формування мети та основних завдань. 3. План викладання нового матеріалу: надано в конспекті лекції. 4. Актуалізація опорних знань:
- Дати визначення похідної;
- Дати визначення первісної, невизначеного інтегралу;
- Дати визначення диференціалу;
- Визначити зв’язок неперервності та диференційованості;
- Необхідні умови інтегрованості функції;
- Таблиця похідних, таблиця інтегралів основних елементарних функцій. 5. Вивчення нового матеріалу: Тема лекції: Допоміжні алгоритми.
- Мотивація вивчення матеріалу: диференціальні рівняння – це основний сучасний засіб розв’язання прикладних задач, який дає змогу описати математичну модель на зрозумілій мові. Тому, сучасному студенту необхідно вміти не тільки розв’язувати основні типи звичайних диференціальних рівнянь, але моделювати за допомогою диференціальних рівнянь текстові задачі.
- План вивчення нового матеріалу: надається в конспекті лекції. 6. Виклад нового матеріалу: конспект лекції надається. 7. Закріплення нового матеріалу: обговорення окремих питань алгоритмів. 8. Підведення підсумків заняття. 9. Домашнє завдання:
Викладач М.П.Леверя
Лекція No10 Тема: Допоміжні алгоритми.
- Поняття допоміжного алгоритму та його призначення . 2. Процедури. 3. Функції. 4. Приклади розв'язання задач з використанням допоміжних
алгоритмів.
- Поняття допоміжного алгоритму та його призначення .
При розробці програми іноді з'являються повторювані групи дій або виникає необхідність поділити алгоритм на функціональні модулі, зробити його структуру ієрархічною. Для цього існують засоби організації допоміжних алгоритмів. При розв'язанні складної задачі рекомендується алгоритм розроблювати «зверху вниз», від більш загального плану до докладного. У такому вигляді головний алгоритм відповідає укрупненому плану розв'язання задачі, а його команди — виклику відповідної підзадачі, реалізованої у вигляді допоміжного алгоритма. Ідучи таким шляхом створення алгоритму, можна окремі функції, що найбільш часто використовуються, реалізувати спочатку у вигляді невеликих допоміжних алгоритмів, перевірити їх на контрольних прикладах і, переконавшись у правильності, включати їх до складу основного алгоритму. Використання допоміжних алгоритмів дозволяє розробляти алгоритм частинами, доручати реалізацію великих проектів окремим групам розробників.
Допоміжний алгоритм є частиною основного алгоритму, його опис дається між розділом арг головної програми та її тілом алгоритму. Допоміжних алгоритмів може бути декілька, їх описи розміщуються у довільному порядку один за одним. Опис допоміжного алгоритму можна порівняти із записуваною в математиці формулою «у загальному вигляді», в яку при розрахунках підставляються конкретні значення. Як і формулу, допоміжний алгоритм можна використовувати для різних даних, які передаються з алгоритму, що його викликає. Тому параметри, які використовуються в описі допоміжного алгоритму, називають формальними, а параметри, над значеннями яких виконуються операції, вказані в допоміжному алгоритмі, називають фактичними.
Допоміжний алгоритм — це спеціально оформлений алгоритм, який можна використовувати багато разів при розв'язуванні задач.
Розрізняють два види допоміжних алгоритмів: процедури і функції. Основна різниця між ними полягає в тому, що процедура може мати будь-яку кількість вхідних і вихідних даних (параметрів), а функція — довільну кількість вхідних і тільки одне вихідне значення.
Допоміжні алгоритми мають структуру, аналогічну до структури головного алгоритму. Вони починаються з заголовка із спеціальним словом — ознакою допоміжного алгоритму, далі вказується ім'я допоміжний алгоритму і, при потребі, список формальних параметрів. Далі розміщуються всі розділи описів,
які є в головному алгоритмі: мітки, константи, типи і змінні. У цих розділах описуються дані, які використовуються тільки всередині допоміжного алгоритму. Такі дані називаються локальними, У допоміжному алгоритмі можуть використовуватися також змінні, описані у викликаючому алгортимі. Такі змінні називаються глобальними. Вони можуть використовуватися не лише алгоритмами, які викликають, а й допоміжними алгоритмами.
При роботі з допоміжними алгоритмами виділяється два етапи: опис допоміжного алгоритму, тобто запис алгоритму розв'язання задачі в спеціальній формі, і виклик допоміжного алгоритму — передача йому даних на обробку з викликаючого алгоритму та отримання результатів.
- Процедури.
Процедура - це допоміжний алгоритм, який має будь-яку кількість вхідних і вихідних даних. Процедура може бути описана без параметрів і з параметрами. Параметри в заголовку процедури використовуються для обміну інформацією між процедурою і алгоритмом, який її викликає. Вони визначають дані, які передаються на обробку до процедури, і дані, які отримуються у вигляді результатів.
Процедура без параметрів може реалізовувати будь-який алгоритм. Усі змінні, з якими проводять дії оператори процедури, визначаються у викликаючому алгоритмі, їм присвоюються потрібні для виконання процедури значення. Для виклику процедури без параметрів просто вказується її ім'я.
Для передавання даних до процедури і отримання з неї результатів використовуються формальні і фактичні параметри. Формальні параметри — це умовні позначення в описі процедури; вони описуються в її заголовку. При виклику процедури після її імені в дужках слід вказати список фактичних параметрів, які конкретизують значення, над якими будуть виконуватись операції в тілі процедури. Послідовність, кількість і тип формальних і фактичних параметрів повинні збігатися. Формальні параметри, описані в заголовку процедури, більше ніде не описуються.
Опис процедури має такий вигляд: продедура ім'я (формальні параметри) {опис локальних змінних} поч
{оператори} кін
- Функції.
Допоміжний алгоритм, який має єдиний результат, може бути оформлений як функція. Опис його має вигляд:
ім'я_функції (список формальних параметрів) {опис локальних змінних} поч
{оператори} кін
4. Приклади розв'язання задач з використанням допоміжних
алгоритмів. 1. Знайти найбільше з 3-х чисел.
Алгоритмічна мова Блок-схема Алгоритм пошуку більшого з 2-ох чисел α і β можна записати слідуючим чином:
алг. БІД (дійсн. α, β, γ) поч
якщо α > β, то γ : = α інакше: γ : = β все кін Алгоритм пошуку більшого з 3-х чисел можна скласти в формі дворазового звернення до алгоритму Б і Д:
алг. БІТ (дійсн a, b, c, y) арг. а, b, с рез. y поч. дійсн. z
виконати БІД (a, b, z) виконати БІД (z, c, y) кін.
1) БІД 2) БІТ
- +
Перевірку правильності алгоритму можна провести заповнивши трасировочну таблицю:
1) БІТ
2) БІД (a, b, z)
1) БІД (z, c, y)
поч
поч
а, b, с
α > β
БІД (a, b, z)
γ : = β
γ : = α БІД (z, c, y)
кін
y
кін
Шаг Операція a b c z y Перевірка умови
1 Введення а, b, с 4 1 6
2 БІД (a, b, z) 4 1 4
3 БІД (z, c, y) 6 4 6
4 Виведення y 6
Шаг Операція α β γ Перевірка умови
1 α > β 4 1 4>1, так
2 γ : = α 4 1 4
Шаг Операція α β γ Перевірка умови
1 α > β 4 6 4>6, ні
2 γ : = β 4 6 6
2. Визначити площу трикутника
алг Площа трикутника (дійсн x1,y1,x2,y2,x3,y3,S)
арг. x1,y1,x2,y2,x3,y3 рез. S поч.
Ввести x1,y1,x2,y2,x3,y3 виконати ДC (x1,y1,x2,y2,d1) виконати ДC (x2,y2,x3,y3,d2) виконати ДC (x3,y3,x1,y1,d3) виконати Площ (d1,d2,d3,S) Вивести S кін
Модуль 1 (довжина сторін ДС)
Алгоритмічна мова Блок-схема алг. ДС (дійсн. nx,ny,kx,ky,d) поч
d =
( kx - nx () 2 + ky - ny ) 2 кін поч
x1,y1,x2,y2,x3,y3
ДC (x1,y1,x2,y2,d1)
ДC (x2,y2,x3,y3,d2)
ДC (x3,y3,x1,y1,d3)
Площ (d1,d2,d3,S)
S
кін
початок
кінець
Модуль 2 (площа трикутника Площ)
Алгоритмічна мова Блок-схема алг. ДС (дійсн. a,b,c,S) поч дійс p
2
d =
( nxkx - () 2 + nyky - ) 2 початок
p
=
cba
+
+ 2
S = cpbpapp ( - )( - )( - ) кін
p
=
cba
+ + S =
cpbpapp ( - )( - )( - ) кінець
Розв'язати задачі:
- Скласти алгоритм обчислення значення функції: nny = )!1(!3 + + 2. Скласти алгоритм обчислення значення функції по формулі: y = sin a + sin b , де
sin
xx =
- xxxx
3
!9!7!5!3 + 5 - 7 9 + 3. Баба-Яга записалася на курси водіїв літальних апаратів. Але справи в неї були
кепські, бо вона ніяк не могла запам'ятати, яким чином визначається тривалість польоту, якщо відомі швидкість і відстань. Довелося їй звернутися по допомогу до Хлопчика-Мізинчика, який швиденько написав їй шпаргалку, куди Бабі-Язі треба було лише підставити свої значення. Як виглядала послідовність дій у цій шпаргалці і як нею користувалася Баба-Яга?
- Контрольні питання
- Які є види допоміжних алгоритмів? 2. Що таке допоміжний алгоритм? 3. Як записується процедура? 4. Як записується функція? 5. Що таке формальні та фактичні параметри?
Список літератури:
- Алтухов Е.В., Рыбалко Л.А., Савченко В.С. Основы информатики и
вычислительной техники: Учеб. пособие для учащ. средн. спец. уч. заведений. – М.: Высш. шк., 1992. – 303 с. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное
пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.
Для перегляду тексту необхідно залогінитись.