Алгоритм і його властивості
Рішення задач на комп'ютері засноване на понятті алгоритму. Алгоритм - це точне розпорядження, що визначає обчислювальний процес, що веде від варійованих початкових даних до вихідного результату.
Алгоритм означає точний опис певного процесу, інструкцію з його виконання. Розробка алгоритму є складним і трудомістким процесом. Алгоритмізація - це техніка розробки (складання) алгоритму для розв'язання задач на ЕОМ.
Образотворчі засоби для опису (подання) алгоритму
Для запису алгоритму розв'язання задачі застосовуються наступні образотворчі способи їх представлення:
Словесно-формульне опис
Блок-схема (схема графічних символів)
Алгоритмічні мови
Операторні схеми
Псевдокод
Для запису алгоритму існує загальна методика:
Кожен алгоритм повинен мати ім'я, яке розкриває його сенс.
Необхідно позначити початок і кінець алгоритму.
Описати вхідні і вихідні дані.
Вказати команди, які дозволяють виконувати певні дії над виділеними даними
Загальний вигляд алгоритму
Алгоритм:
Назва алгоритму
Опис даних
Початок
Команди
Кінець
формульний-словесний спосіб запису алгоритму характеризується тим, що опис здійснюється за допомогою слів і формул. Зміст послідовності етапів виконання алгоритмів записується на природному Професійною мовою предметної області в довільній формі.
Графічний спосіб опису алгоритму (блок - схема) отримав найширше розповсюдження. Для графічного опису алгоритмів використовуються схеми алгоритмів або блокові символи (блоки), які з'єднуються між собою лініями зв'язку.
Кожен етап обчислювального процесу представляється геометричними фігурами (блоками). Вони діляться на арифметичні або обчислювальні (прямокутник), логічні (ромб) і блоки вводу-виводу даних (Паралелограм).
Схеми алгоритмів:
Порядок виконання етапів вказується стрілками, з'єднуючими блоки. Геометричні фігури розміщуються зверху вниз і зліва на право. Нумерація блоків проводиться в порядку їх розміщення в схемі.
Алгоритмічні мови - це спеціальний засіб, призначене для запису алгоритмів в аналітичному вигляді. Алгоритмічні мови близькі до математичних виразів і до природним мовам. Кожен алгоритмічна мова має свій словник. Алгоритм, записаний на алгоритмічній мові, виконується за суворими правилами цього конкретного мови.
Операторні схеми алгоритмів. Суть цього способу опису алгоритму полягає в тому, що кожен оператор позначається буквою (наприклад, А - арифметичний оператор, Р - логічний оператор і т.д.).
Оператори записуються зліва направо в послідовності їх виконання, причому, кожен оператор має індекс, що вказує порядковий номер оператора. Алгоритм записується в один рядок у вигляді послідовності операторів.
Псевдокод - система команд абстрактної машини. Цей спосіб запису алгоритму за допомогою операторів близьких до алгоритмічним мовам.
Принципи розробки алгоритмів і програм
Типи алгоритмічних процесів
За структурою виконання алгоритми і програми діляться на три види:
Лінійні
гілкуються
Циклічні
Лінійний алгоритм (лінійна структура) - це такий алгоритм, в якому всі дії виконуються послідовно один за одним і тільки один раз. Схема являє собою послідовність блоків, які розташовуються зверху вниз у порядку їх виконання. Первинні та проміжні дані не роблять впливу на напрямок процесу обчислення.
Алгоритми розгалужується структури
На практиці часто зустрічаються задачі, в яких в Залежно від початкових умов або проміжних результатів необхідно виконати обчислення за одним або іншим формулами.
Такі завдання можна описати за допомогою алгоритмів розгалужується структури. У таких алгоритмах вибір напрямку продовження обчислення здійснюється за підсумками перевірки заданої умови. Розгалужені процеси описуються оператором IF (умова).
Циклічні обчислювальні процеси
Для вирішення багатьох завдань характерно багаторазове повторення окремих ділянок обчислень. Для вирішення таких завдань застосовуються алгоритми циклічної структури (циклічні алгоритми). Цикл - послідовність команд, яка повторюється до тих пір, поки не буде виконано задане умова. Циклічне опис багаторазово повторюваних процесів значно знижує трудомісткість написання програм.
Існують дві схеми циклічних обчислювальних процесів.
Особливістю першої схеми є те, що перевірка умови виходу з циклу проводиться до виконання тіла циклу. У тому випадку, якщо умова виходу з циклу виконується, то тіло циклу не виконується жодного разу.
Особливістю другої схеми є те, що цикл виконується бодай один раз, так як перша перевірка умови виходу з циклу здійснюється після того, як тіло циклу виконано.
Існують цикли з відомим числом повторень і ітераційні цикли. При ітераційному циклі вихід з тіла циклу, як правило, відбувається при досягненні заданої точності обчислення.
Мови програмування
Мови програмування - це штучні мови записи алгоритмів для виконання їх на ЕОМ. Програмування (кодування) - складання програми по заданому алгоритму.
Класифікація мов програмування. Загалом, мови програмування діляться на дві групи: операторні і функціональні. До функціональним відносяться ЛИСП, ПРОЛОГ і т.д.
Операторні мови поділяються на процедурні і непроцедурного (Smalltalk, QBE). Процедурні діляться на машино - орієнтовані і машино - незалежні.
До машино - орієнтованим мовам відносяться: машинні мови, автокодом, мови символічного кодування, асемблери.
До машино - незалежним мов відносяться:
Процедурно - орієнтовані (Паскаль, Фортран та ін)
Проблемно - орієнтовані (ЛИСП та ін)
Об'єктно-орієнтовані (Сі + +, Visual Basic, Java та ін)
Засоби та правила побудови блок-схем
Блок-схема є формою представлення алгоритму з допомогою графічних символів. Графічні символи, їх розміри, а також правила побудови блок-схем визначені державними стандартами. Розглянемо часто вживані графічні символи (повний список включає 42 символу).
Процес. Виконання операції або групи операцій, в внаслідок чого змінюється значення, форма подання або розташування даних.
Усередині символу або ж у вигляді коментаря на природному мовою або у вигляді формули записуються дії, які виробляються при виконанні операції або групи операцій.
Рішення. Вибір напрямку виконання алгоритму або програми в залежності від деяких змінних умов.
Символ використовується для зображення уніфікованих структур:
розвилки ПОВНА
розвилки НЕПОВНА
ВИБІР
ЦИКЛ-ДО
ЦИКЛ-ПОКИ
Модифікація. Виконання операцій, які змінюють команди або групу команд, що змінюють програму.
Символ використовується для зображення уніфікованої структури циклу з параметром. Усередині символу записується параметр циклу з зазначенням початкового і кінцевого значень, а також крок зміни циклу, якщо він не дорівнює одиниці.
зумовлених процес. Використання раніше створених і окремо описаних алгоритмів або програм (процедур, функцій, програмних модулів). Символ служить для вказівки звернення до процедур, функцій, програмним модулям.
Ручне введення. Введення даних оператором в процес обробки за допомогою пристрою, безпосередньо сполученого з комп'ютером (наприклад, клавіатура).
Дисплей. Введення - виведення даних у випадку, якщо безпосередньо підключений до процесора пристрій відтворює дані і дозволяє оператору вносити зміни в процесі їх обробки.
Документ. Введення - виведення даних, носієм яких служить папір.
Лінія потоку. ...
