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

6

Алгоритми

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

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

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

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

2. Визначеність (детермінованість). Ця властивість означає, що кожна команда не повинна допускати двоякого тлумачення. Кожний крок алгоритму повинен бути точно визначеним.

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

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

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

6. Скінченність. Діючи за алгоритмом, виконавець одержує розв'язок задачі за скінченну кількість кроків.

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

Алгоритм описується засобами мови, зрозумілої виконавцю. Для людини - це природна мова. Комп'ютер виконує операції з багато розрядними числами у двійковій системі числення, тобто мовою комп'ютера є подвійність кодів із нулів і одиниць. Використання такої комп'ютерної мови для складання програм дуже неефективне. Записи програм, отримані таким чином, виявляються дуже докладними та громіздкими, процес розробки програм - програмування - складним і трудомістким. Тому для створення програм використовуються спеціальні мови - так звані мови програмування. Мова програмування дозволяє записувати команди в такій формі, щоб їх можна було замінити на машинні коди. Це перетворення автоматично здійснюється за допомогою спеціальних програм-перекладачів, які називаються трансляторами. Транслятори є складовою частиною системного програмного забезпечення комп'ютера. Чим досконалішими стають комп'ютери, тим більше мови програмування за своїми властивостями наближаються до природної мови людини.

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

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

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

Програми з розгалуженням

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

Умовному оператору відповідають дві структури. Неповна форма умовного оператора: дія здійснюється тільки тоді, коли виконується умова, у разі невиконання умови відбувається перехід до наступного оператора (вихід із структури). Повна форма умовного оператора: при виконанні умови (вихід «+») виконується одна дія, при невиконанні (вихід «-») - інша дія. Кожна структура має один вихід і один вхід. Програму рекомендується будувати з послідовних, логічно завершених блоків. При цьому не допускається передача управління між блоками інакше як через вихід з одного блока та через вхід до іншого. У побудованій таким чином програмі буде менше помилок при розробці і її легше перевіряти на правильність виконання.

Неповний умовний оператор має вигляд

If умова then оператор;

Повний умовний оператор записується у вигляді

if умова then оператор_1 else оператор_2;

Якщо після слів then і else треба записати не один оператор, а кілька, тоді ці оператори беруться в так звані операторні дужки: відкриваюча дужка - begin, і закриваюча - end:

begin

{оператори}

end;

Перед словом else крапка з комою не ставиться. Кожну пару begin…end записують в одному стовпці: так легше перевірити наявність для кожної відкриваючої операторної дужки відповідної закриваючої.

Приклад умовного оператора:

if a<b then y:=x;

if x<0 then x:=-x; {зміна знака змінної х}

if a+b<c then

begin

z:=x; {обмін значеннями змінних х і у}

x:=y;

y:=z

end;

В умовному операторі може бути інший умовний оператор. Наприклад:

If sqr(x)+sqr(y)>1 then

If x >y then z:=0

else z:=1;

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

Список використаної

1. Верлань А.Ф., Апатова Н.В. Інформатика 10 - 11 клас. - Київ, - 2000.