ОснАлгор_Посібн_Яровенко

4.4. ІНСТРУМЕНТАЛЬНІ ЗАСОБИ СТВОРЕННЯ БЛОК-СХЕМ.

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

Окреме місце займають спеціалізовані програмні засоби створення блоксхем алгоритмів. Серед їх великого розмаїття відзначимо наступні: Dia (проект вільного програмного забезпечення Gnome – http://live.gnome.org/Dia), FCEditor.NET (http://fceditor.com), DiagramDesigner (проект MeeSoft – http://meesoft.com), Microsoft Visio, yEdGraphEditor (компанія yWorks – http://www.yworks.com/en/index.html).

4.5.БАЗОВІ СТРУКТУРИ АЛГОРИТМУ

Впрограмуванні відома теорема італійських математиків Корадо Бома (Corrado Böhm) и Джузеппе Якопіні (Giuseppe Jacopini), сформульована і доведена в 1966 році (Bohm Corrado and Giuseppe Jacopini. «Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules». Communications of the ACM,V.9, May 1966, p. 366–371). про те, що будь-який виконуваний алгоритм може бути перетворений до структурованого виду, в якому хід його виконання визначається тільки трьома керуючими структурами – послідовною

(слідування), розгалуження і повторення або циклу.

Ця теорема лежить в основі методології структурного програмування, основні положення якої в 1970-х роках розробили видатні вчені в області інформатики і теорії програмування, лауреати премії Тюрінга – нідерландець Е.Дейкстра (Edsger Wybe Dijkstra), швейцарець Н.Вірт (Niklaus Wirth) та англієць Ч.Хоар (Charles Antony Richard Hoare).

Згідно з цією методологією:

1.Будь-яка програма є структурою, створеною на основі трьох базових структур (конструкцій):

послідовне виконання – однократне виконання операцій в тому порядку,

вякому вони записані в тексті програми;

розгалуження - однократне виконання одної з двох чи декількох операцій

взалежності від виконання певної заданої умови;

цикл – многократне виконання операції доти, доки виконується задана умова продовження циклу.

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

Кожна конструкція являє собою блок із одним входом і одним або кількома виходами.

Блок Слідування передбачає лінійне виконання операторів програми.

81

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

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

if (єдиний вибір)

if...else (подвійний вибір)

switch або case (множинний вибір)

Усі три структури при бажанні можна звести до однієї типу if. Блок Повторення реалізується одним із трьох способів:

структура while…do (повторення з передумовою);

структура repeat…until (повторення з післяумовою);

структура for (задана кількість повторень).

Усі три структури можна звести до структури while…do. Структурована програма складається із вищеназваних блоків за двома

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

2.Фрагменти програми, які повторюються (або не повторюються, але є логічно цілісними обчислювальними блоками) можуть оформлятися у виді підпрограм (процедур чи функцій).

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

3.Розробка програми здійснюється покроково, методом «згори донизу».

Спочатку записується текст основної програми, в якому, замість кожного

логічно зв’язного фрагмента тексту, вставляється виклик підпрограми, яка виконуватиме цей фрагмент. Замість справжніх працюючих підпрограм, в програму вставляються «заглушки», які нічого не роблять. Отримана програма перевіряється і відлагоджується. Після того, як програміст переконався, що підпрограми викликаються в правильній послідовності (тобто загальна структура програми вірна), підпрограми-заглушки послідовно заміняються на реально працюючі, причому розробка кожної підпрограми здійснюється тим же методом, що й основної програми. Розробка закінчується тоді, коли не залишиться ні однієї «заглушки». Така послідовність гарантує, що на кожному етапі розробки програміст одночасно має в полі зору зрозумілу йому множину фрагментів і може бути впевненим, що загальна структура всіх більш високих рівнів програми вірна. При супроводі та внесенні змін в програму виясняється, в які саме процедури потрібно внести зміни, і вони вносяться, не зачіпаючи ті частини програми, які не зв’язані безпосередньо з ними. Це дозволяє гарантувати, що при внесені змін і виправленні помилок не вийде з ладу та частина програми, яка знаходиться в даний момент поза зоною уваги програміста.

Таким чином, структуровані програми містять всього сім типів керуючих структур, які з'єднуються всього двома способами.

82

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

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

Приклад блок-схеми лінійного алгоритму приведений на рис.24.

1

Початок

2

Введення

даних

3

Операція

4

Виведення

даних

Зупинка

Рис.24. Блок-схема лінійного алгоритму.

Означення. Обчислювальний процес (алгоритм) називається лінійним,

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

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

Означення. Обчислювальний процес (алгоритм) називається

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

Розгалужені алгоритми містять крім структури слідування ще одну базову керуючу структуру – вибору. Умовою вибору напряму обчислень може бути будь-який вираз логічного типу, результатом обчислення якого є true (істина) або false (хибність).

На рис. 25.а) та 25.б) приведені блок-схеми структур єдиного та подвійного вибору відповідно, а на рис.26 – блок-схема множинного вибору.

