Материал: Лекція 2. Способи запису алгоритмів

25

Модуль 1. Алгоритми і абстрактні структури даних Лекція 2. Способи запису алгоритмів

План

2.1. Способи запису алгоритмів

2.2. Базові конструкції структурного програмування

2.3. Прості алгоритми. Обчислення n! і чисел Фібоначчі (нерекурсивні алгоритми)

2.4. Алгоритм Ератосфена пошуку простих чисел

2.5. Алгоритм знаходження найбільшого спільного дільника двох чисел (алгоритм Евкліда).

2.5. Очислення часу виконання програми

2.1. Способи запису алгоритмів

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

Історично на практиці склалися наступні найбільш поширені форми запису алгоритмів:

• словесна (записи природною мовою);

• графічна (зображення з графічних символів);

• алгоритмічна (псевдокод) (напівформалізований опис алгоритмів на умовній алгоритмічній мові, що включає до себе, як елементи мови програмування, так і фрази природної мови, загальноприйняті математичні позначення тощо);

• програмна (тексти на мовах програмування).

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

Алгоритмічна форма запису алгоритму передбачає застосування певної напівформальної мови (псевдокоду). Ця форма запису мала важливе значення у минулому, коли основними мовами програмування були машинні мови та асемблер. В наш час мови програмування є достатньо високорівневими для розуміння опису алгоритму.

Отже, на теперішній час найбільш вживаними є графічний і програмний способи запису алгоритмів.

Графічний спосіб запису алгоритмів.

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

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

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

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

У таблиці 1. наведені найбільш часто вживані символи.

Назва символу	Позначення і приклад заповнення	Пояснення
Процес		Обчислювальна дія або послідовність дій
Рішення		Перевірка умов
Модифікація		Початок циклу
Визначений процес		Обчислення по підпрограмі, стандартній підпрограмі
Уведення-виведення		Уведення-виведення в загальному вигляді
Запуск-зупинення		Початок, кінець алгоритму, вхід і вихід в підпрограму
Документ		Друк результатів

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

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

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

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

Для прикладу наведемо блок-схему алгоритму знаходження максимального з двох чисел:

Рис. 2.1. Приклад блок-схеми знаходження найбільшого з двох чисел

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

Таким чином…

Блок-схема є формою подання алгоритму рішення задач у загальному виді.

Переваги цього методу зводяться до наступного:

1. Забезпечується обмін методами рішення між фахівцями, що використовують різні мови програмування.

2. Полегшується робота зі складання програми, тому що є загальний опис усього процесу рішення задачі.

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

4. Полегшується читання й розуміння програм.

5. Зменшується кількість помилок при програмуванні.

6. Спрощується перевірка й відлагодження готових програм.

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

Ще одним недоліком блок-схем є складність опису достатньо великого і складного алгоритму.

Для прискорення процесу перекладу алгоритмів задач із мови алгоритмічної системи в мову машини були розроблені спеціальні алгоритмічні системи, що одержали назву алгоритмічні мови програмування.

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

Алгоритмічні мови програмування – можна розглядати як один із способів формального запису алгоритму. Одні і ті самі алгоритми можна реалізувати на різних мовах програмування.

Наприклад, наведемо запис наведеного вище алгоритму знаходження максимального з двох чисел.

int x, y, max;

x = int.Parse(Console.ReadLine());

y = int.Parse(Console.ReadLine());

if (x > y)

max = x;

else

max = y;

Console.WriteLine("max= " + max);

Словесна форма запису алгоритму

Нарешті, цей самий алгоритм можна записати у словесній формі:

Крок 1. визначити змінні цілого типу: x,y,max;

Крок 2. Ввести числа і призначити їх змінним x,y;

Крок 3. Якщо x>y то перейти до кроку 4, інакше до кроку 5;

Крок 4. Призначити змінній max = x. Перейти до кроку 6.

Крок 5. Призначити змінній max = y;

Крок 6. Вивести значення змінної max.

2.2. Базові конструкції структурного програмування

При програмному способі запису алгоритму важливо дотримуватися не лише синтаксису мови програмування, але і прагнути зберегти чітку структуру і зрозумілість програми. Для цього у 80-х роках 20-го століття було запропоновано технологію структурного програмування.

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

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

Послідовністю називається конструкція, що реалізовує послідовне виконання двох або більше операторів (простих або складних).

Розгалуження задає виконання того чи іншого оператора залежно від виконання якої-небудь умови. Реалізується за допомогою операторів if та switch.

Цикл реалізує багатократне виконання операторів. Реалізується за допомогою операторів циклу.

Рис. 2.2. Базові конструкції структурного програмування

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

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

У мовах об’єктно-орієнтованого програмування (C#, Java) ідеї структурного програмування використовуються на найнижчому рівні — при написанні методів класу.

2.3. Прості алгоритми. Обчислення n! і чисел Фібоначчі (нерекурсивні алгоритми)

Розглянемо різні форми запису алгоритмів на прикладі простих задач.

2.3.1. Знаходження факторіала цілого числа

Постановка задачі:

Обчислити факторіал n! де

, де

Приклад. Для n=5, n!=1*2*3*4*5

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

Крок 1. Оголосити змінні: n – кількість членів ряду (ціле), fact – обчислене значення факторіалу (довге ціле), i – змінна циклу (ціле).

Крок 2. Ввести число членів ряду і призначити його змінній n, призначити fact =1.

Крок 3. Цикл. Починаючи з елементу i=2 до n

fact := fact * i

Крок 4. Вивести результат на консоль

Реалізація алгоритму на мові C#.

static void Main(string[] args)

{

long fact=1;

int n = int.Parse(Console.ReadLine());

for (int i = 2; i <= n; i++)

fact *= i;

Console.WriteLine("fact= " + fact);

Console.ReadKey();

}

2.3.2. Знаходження чисел Фібоначчі

Постановка задачі: Обчислити вказану кількість чисел Фібоначчі.

Обчислення чисел Фібоначчі задається формулами:

F(1)=1,F(2)=1;F(3)=2, F(n+1)=F(n)+F(n-1)

Таким чином, це послідовність чисел, у якій кожне наступне число дорівнює сумі двох попередніх чисел. Назва ряду чисел походить від імені середньовічного математика Леонардо Пізанського (відомого як Фібоначчі).

Приклад:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946

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

Крок 1. Оголосити змінні:

n - кількість елементів ряду;

a, b - значення двох перших елементів ряду;

c - буферна змінна;

i - лічильник.

Крок 2. Ввести значення n з консолі

Крок 3. Призначити a і b значення 1 і 1 відповідно (це перші числа ряду Фібоначчі). Вивести їх на екран.

Крок 4. Цикл. Починаючи з 3-го елементу до n

- виводити на екран суму a і b

- зберегти значення змінної b в c

- записати в b суму a і b,

- призначити a значення с.

Реалізація алгоритму на мові C#

static void Main(string[] args)

{

int a = 1;

int b = 1;

int c = 0;

Console.WriteLine("Введіть кількість чисел послідовності");

int n = int.Parse(Console.ReadLine());

Console.WriteLine("Перше число = " + a);

Console.WriteLine("Друге число = " + b);

for (int i = 2; i < n; i++)

{

c = a + b;

Console.WriteLine("Наступний член ряду= " + c);

a = b;

b = c;

}

Console.ReadKey();

}