НОУ ІНТУІТ, Лекція, Базові алгоритмічні структури
Розрізняють три базові алгоритмічні структури: прямування, розгалуження, повторення.
Структура слідування складається з двох команд із зазначеною черговістю їх виконання та має вигляд:
Структура типу розгалуження у повній формі складається з деякої умови, що перевіряється на істинність при виконанні структури, команди, що виконується при виконанні умови, що перевіряється, і команди, що виконується при невиконанні умови. Структура має вигляд
Ключові (службові) слова Паскаля - if (якщо), then (то), else (інакше). Ключові слова не можна змінювати, замінювати, оскільки їх зразки закріплені у перекладачі з мови Паскаль (про нього докладніше – нижче).
Приклад. Команда виду
Структура типу розгалуження у неповній формі – окремий випадок розгалуження у повній формі, у якій, за невиконання умови, управління просто передається наступній команді і більше ніяких дій команда розгалуження не здійснює. Ця структура має вигляд
Структура повторення (цикл) служить для компактного запису однієї й тієї ж набору команд, повторюваних різних значень параметрів команд.
Структура повторення типу "поки (while)" записується у вигляді:
Ключові слова Паскаля - while (поки що), do (виконувати), begin (початок), end (кінець).
Тілом циклу називається послідовність повторюваних команд, яка може бути і порожньою (випадок, що рідко зустрічається).
Частина команди циклу "while" - заголовок циклу.
Даний цикл виконується за правилом: якщо умова повторення для поточних параметрів не виконано, то повторення команд (тіла) циклу на цьому завершується; якщо воно виконано, то виконується тіло циклу і знову перевіряється умова повторення команд тіла циклу .
Приклад. Нехайнеобхідно знаходити суму всіх непарних елементів натурального ряду чисел доти, поки ця сума не перевищить значення n. Доданок, у якому ця сума перевищить n – включати до суми.
"Забудемо" тимчасово чисто математичне вирішення цього завдання - з використанням суми арифметичної прогресії з кроком 2. Алгоритм програма ) має вигляд
Друга форма повторення - цикл типу "до" (for), яка має вигляд
Тут – ім'я, ідентифікатор змінної, що перераховується.
Ключові слова Паскаля – for(для), to(к).
Цей цикл виконується за правилом: для початкового значення змінної виконуються команди тіла циклу по порядку і потім перевіряється, чи перевищило поточне значення змінної заданого кінцевого значення; якщо перевищило цикл закінчується, інакше значення змінної збільшується на одиницю і знову повторюється тіло циклу і т.д.
Приклад. Необхідно обчислити середню вартість одиниці всіх n видів товарів (одиниця виміру – та сама, наприклад, тонна), якщо вартість одиниці кожного товару збільшується на 10, а найменша вартість одиниці товару дорівнює 2. Якщо "забути" тимчасово краще, "чисто математичне Розв'язання цього завдання, то алгоритм буде мати вигляд
Розглянемо приклади алгоритмізації (програмування) завдань мовою Паскаль.
Приклад. Складемо алгоритм обчислення факторіалу заданого натурального числа n тобто твори n! = 1 * 2 * 3 *. * (n – 1) * n з використанням рекурентної формули n! = (n - 1)! * n. Опишемо метод рішення. Для цього зауважимо ланцюжок справедливих рівностей:
1! = 1, 2! = 1 * 2 = 1! * 2, 3! = 1 * 2 * 3 = 2! * 3, . m! = 1 * 2 * 3 * . * (m - 1) * m = (m - 1)! * m.
Отже, для обчислення факторіалу m! необхідно факторіал (m - 1)! домножити на m де m = 1, 2, . n. Програма на Паскалі має вигляд
Приклад. Складемо алгоритм переведення заданого десяткового натурального числа n у двійкову систему. Метод рішення визначається процедурою перекладу – послідовними поділами числа n на 2 та наступним збором залишків від поділу. Якщо послідовно видавалися з рівними 1,0,1,0,0,1, то двійкове зображення c дорівнює 100101. Алгоритм має вигляд