Алгоритмизация

МІНІСТЕРСТВО АГРОПРОМИСЛОВОГО КОМПЛЕКСУ УКРАЇНИ

Головне управління кадрового забезпечення і аграрної освіти Управління аграрної освіти

Алгоритми та алгоритмізація

Методичні вказівки для вивчення курсів «Компютерна техніка та програмування» та «Основи інформатики та обчислювальної техніки» очної та заочної форм навчання

Харків 1998

Автори – укладачі:

В.О. Романов, кандидат фізико-математичних наук, доцент; І.В. Сергєєва, асистент ( Харківський державний технічний університет сільського господарства)

Рецензенти:

С.В. Трубников, професор (Харківський державний університет); І.О. Фурман, професор (Харківський державний технічний університет сільського господарства)

Схвалено і рекомендовано до видання Радою Навчально-методичного центру по заочній формі навчання у закладах освіти 3-4 рівнів акредитації аграрного профілю (план видання навчально-методичної літератури на 1997-1998 н.р., рег.№:-050/98 від 22.01.1998

ЗАГАЛЬНІ ВКАЗІВКИ

Широке розповсюдження персональних комп’ютерів і їх проникнення в усі галузі людської діяльності обумовлює їх використання при розв’язанні багатьох актуальних задач, в тому числі інженерних і економічних. Курси «Основи обчислювальної техніки і програмування на EOM», «Основи інформатики і обчислювальної техніки», «Компютерна техніка та програмування» дають студентам загальні відомості про принципи організації і функціонуванню EOM, загальні навики роботи на персональних комп’ютерах, а також навики по розв’язанню простих інженерних та економічних задач, починаючи з складання алгоритму, побудови блок-схеми алгоритму і закінчуючи записом програми та алгоритмічній мові високого рівня, введенням програми у комп’ютери, її налагодження і получення результатів розв’язання задачі.

Дані методичні вказівки вміщують основні відомості по алгоритмізації – процесі складання алгоритму і запису алгоритму у вигляді блок-схеми. Тут же наведено приклад по розв’язанню простої задачі на EOM: складання математичної моделі, вибір алгоритму, складання блок-схеми, і т.п., до одержання результату.

1.АЛГОРИТМ ТА ЙОГО ЗАГАЛЬНІ ВЛАСТИВОСТІ

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

Наприклад, алгоритм рішення квадратного рівняння можна записати у вигляді: 1.Обчислити d = b2-4ac.

2.Якщо d<0, то перейти до кроку 5.

3.Обчислити x1 = (−b + d)/(2a).

4.Обчислити x2 = (−b − d)/(2a).

5.Закінчити обчислення.

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

Алгоритм має такі основні властивості, що розкривають його визначення:

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

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

3.Результативність (або кінцевність). Ця властивість означає, що алгоритм повинен приводити до розв’язання задачі за кінцевим числом кроків.

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

Щоб розробити алгоритм, потрібно добре уявляти собі хід розв’язування, а також можливу форму вихідних даних і результатів.

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

Розроблений алгоритм можна записати декількома способами, наприклад: - На природній мові; - У вигляді блок-схеми;

- На алгоритмічній мові (спеціальній мові для запису алгоритмів для EOM)

2.ЗАПИС АЛГОРИТМУ НА ПРИРОДНІЙ МОВІ

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

1) Крок обробки ( обчислення):

Присвоїти u = вираз.

Тут u – змінна, а вираз задає правило обчислення значення, яке буде присвоєно змінній u. Як правило, вираз – це алгебраїчний вираз.

2) Перехід до кроку з номером N:

Перейти до n. N.

Виконання алгоритму продовжується з кроку з номером N і далі. 3) Завдання початкових значень:

Введення u, t ,…

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

4) Фіксація результату обчислень:

Вивід u t,…

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

5) Початок алгоритму:

Початок.

6) Кінець виконання алгоритму:

Кінець.

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

