Форми опису алгоритмів

Размещено на http://www.allbest.ru/

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

Складання й запис алгоритмів. Базові алгоритмічні структури. Логічні значення та логічні операції. Запис логічних виразів мовою програмування. Алгоритмічна конструкція розгалуження. Оператори одно- дво- та поліальтернативного розгалуження. Вкладені оператори розгалуження. Прапорці та групи перемикачів. Реалізація розгалужень за допомогою прапорців та груп перемикачів. Алгоритмічна конструкція повторення та її різновиди: визначені та невизначені цикли, цикли з після умовою та з передумовою. Оператори циклів. Обчислення сум, добутків, середніх значень наборів чисел. Розв'язування задач, що потребують обчислень за ітеративними формулами. Розв'язування задач, що потребують комбінування циклічних операторів з операторами розгалуження.

Моделі та способи їх зображення

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

Модель (від лат. «modulus» - міра, зразок, норма) - це прообраз, опис або зображення якогось об'єкта.

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

Модель у голові людини існує у формі не до кінця усвідомлених уявних зображень. Такі моделі, отримані внаслідок висновків, називаються вербальними (від лат. «verbalis» - усний). Вербальними називаються також моделі, викладені в розмовній формі. Отже, всі абстрактні моделі можна поділити на знакові і вербальні (мал. 79.1).

Мал. 79.1 Класифікація моделей за способом зображення

3 математичними моделями не слід плутати інформаційні моделі.

Інформаційна модель - це модель, що описує інформаційні процеси або містить інформацію про властивості і стан об'єктів, процесів, явищ.

Найпростішими прикладами інформаційних моделей є різні загадки

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

Комп'ютерна модель - це модель, реалізована за допомогою програмних засобів.

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

1. Етапи побудови комп'ютерної моделі

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

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

Пояснимо на прикладах. Скажімо, вам потрібно побудувати електронну таблицю-довідник про ваших знайомих. Ви описали цю задачу у вигляді питання «як отримати таблицю-довідник? ». Метою створення таблиці буде отримання оперативної інформації про ваших друзів і знайомих. Внаслідок попереднього аналізу відомостей, які вас цікавлять, ви вирішили, що майбутня таблиця мае складатися зі стовпців з ПІБ, адресою, телефоном і датою народження.

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

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

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

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

Від інформаційної моделі до програми

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

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

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

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

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

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

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

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

Алгоритми і способи їх опису

Поняття алгоритму

Термін «алгоритм» походить від назви середньоазіатського міста Хорезм. У цьому місті в IX ст. жив математик і астроном Мухамед, який сформулював правила чотирьох арифметичних дій. Арабський варіант його імені Аль-Хорезмі, що в Європі записувався латиною як Algorithmi, і став основою терміна "алгоритм". Однак пізніше під словом алгоритм стали розуміти правила знаходження найбільшого спільного дільника, які були викладені ще в працях великого давньогрецького математика Евкліда (III ст. до н.е.). За наших часів поняття алгоритму було узагальнено, і словом "алгоритм" стали позначати опис будь-якої послідовності дій. Поняття алгоритму є одним із фундаментальних у сучасній математиці й інформатиці.

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

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

Словесний запис алгоритмів

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

Словесний спосіб запису заснований на тій чи іншій природній мові спілкування (див. алгоритм Евкліда). Однак словесний запис алгоритму відрізняється від звичайних мовних конструкцій ретельнішим добором слів і фраз, який не допускає повторень або двозначного тлумачення. Крім того, у запису алгоритму можуть використовуватися математичні символи і вирази.

Розглянемо словесний спосіб запису ще на одному простому прикладі. Маємо знайти модуль величини x (тобто значення | X |) і надати цього значення змінній Y. Під час побудови алгоритму скористаємося визначенням модуля: | x | =x при x> 0 і | x =-x при x<0. Алгоритм можна записати у такий спосіб.

Початок.

Ввести числове значення величини X.

Якщо X> 0, то Y надати значення X, інакше Y надати значення -X.

Вивести значення Y.

Кінець.

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

Блок-схеми алгоритмів

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

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

У алгоритмах часто використовуються команди введення і виведення значень. Цим командам відповідають блоки введення-виведення:

Тут лівий блок означає введення величини x, а правий блок - виведення Y. За допомогою наведених вище блоків ви можете скласти найпростіший алгоритм введення величини X

Відповідно до цього алгоритму в програму вводиться значення величини X. Однак програма, що складається тільки з операції введення, навряд чи доцільна. Звичайно над введеною величиною виконуються певні дії, що позначаються прямокутними (операторними) блоками:

У середині прямокутників записані вирази, що виконуються над величинами. Лівий блок означає присвоювання змінній X значення суми Х + 1 (про операції присвоювання йтиметься в наступному параграфі). Правий блок відповідає за знаходження різниці x-Y і надання значення різниці змінній z. Операторні блоки можуть мати кілька входів і лише один вихід.

