| Главная » Файлы » Для вчителя » Інформатика | [ Добавить материал ] |
алгоритми та способи їх опису. Урок
| [ · Скачать удаленно (130 Kb) ] | 19.07.2010, 14:59 |
| Тема: алгоритми та способи їх опису. Мета: ввести поняття алгоритму, способів їх опису, формувати в учнів вміння складати алгоритми і записувати їх різними способами; розвивати пам’ять, мислення; виховувати старанність, працелюбність наполегливість. Хід уроку І. Організаційний момент. ІІ. Перевірка домашнього завдання. Контрольні запитання 1. Що таке модель? Наведіть приклади матеріальних і абстрактних моделей. 2. Що розуміється під знаковою моделлю? 3. Що таке математична та інформаційна модель? У чому різниця між ними? 4. Що таке комп'ютерна модель? 5. Які унікальні можливості дає комп'ютерне моделювання? 6. Назвіть основні етапи створення комп'ютерної моделі. 7. Що таке комп'ютерні експерименти? 8. Назвіть тип програмного забезпечення, яке використовується для реалізації ком¬п'ютерних моделей. ІІІ. Вивчення нового матеріалу. Алгоритми і способи їх опису Поняття алгоритму Термін «алгоритм» походить від назви середньоазіатського міста Хорезм. У цьому місті в IX ст. жив математик і астроном Мухамед, який сформулював правила чотирьох арифметичних дій. Арабський варіант його імені Аль-Хорезмі, що в Європі записувався латиною як Algorithmi, і став основою терміна "алгоритм". Однак пізніше під словом алгоритм стали розуміти правила зна-ходження найбільшого спільного дільника, які були викладені ще в працях вели¬кого давньогрецького математика Евкліда (III ст. до н.е.). За наших часів поняття алгоритму було узагальнено, і словом "алгоритм" стали позначати опис будь-якої послідовності дій. Поняття алгоритму є одним із фундаментальних у сучасній математиці й інформатиці. Алгоритм – це точний і зрозумілий опис послідовності дій над заданими об'єктами, що дозволяє отримати кінцевий результат. Ви вже не раз зустрічалися з алгоритмами в інших шкільних предметах. На¬приклад, у хімії отримання тієї чи іншої сполуки можна описати за допомогою алгоритму. Але найбільше прикладів алгоритмів у математиці – науці, в якій зародилося саме це поняття. По суті, математика займається вивченням різних алгоритмів і створенням нових. До алгоритмів із шкільного курсу математики можна віднести правила виконання арифметичних дій, правила знаходження розв'язків рівнянь тощо. У вигляді алгоритмів можна сформулювати правила побудови різних геометричних фігур (згадайте задачу на побудову), а також рекомендації щодо розв'язку багатьох типових задач. До слова «алгоритм» близькі за значенням слова: спосіб, рецепт. Одні алгоритми в інформатиці – це не тільки рецепти розв'язання задач. Алгоритми розробляються, насамперед, із метою автоматизації дій виконавця. Складання алгоритму починається з розбиття описуваного процесу на послідовність окремих кроків. Властивість розбивки алгоритму на окремі кроки називається дискретністю алгоритму. Кожний крок алгоритму формулюється у вигляді інструкцій (команд), тобто визначених розпоряджень виконавцю. Розглянемо як приклад алгоритм Евкліда, вигаданий ним для знаходження найбільшого спільного дільника (НСД) двох натуральних чисел т і п. Відомо, що НСД може бути отриманий шляхом послідовного ділення спочатку більшого числа на менше, потім меншого числа на отриманий залишок, першого залишу на другий залишок і т.д. Ділення триває доти, доки у залишку не утвориться нуль. Останній дільник і є НСД. Наведемо приклад знаходження НСД для пари чисел 66 і 18: 66:18 = 3 +(12) 18:12 = 1 + (6) 12:6 = 2 Тут у дужках записаний залишок від ділення. В останній рівності залишок відсутній, тому НСД дорівнює дільнику, тобто 6. Алгоритм розв'язання задачі про НСД для пари чисел т і п записується у такий спосіб: 1. Якщо т > п, то перейти до 3. , інакше перейти до 2. 2. Якщо п > т, то перейти до 4. , інакше перейти до 5. 3. Від т відняти п і вважати цю різницю новим значенням т. Перейти до 1. 4. Від п відняти т і вважати цю різницю новим значенням п. Перейти до 1. 5. Вважати, що НСД дорівнює т. Кінець. Зверніть увагу, що пункти 3, 4 цього алгоритму виконуються лише тоді, коли т > п або у випадку п > т, тобто коли т не дорівнює п. Останній пункт:5 виконується лише тоді, коли п = т (залишок дорівнює нулю). Виконавець і властивості алгоритму Алгоритм розв'язання однієї й тієї самої задачі може бути поданий по-різному. Якщо ви навчаєте чомусь собаку, ви будете давати усні команди зрозумілою для неї мовою. Якщо ж ви навчаєте свого приятеля їздити на велосипеді, то система команд, які він може виконати, буде, звичайно, ширшою. Алгоритм їзди ви можете описати усно, але можете за бажанням записати на папері. Алгоритми складаються з орієнтацією на певного виконавця алгоритму: дресированої тварини, людини, автомата, ЕОМ. До алгоритму мають входити команди, які виконавець може виконати, і неприпустимі команди, які він не може виконати. У кожного виконавця є свій кінцевий набір команд, які для нього зрозумілі і можуть бути виконані. Цей набір називають системою команд вико¬навця. Користуючись системою команд, виконавець може виконувати алгоритм формально, не вникаючи у зміст поставленої задачі. Від виконавця вимагається лише виконання послідовності дій, передбачене алгоритмом. Коли алгоритм зро¬зумілий конкретному виконавцю, кажуть, що такий алгоритм має властивість певності. Завдяки певності багатократне виконання одного алгоритму різними виконавцями за тих самих вихідних умов приведе до однакових результатів. Для отримання конкретного результату не допускаються довільні дії з боку виконавця. Образно кажучи, алгоритм – це не кулінарний рецепт, і в ньому неприпустимі вказівки типу «Додати дві-три ложки цукру» або «Зняти з вогню через кілька хвилин». Вказівки, зрозумілі у певних ситуаціях для людини, мо¬жуть загнати у глухий кут автомат. Потрібно уникати також ситуацій, коли після виконання чергової команди виконавцю незрозуміле, яка команда має виконуватися наступною. Крім певності, алгоритм повинен мати низку інших властивостей. Очевидна властивість алгоритму, як було зазначено раніше, – це його дискретність. Будь-який алгоритм складається з послідовності закінчених дій – кроків. Перехід до наступного кроку можливий лише після завершення попереднього. Ще однією властивістю алгоритму, що формулюється як вимога, є його результативність. Виконання алгоритму має приводити до конкретного резуль¬тату – розв'язання задачі протягом певного числа кроків. Під розв'язанням задачі може розумітися також повідомлення про те, що задача розв'язання не має. Найкращими є ті алгоритми, які забезпечують розв'язання широкого кола задач (наприклад, розглянутий вище алгоритм Евкліда, алгоритми виконання арифметичних дій). Про такі алгоритми кажуть, що вони мають властивість масовості. Вони дозволяють розв'язувати (і неодноразово) не одну конкретну задачу, а багато однотипних задач. Властивість масовості значно збільшує практичну цінність алгоритму. Словесний запис алгоритмів Для зображення алгоритмів можна користуватися різними способами запи¬су, які відрізняються ступенем наочності і точності. Деякі способи орієнтовані на виконавця – людину, інші – на виконання комп'ютером, треті є допоміжними (використовуються для полегшення міркувань). У цьому параграфі ми роз¬глянемо три способи подання алгоритмів: за допомогою звичайної мови спіл¬кування, із використанням блок-схем і за допомогою навчальної алгоритмічної мови. Словесний спосіб запису заснований на тій чи іншій природній мові спілку¬вання (див. алгоритм Евкліда). Однак словесний запис алгоритму відрізняється від звичайних мовних конструкцій ретельнішим добором слів і фраз, який не допускає повторень або двозначного тлумачення. Крім того, у запису алгоритму можуть використовуватися математичні символи і вирази. Розглянемо словесний спосіб запису ще на одному простому прикладі. Має¬мо знайти модуль величини X (тобто значення ) і надати цього значення змінній у. Під час побудови алгоритму скористаємося визначенням модуля;, |х| = х при х >=0 і |х| = -х при х<0. Алгоритм можна записати у такий спосіб. 1. Початок. 2. Ввести числове значення величини X. 3. Якщо , то Y надати значення X, інакше Y надати значення -X. 4. Вивести значення Y. 5. Кінець. Словесний запис найчастіше застосовується на початковому етапі вивченні алгоритмів і призначається для використання алгоритму людиною. Однак ця форма запису алгоритму має два істотних недоліки. По-перше, вона недостатньо наочна і, по-друге, її важко безпосередньо перекласти мовою програми. Блок-схеми алгоритмів Наочною формою запису алгоритмів є блок-схеми, що складаються з геометричних фігур - блоків. Кожний блок відповідає певній дії. Наприклад, запис алгоритму починається і закінчується такими блоками: Ці елементи називаються блоками початку і кінця алгоритму. Стрілки вказують напрямок виконання алгоритму. Блок Початок має одну вихідну стрілку, а блок Кінець — одну вхідну стрілку. У алгоритмах часто використовуються команди введення і виведення значень. Цим командам відповідають блоки введення-виведення: Тут лівий блок означає введення величини X, а правий блок — виведення Y. За допомогою наведених вище блоків ви можете скласти найпростіший алгоритм введення величини X: Відповідно до цього алгоритму в програму вводиться значення величини Х. Однак програма, що складається тільки з операції введення, навряд чи доцільна. Звичайно над введеною величиною виконуються певні дії, що позначаються прямокутними (операторними) блоками: У середині прямокутників записані вирази, що виконуються над величинами. Лівий блок означає присвоювання змінній Х значення суми Х+1. Правий блок відповідає за знаходження різниці Х-У і надання значення різниці змінній Z. Операторні блоки можуть мати кілька входів і лише один вихід. Запишемо найпростіший алгоритм обчислення квадрата якогось числа: Відповідно до цього алгоритму вводиться величина X, потім обчислюється квадрат цієї величини (добуток Х*Х) і виводиться отримане значення. Усі наведені вище блоки дозволяють організувати послідовне виконання інструкцій алгоритму. Однак на практиці часто виникають ситуації, коли залеж¬но від виконання будь-якої умови маємо змінити послідовний хід обчислень. Прикладом такої умови є нерівність Х>0 в алгоритмі знаходження модуля числа х (див. попередній пункт). У схему алгоритму логічна умова вводиться за допо¬могою умовного блока. Цей блок прийнято зображати у вигляді ромба з одним входом і двома виходами: Якщо умова, зазначена на зображенні блока, виконується (умова має зна¬чення Істина), то відбувається перехід по стрілці Так, якщо не виконується (значення Хибність) - по стрілці Ні. Завдяки умовному блоку обчислювальний процес ніби розгалужується, тобто умовний блок використовується для ор¬ганізації розгалуження. Наведемо як приклад алгоритм обчислення модуля числа: Запис цього алгоритму обмежують блоки початку і кінця. За блоком почат¬ку алгоритму йде блок введення значень X, а за ним — умовний блок. В умовному блоці виконується перевірка умови Х>0 і в результаті перевірки здійснюється перехід по одній із гілок Так або Ні. На кожній із гілок розташований операторний блок надання значень змінній Y. Після операції надання гілки алгоритму сходяться, і наступна інструкція алгоритму міститься в блоці виведення отриманого значення Y. Навчальна алгоритмічна мова Словесний запис алгоритму більше придатний для виконавця — людини. Якщо ж виконавцем є комп'ютер, то алгоритм маємо записувати за допомогою інструкцій, які легко перекладаються на мову програми. Однак, перед тим як складати програму, учням звичайно пропонується побудувати алгоритм розв'язання й описати його на навчальній алгоритмічній мові (НАМ). Розглянемо основні компоненти НАМ або, як її інакше називають, алгоритмічної нотації (слово «нотація» розуміється як «позначення»). Алфавіт Алфавіт НАМ нічим не обмежений: він може бути як англійським, так і українським. У нього можуть бути введені будь-які зрозумілі всім символи: знаків арифметичних операцій (+, -, *, /), знаки відношень (=,>,< тощо), спеціальні знаки тощо. Тобто алфавіт навчальної алгоритмічної мови є відкритим. Крім алфавіту, в алгоритмічній нотації визначаються службові слова, що є неподільними. До службових слів належать: алг - заголовок алгоритму; рез - результат; поч - початок алгоритму; чит - читання (введення); кін - кінець алгоритму; зап - запис (виведення); арг - аргумент; якщо, то, інакше - умовні інструкції та інші. Службові слова звичайно виділяються напівжирним шрифтом або підкресленням. Зміст багатьох із цих слів буде зрозумілий вам із подальшого викладу. Структури запису алгоритму Початок запису алгоритму в алгоритмічній мові завжди супроводжується заголовком типу: алг <ім'я алгоритму> Заголовок складається зі службового слова алг і короткої назви алгоритму (імені), наприклад, «Пошук символу» або «Обчислення кореня». Бажано, щоб ім'я відображало зміст алгоритму. Заголовок дозволяє використовувати даний алгоритм в інших алгоритмах за допомогою посилань на нього. Після заголовка йдуть списки аргументів і результатів роботи алгоритму (елементи списків відокремлюються один від одного комами); арг <список аргументів> рез <список результатів> Частина алгоритму, яка безпосередньо містить опис послідовності дій, нази¬вається частиною, що виконується. Вона починається службовим словом поч і закінчується словом кін. В алгоритмах роботи з величинами слідом за словом поч вказується список проміжних результатів із зазначенням їхніх типів. Між словами поч і кін розміщається послідовність інструкцій — серія. В окремих випадках серія може складатися усього з однієї інструкції, а також може бути порожньою. Оператори серії, що стоять у одному рядку, розділяються крапкою з комою. Загальний запис алгоритму може бути таким: алг <ім'я алгоритму> арг <список аргументів> рез <список результатів> поч <список проміжних результатів та їхніх типів> <серія> кін IV. Підсумок уроку. Запитання 1. Що такс алгоритм? Дайте визначення цього поняття. 2. Назвіть виконавців для таких алгоритмів: а - спосіб розв'язання задачі, що записує на дошці вчитель; б - інструкція про те, як завести автомобіль. 3. Назвіть відомі вам властивості алгоритмів. 4. Чи буде вважатися алгоритмом послідовність дій, що не приводить до будь-якого результату? Що таке результативність алгоритму? 5. Наведіть приклади властивості масовості алгоритму. 6. Назвіть відомі вам способи зображення алгоритмів. 7. Які переваги графічного зображення алгоритмів перед словесним записом? 8. Як властивість дискретності алгоритму пов'язана із зображенням алгоритму у вигляді блок-схеми? 9. Назвіть компоненти блок-схем алгоритмів. 10. Чи може умовний блок мати один вихід? 11. Що такс навчальна алгоритмічна мова? Які службові слова у ній застосовуються? V. Домашнє завдання. Вправи 1. Користуючись алгоритмом Евкліда, знайдіть НСД для таких пар чисел: 35 і 84; 195 і 585. 2. Запишіть алгоритм визначення площі трикутника за допомогою міліметрової лінійки і косинця з прямим кутом. 3. Складіть алгоритм обчислення залишку від ділення двох цілих чисел. Запишіть цей алгоритм у словесній формі, аналогічній алгоритму Евкліда. 4. Складіть словесний запис алгоритму для знаходження суми кінцевої арифметичної прогресії 1, 4, 7, 10,...31 (без використання формули для суми прогресії). 5. Побудуйте блок-схему обчислення розміру 2*|Х-11|. 6. Дано значення сторін трикутника а, b, с. Складіть блок-схему визначення того, чи є трикутник прямокутним. Скористайтеся теоремою Піфагора. | |
| Просмотров: 1260 | Загрузок: 258 | | |