Приклад 1. Побудувати таблицю функції f(x) на інтервалі змінної від x1 до x2 з кроком Δx. Для побудови таблиці функції на заданому інтервалі з заданим кроком можна користуватися простим алгоритмом:

1.Початок

2.Введення x1, x2 ,∆x.

3.Присвоїти x = x1

4.Присвоїти y = f (x)

5.Вивід x, y. (одержана перша графа таблиці)

6.Присвоїти x = x + ∆x.( значення х збільшується на крок)

7.Присвоїти y = f (x).

8.Вивід x, y. (одержана друга графа таблиці)

9.Присвоїти x = x + ∆x.( значення х збільшується на крок)

………………………..

N-3. Присвоїти x = x2 N-2. Присвоїти y = f (x)

N-1. Вивід x, y. (одержана остання графа таблиці)

N. Кінець

Даний алгоритм містить велике число кроків для малого випадку Δx або широкого інтервалу [x1 , x2 ], але легко бачити, що в ньому багато раз повторюються абсолютно однакові дії, наприклад, послідовності кроків 4-5-6, 7-8-9 і т.д. однакові. Тому, той самий алгоритм можна

записати ( але не виконувати) коротше, використовуючи можливість багаторазового повторення кроків:

1.Початок

2.Введення x1 , x2 ,∆x.

3.Присвоїти x = x1

4.Присвоїти y = f (x)

5.Вивід x, y.

6.Присвоїти x = x + ∆x

7.Якщо, x ≤ x2 ч то перейти до п.4

8.Кінець

Помітимо, що дана форма запису значно коротша, проте реалізує всі дії, що і попередня. Число повторень (переходів від п. 7 до п. 4) легко підрахувати як n = (x2 − x1 )/ ∆x

Приклад 2. Обчислити значення функції

		f (x), x < x0
	y =
		g(x), x ≥x0

Наведена вище формула є лише коротким записом того, що, коли x < x0 , то y = f (x),інакше (тобто коли x ≥≥ x0 ) − y = g(x). Тепер алгоритм обчислення цієї функції може бути легко записаний:

1.Початок

2.Введення x, x0 .

3.Якщо x < x0 , то перейти до п.6

4.Присвоїти y = g(x)

5.Перейти до п. 7.

6.Присвоїти y = f (x)

7.Вивід y.

8.Кінець

Тут на початку здійснюється введення значень x і x0 , а потім перевірюється умова x < x0 . Якщо ця умова дійсна (тобто x справді менше x0 ), то здійснюється перехід до п. 6, де обчислюється за

формулою (як і повинно бути за умовою), і далі до п.7 – виводу результату обчислення, і до п.8 – обчислення закінчується (у цьому випадку п. 4 і 5 алгоритму не виконуються). Якщо умова п.3 невірна , то перехід до п.7 не виконується, а здійснюється перехід до наступного пункту 4 і обчислюється за формулою f (x) (як і повинно бути за умовою для цього випадку, а потім здійснюється перехід до п. 8 – кінець. Таким чином, у цьому прикладі в залежності від умови виконується та чи інша частина алгоритму.

Приклад 3. Побудувати таблицю функції

f (x), x < x0 y = g(x), x ≥ x0

на інтервалі змінної x від x1 до x2 з кроком ∆x.

Ця складніша задача легко може бути розв’язана якщо використати результати двох попередніх прикладів. Приклад 1 дає нам алгоритм побудови таблиці будь-якої функції, при цьому значення функції обчислюється в п.4 для заданого x. У прикладі 2 одержаний потрібної алгоритм обчислення потрібної функції в довільній точці – пункти 3-6 алгоритму прикладу 2. Таким чином, для того, щоб одержати алгоритм розв’язування нашої задачі, необхідно обєднати алгоритми, тобто, замість п.4 алгоритму прикладу 1 повинні бути записані пункти 3-6 алгоритму прикладу 2. Провіривши пере нумерацію пунктів одержуємо кінцевий результат:

1.Початок

2.Введення x1 , x2 ,∆x, x0

3.	Присвоїти x = x1	4. Якщо
x < x0 , то перейти до п.7
5.	Присвоїти y = g(x)	6. Перейти
до п. 8.
7.	Присвоїти y = f (x)	8. Вивід

x, y.

9.Присвоїти x = x + ∆x

10.Якщо x ≤ x2 , то перейти до п.4.

11.Кінець

3. ЗОБРАЖЕННЯ АЛГОРИТМУ У ВИГЛЯДІ БЛОК-СХЕМИ

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

Пункт «Присвоїти» зображується прямокутником, всередині якого записується зміст присвоєння типу u=вираз

Перевірка умови зображується ромбом, всередині якого записується умова. У результаті перевірки умови здійснюється вибір одного з двох можливих переходів «ТАК» (умова виконується) і «НІ» (умова не виконується)

Введення і вивід зображуються паралелограмом (рис.1.в), всередині якого пишуться слова «введення» або «вивід» і перераховуються змінні, значення яких повинні бути введені або виведенні.

Початок і кінець алгоритму зображуються фігурою (рис.1.г.), всередині якої записуються слова «початок» або «кінець».

			так			ні
	u=вираз				умова
а )обчислит. присвоїти				б) перевірка умови