Запишемо найпростіший алгоритм обчислення квадрата якогось числа:

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

Усі наведені вище блоки дозволяють організувати послідовне виконання інструкцій алгоритму. Однак на практиці часто виникають ситуації, коли залежно від виконання будь-якої умови маємо змінити послідовний хід обчислень. Прикладом такої умови є нерівність X> 0 в алгоритмі знаходження модуля числа X (див. попередній пункт). У схему алгоритму логічна умова вводиться за допомогою умовного блока. Цей блок прийнято зображати у вигляді ромба з одним входом і двома виходами:

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

Наведемо як приклад алгоритм обчислення модуля числа:

Схема розгалуження

Схема розгалуження відповідає умовному оператору. Ця схема складається з логічного елемента з перевіркою умови P і блоків S₁ і S₂ (мал. 85.1,6). Якщо один із блоків відсутній, то отримуємо неповний умовний оператор(мал.К5.1,в).

а 6 в

Мал. 85.1 Базові структури: а - проходження; б, в - розгалуження

Запис цього алгоритму обмежують блоки початку і кінця. За блоком початку алгоритму йде блок введення значень x, а за ним - умовний блок. В умовному блоці виконується перевірка умови X> 0 і в результаті перевірки здійснюється перехід no одній із гілок Так або Ні. На кожній із гілок розташований операторний блок надання значень змінній Y. Після операції надання гілки алгоритму сходяться, і наступна інструкція алгоритму міститься в блоці виведення отриманого значення Y.

Прикладом використання неповного умовного оператора може бути обчислення алгебраїчного виразу:

модель інформаційний комп'ютерний оператор

що відповідно читається як «якщо X > 0, то покласти рівним X, інакше - Х/2». Блок-схема алгоритму показана на мал. 83.1.

Множинне розгалуження. Оператор вибору

Якщо в алгоритмі потрібно зробити вибір між трьома і більше варіантами виконуваних послідовностей (а не двома, як у простому розгалуженні), то прийдемо до множинного розгалуження. Множинне розгалуження - це узагальнення умовного Мал. 83.1. Блок-схема з оператора, розглянутого вище.

Цикли

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

Цикл із передумовою

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

а б

Мал. 34.1 Блок-схеми операторів циклу: а - цикл з передумовою; б - цикл із постумовою

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

Розглянемо приклад. Нехай потрібно обчислити залишок від ділення двох цілих чисел А і В (A>=0, B>0). Знайти цю величину можна відніманням числа В від числа А, доки А залишається більшим від В. Наприклад, залишок від ділення 56 на 5 можна знайти, віднімаючи від 56 числа 5 і порівнюючи отриману різницю з 5. Оскільки 51>5, треба знову від різниці відняти 5 і результат порівняти з 5. Обчислення триватимуть, доки не буде отримано різницю 1, яка є залишком відділення 56 на 5.

Комбінування базових структур

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

Ці вимоги можна задовольнити, якщо дотримуватися структурного niдхoду в основі якого лежить твердження, що алгоритм будь-якого ступеня складності можна відобразити за допомогою трьох базових структур: проходження, розгалуження і циклу. Базові структури можна комбінувати одну з одною, організовуючи проходження структур, розгалуження, вкладення однієї структури в іншу.

Створювати складнішу структуру за допомогою базових структур можна двома способами:

- приєднувати одну структуру до іншої, утворюючи послідовність структур;

- замінювати функціональні блоки S₁ i S, кожної з базових структур вкладеними в них структурами.

Ці правила дозволяють будувати алгоритми будь-якої складності, розвиваючи їх не тільки «у ширину», а й «усередину». Одержувані алгоритми мають чітку та ясну структуру. Приклади комбінованих алгоритмів подані на мал. 85.2, а, б, в. г.

Мал. 85.2 Комбіновані схеми алгоритмів: а - «умова в умові»; б - «цикл в умові»; в - «цикл у циклі»; г - триразове вкладення операторів

Метод покрокової деталізації

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

Розглянемо метод покрокової деталізації на прикладі розв'язання квадратного рівняння

Ах² + bx + c = 0.

На першому етапі розв'язуються такі задачі:

1. Уведення даних.

2. Розрахунок детермінанта.

3. Аналіз існування коренів рівняння і їхнє обчислення.

Виведення результату розрахунку.

Завершення задачі.

На другому етапі здійснюється деталізація кожного з названих пунктів. | Розглянемо для прикладу пункт 1: 1.1. Увести коефіцієнт а.

1.2.Якщоа =0, повідомити, що рівняння є лінійним, і перейти до пункту 5. 1.3.Увести коефіцієнт b.

1.4. Увести коефіцієнт c.

1.5. Отримати підтвердження користувача, що значення коефіцієнтів правильні, якщо ні, то повернутися до пункту 5.

Наступному етапу деталізації відповідатиме запис програмного коду.

Размещено на Allbest.ru