83

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Умова false		true	Умова false
true		Операція 1
				Операція 2
Операція

а)

б)

Рис.25. Блок-схеми структур вибору:

Початок

Введення

даних

Аналіз			false
ознаки
true
			Операція 1
			Операція 2
			…
			Операція n

Виведення

даних

Зупинка

Рис. 26. Блок-схема розгалуженого алгоритму із структурою множинного вибору.

84

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Означення. Циклом називається послідовність операцій (дій), що неодноразово повторюється.

Означення. Обчислювальний процес (алгоритм), який містить цикл,

називається циклічним.

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

В загальному випадку відомий інтервал допустимих значень параметру циклу:

пз ≤ пц ≤ кз,

де пц – параметр циклу (лічильник, керуюча змінна); пз, кз – початкове та кінцеве значення параметру циклу відповідно.

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

Число повторень циклу визначається за формулою:

N = (кз - пз)/кц + 1,

де кц – значення кроку циклу.

Поточне значення параметру циклу обчислюється за формулою:

пц = пз + (k - 1) кц,

де k змінюється від 1 до N.

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

кц = (кз - пз) / ( N-1).

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

Наприклад,

пц = пц + кц.

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

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

ініціалізація (підготовка) циклу – задання початкових значень параметрів циклу (І);

виконання обчислень – тіло циклу (Т);

модифікація параметрів циклу – зміна значень параметрів циклу (М);

перевірка умови закінчення циклу (У).

85

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

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

Ітераційні цикли.

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

Розрізняють два види ітераційних циклів – цикл з передумовою та цикл з післяумовою (постумовою). Назва виду циклу визначає розташування умови виходу з циклу відносно тіла циклу. В загальному випадку умовою виходу з циклу може бути будь-який вираз логічного типу, тобто, вираз, який приймає одне з двох значень – «true» (істина) чи «false» (хибність). Результат обчислення цього виразу (перевірки умови) визначає напрям подальших обчислень і вказується на блок-схемах.

У циклі з передумовою (рис. 27) спочатку перевіряється умова і, якщо умова виконується (логічний вираз приймає значення «true»), то виконується тіло циклу. Потім знову перевіряється умова і т. д. Виконання циклу припиняється, коли умова перестає виконуватися (логічний вираз приймає значення «false»).

Початок

І

false

пз, кз,кц

У

true

пц = пз

Т

(або пц = кз)

М

false

пц ≤ кз

а)

(пц ≥ пз)

true

Тіло циклу

Результат

пц = пц + кц

(або пц = пц - кц)

Рис. 27. а) блок-схема циклу з передумовою;

б) блок-схема алгоритму з циклом з передумовою.

Зупинка

86

б)

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

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

«false»).

При організації ітераційних циклів необхідно забезпечити обов'язкове виконання умови виходу з циклу, тобто, збіжність ітераційного процесу. Для цього необхідно забезпечити вплив хоча б однієї з операцій тіла циклу на значення умови (повинна змінюватись хоча б одна змінна, яка входить в умову і виконує роль параметра циклу). В противному випадку відбудеться «зациклення» – цикл буде виконуватись нескінченно.

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

				Початок
	І
				пз, кз, кц
	Т
	М			пц = пз
				(або пц = кз)
	У		true
				Тіло циклу
false
				Результат
	а)
				пц = пц+кц
				(або пц=пц - кц)

false	пц > кз
	(пц < пз)
	true
	Зупинка
	б)

Рис. 28. а) блок-схема циклу з післяумовою; б) блок-схема алгоритму з циклом з післяумовою.

87

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Регулярні цикли.

Регулярні цикли називають також циклами з лічильником. В регулярних циклах крок циклу строго постійний і рівний ±1. Тобто, лічильник числа повторень (пц) змінюється автоматично на ±1: від початкового значення (пз) до кінцевого (кз) з кроком кц=1, або ж від кінцевого значення (кз) до початкового (пз) з кроком кц=-1. Тому в тілі регулярного циклу не дозволяється змінювати значення лічильника циклу. Початкове значення лічильника циклу обчислюється один раз до входу в цикл і одразу перевіряється умова продовження обчислень (пц≤кз або пц≥пз). Якщо умова не виконується, то тіло регулярного циклу не виконається жодного разу. Умовою закінчення регулярного циклу є досягнення лічильником циклу свого кінцевого (або початкового) значення. Відзначимо, що в мові Pascal (Turbo Pascal, PascalABC) регулярні цикли реалізовані як цикли з передумовою, тобто їх можна представити у вигляді структури while…do. Блок-схеми алгоритмів з регулярним циклом приведені на рис.29.

	Початок					І
							false
	N (пз, кз)					У
						true
						Т
	пц = пз
			false			М
	пц≤кз
						б)
	true
	Тіло циклу
						пц = пз; кз; кц