г) початок кікінець.

в) введення. вивід

Рис. 1. Елементи блок-схеми Наприклад, зобразимо блок-схему алгоритму побудови таблиці функції (див. приклад 3 з

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

Блок-схемами звичайно, користуються на проміжному етапі при написані програми на EOM. Використання схем забезпечує придбання надійних навичок розробки алгоритмів у рамках так званого структурного програмування. В офіційних документах при зображенні блок-схеми потрібно користуватися стандартами, наприклад, ДЕРЖСТ(ГОСТ) 19.003-80.

4. ОСНОВНІ СТРУКТУРИ АЛГОРИТМІВ

Основні структури алгоритмів – це обмежений набір блоків і стандартних способів їх зєднання для виконання необхідної послідовності дій. До основних структур відносять:

1. Послідовність (або лінійний алгоритм). Просте послідовне розташування кроків або блоків, що виконються один за одним (рис.3)

2. Розгалуження. Застосовується, коли в залежності від деякої умови потрібно виконати або одну, або іншу дію (рис. 4), або групи дій. На природній мові розгалуженню відповідає послідовність кроків:

		Початок
		Введення
		х1, х2 .∆х, х0
		х = х1
так			ні
		х < x0
y = f (x)				y = g(x)

Вивід х, у

х = х + ∆x

так

x ≤ x2

ні

Кінець

Рис.2. Блок-схеми алгоритму приклада 3 п 1.1.

1.Якщо умова, то йти до п.4

2.(дія)

3.Перейти до п.5

4.(дія 2)

5.…………………..

Окремим випадком розгалуження є обхід, коли одна з віток не містить ніяких дій (рис.5) Н природній мові обходу відповідає послідовність кроків

1. Якщо умова, то йти до п.4

2.(дія)

3.…………………..

3. Цикл. Застосовується при необхідності виконання якої-небудь дії декілька разів до того, поки виконується деяка умова 9рис.6) На природній мові циклу відповідає послідовність кроків:

1.(Надання початкових значень деяким змінними)

2.(Багаторазове виконання дії)

3.Якщо умова, то йти до п.2

4.………………

				так					ні
	Дія 1					Умова
	Дія 2
			Дія 1						Дія 2

............

Дія N

Рис. 3. Послідовність.

Рис.4. Розгалуження.

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

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

			так				ні
Дія					Умова

так

Умова	Дія 1

ні

Рис. 6. Цикл.

Рис. 5. Обхід

Приклад 4 Розглянемо слідуючу задачу: скласти блок-схему алгоритму для обчислення таблиці

значень функції.