пц = пц + кц
						Т
	Результат
						Результат
	Зупинка
	а)						в)

Рис. 29. а) блок-схема алгоритму з регулярним циклом; б), в) – блок-схеми регулярної циклічної структури.

88

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

ЛАБОРАТОРНА РОБОТА № 1.

Тема: Визначення та аналіз вимог до програмного продукту.

Мета: Освоїти процес розробки програмного продукту, визначити і засвоїти зміст його етапів; навчитись визначати, формувати, аналізувати та специфікувати вимоги до програмного продукту.

Завдання:

1.Визначити, проаналізувати та специфікувати вимоги до майбутньої програми розв’язування навчальної задачі за заданим варіантом.

2.Відповісти на контрольні запитання.

3.Підготувати звіт з лабораторної роботи.

Звіт з лабораторної роботи має містити специфікації вимог до програми майбутньої розв’язування задачі та відповіді на контрольні запитання.

КОНТРОЛЬНІ ЗАПИТАННЯ.

1.Що таке «програмний продукт» (програмний засіб)?

2.Чому, на Вашу думку, необхідна програмна документація?

3.Приведіть приклад (можливо, з власного досвіду) помилок в проектуванні будь-якого об’єкту та їх наслідки.

4.Чому, на Вашу думку, вимоги до ПЗ регламентуються стандартами?

5.Які з вимог рекомендованої класифікації вимог Ви віднесете до функціональних? Чому?

6.Які з вимог рекомендованої класифікації вимог Ви віднесете до вимог користувачів? Чому?

7.Які з вимог рекомендованої класифікації вимог Ви віднесете до системних? Чому?

8.Як Ви розумієте здійсненність вимоги до ПП? Приведіть приклади нездійсненних вимог.

9.Приведіть приклади суперечливих вимог до ПП

10.Які, на Вашу думку, характеристики та атрибути якості мають бути реалізовані в навчальних програмах лабораторного курсу? Чому?

ВАРІАНТИ ЗАВДАНЬ.

1.Автоматизувати облік автомобілів в автосалоні.

2.Автоматизувати облік клієнтів ательє (за вказівкою викладача чи вибором студента).

3.Автоматизувати облік читачів бібліотеки.

4.Автоматизувати облік абонентів оператора мобільного зв’язку.

5.Автоматизувати облік абонентів провайдера (постачальника послуг з доступу до Internet).

6.Автоматизувати облік ПЗ в комп’ютерному класі навчального закладу.

7.Автоматизувати облік навчально-методичної літератури в комп’ютерному класі навчального закладу.

8.Автоматизувати облік навчально-методичної літератури в шкільному кабінеті математики.

89

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

9.Автоматизувати облік приладів в шкільному кабінеті фізики.

10.Автоматизувати облік пацієнтів медичного закладу (реєстратура).

11.Автоматизувати облік спортсменів спортклубу.

12.Автоматизувати облік слухачів підготовчих курсів університету.

13.Автоматизувати облік книг в бібліотеці.

14.Автоматизувати облік комп’ютерів в навчальному закладі.

15.Автоматизувати облік транспортних засобів підприємства.

16.Обчислити корені квадратного рівняння.

17.Обчислити площу правильного n–кутника.

18.Обчислити площу трикутника за координатами його вершин.

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

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

21.Обчислити час і дальність польоту снаряду, випущеного із заданою швидкістю під заданим кутом до горизонту.

22.Визначити час, за який пролетить задану відстань тіло, кинуте вертикально вгору із заданою швидкістю.

23.Обчислити периметр і площу правильного шестикутника, вписаного в коло заданого радіусу.

24.Обчислити довжину більшої частини відрізку, який заданий координатами своїх кінців і ділиться у заданому відношенні n1 : n2.

25.Обчислити довжину ломаної з n ланок за заданими координатами вершин.

26.Визначити радіуси вписаного та описаного кіл за заданими довжинами сторін трикутника.

27.Визначити довжини висот (медіан, бісектрис) трикутника за заданими довжинами його сторін.

28.Розв’язати систему двох лінійних алгебричних рівнянь.

29.Обчислити площу трикутника за довжинами його сторін.

30.Обчислити площу ромбу за заданим радіусом вписаного в нього кола.

31.Стиснути текстовий документ.

32.Реставрувати стару фотографію.

33.Перевести дані з паперового носія в електронний формат.

90

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)