Основи алгоритмізації

1.5.1 Алгоритми та їх властивості
Алгоритм - це чітко визначена для конкретного виконавця послідовність дій, які спрямовані на досягнення поставленої мети або розв'язання задачі певного типу.
У 820 році нашої ери в Бухарі був написаний підручник "Аль-Джабр Ва-аль-Мукабала" ("Наука виключення скорочення"), в якому були описані правила виконання чотирьох арифметичних дій над числами в десятковій системі числення. Автором підручника був арабський математик Мухаммед Бен Муса аль-Хорезмі. Від слова "альджебр" у назві підручника пішло слово "алгебра", а від імені аль-Хорезмі - слово "алгоризм", що пізніше перейшло в слово "алгоритм".
Властивості алгоритмів:
1. Зрозумілість. В алгоритмі повинні бути лише операції, які знайомі виконавцеві. При цьому виконавцем алгоритму може бути: людина, комп'ютер, робот тощо.
2. Масовість. За допомогою складеного алгоритму повинен розв'язуватися цілий клас задач.
3. Однозначність. Будь-який алгоритм повинен бути описаний так, щоб при його виконанні у виконавця не виникало двозначних вказівок. Тобто різні виконавці згідно з алгоритмом повинні діяти однаково та прийти до одного й того ж результату.
4. Правильність. Виконання алгоритму повинно давати правильні результати.
5. Скінченність. Завершення роботи алгоритму повинно здійснюється в цілому за скінченну кількість кроків.
6. Дискретність. Алгоритм повинен складатися з окремих завершених операцій, які виконуються послідовно.
7. Ефективність. Алгоритм повинен забезпечувати розв'язання задачі за мінімальний час з мінімальними витратами оперативної пам'яті.
Способи представлення алгоритмів. Алгоритми можуть бути представлені: у вигляді таблиці, описані як система словесних правил (лексикографічний або словеснокроковий спосіб запису алгоритму), представлені алгоритмічною мовою у вигляді послідовності операторів (операторний спосіб), або з допомогою графічного зображення у формі блок-схем (графічний або геометричний спосіб запису алгоритму).
Слід зауважити, що графічному способу подання алгоритмів надається перевага через його простоту, наочність і зручність. Блок-схема алгоритму зображає послідовність блоків, з'єднаних між собою стрілками, які вказують послідовність виконання і зв'язок між блоками. Всередині блоків записується їх короткий зміст.

1.5.2 Блок-схеми
Блок-схема - це спосіб представлення алгоритму в графічній формі, у вигляді геометричних фігур, сполучених між собою лініями (стрілками). Форма блока визначає тип дії, а текст всередині блоку дає детальне пояснення конкретної дії. Стрілки на лініях, що сполучають блоки схеми, вказують послідовність виконання команд, передбачених алгоритмом. Блок-схеми, за рахунок наочності спрощують створення ефективних алгоритмів, розуміння роботи вже створених, а як наслідок і їх оптимізацію. Існуючі стандарти на типи блоків дозволяють легко адаптувати алгоритми, створені у вигляді блок-схем до будь-яких існуючих на сьогоднішній день мов програмування.
Зображення блоків у алгоритмі, їх розміри, товщина ліній, кут нахилу ліній тощо, регламентуються Державним стандартом "Схеми алгоритмів, програм, даних і систем", а саме: 19.701-90 (ISO 5807-85).
Блоки у блок-схемі з'єднуються лініями потоків. У кожен блок може входити не менше однієї лінії, з блоку ж (окрім логічного) може виходити лише одна лінія потоку. З логічного блоку завжди виходять дві лінії потоку: одна у випадку виконання умови, інша - при її невиконанні. Бажано, щоб лінії потоку не перетинались.
Алгоритм може бути детальним, або спрощеним (деякі зрозумілі блоки можуть не записуватись, інакше алгоритм збільшується в розмірі).
Основні види блок-схем:
• прості (нерозгалужені);
• розгалужені;
• циклічні;
• з підпрограмами;
• змішані.

Рис. 1.2. Основні елементи блок-схем

1.5.3 Базові алгоритмічні конструкції
Базові алгоритмічні конструкції - це способи управління процесами обробки даних. Виділяють три базові алгоритмічні конструкції:
1. лінійні алгоритми;
2. алгоритми розгалуженої структури;
3. алгоритми циклічної структури.

Лінійні алгоритми (рис. 1.3). Алгоритм називається лінійним, якщо блоки алгоритму виконуються один за одним. Алгоритми лінійної структури не містять умовних і безумовних переходів, циклів.
Алгоритми розгалуженої структури (рис.1.4). Якщо вибраний метод розв'язання задачі передбачає виконання різних дій в залежності від значень будь-яких змінних, але при цьому кожна гілка алгоритму в процесі розв'язання задачі виконується не більше одного разу, алгоритм називається розгалуженим.
Алгоритми циклічної структури (рис.1.5).
Цикл - це команда виконавцеві (компілятору) багаторазово повторити послідовність певних команд.
При багатократному проходженні деяких ділянок алгоритму в процесі виконання алгоритм називається циклічним. Кількість проходжень циклу повинна бути повністю визначена алгоритмом розв'язання задачі, інакше виникає "зациклювання", при якому процес розв'язання задачі не може завершитися.
Алгоритми розв'язку задач циклічної структури можуть бути такими, що при однократному проході циклу деякі ділянки алгоритму виконуються неодноразово, тобто всередині циклу існують інші цикли. Алгоритми такої структури називаються алгоритмами з вкладеними циклами.

Тепер перейдемо до запису алгоритмів програм безпосередньо мовою програмування Сі.
Оператори - це основні елементи, з яких "будуються" програми на будь-якій мові програмування. Більшість операторів складаються з виразів. Виходячи з цього, спочатку розглянемо вирази.
Вираз представляє собою об'єднання операцій і операндів. Найпростіший вираз складається з одного операнду.
Приклади виразів:
5
-7
10+21
a*(b+d*1)-1
x=++a%3
a>3

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

-5+7
1<2
6+(a=1+2)
a=1+2

Як вже було сказано, основу будь-якої програми складають оператори. Оператором-виразом називається вираз, вслід за яким стоїть крапка з комою. Взагалі усі оператори можна згрупувати у наступні класи:
• оператори присвоювання;
• виклики функцій;
• розгалуження;
• цикли.
Проте, оператори найчастіше відносяться до більш ніж одного з чотирьох класів. Наприклад, оператор if (a=fn(b+c)>d) складається з представників наступних класів: присвоювання, виклик функції та розгалуження. У тому і є гнучкість Сі, що є можливість змішування в одному операторі операторів різних класів. Проте навряд чи слід цим зловживати - програма може вийти правильною, проте надто заплутаною та нечитабельною.

1.6.1 Оператор розгалуження if
Оператор розгалуження призначений для виконання тих або інших дій в залежності від істинності або хибності деякої умови. Основний оператор цього блоку в Сі - if... else не має ключового слова then, як у Паскалі, проте обов'язково вимагає, щоб умова, що перевіряється, розміщувалася б у круглих дужках. Оператор, що слідує за логічним виразом, є then- частиною оператору if...else.
Синтаксис оператора:
if (<умова>)
<оператор1>;
[else <оператор2;>]

Рис. 1.6. Синтаксис оператора if

Умова хибна, якщо вона дорівнює нулю, в інших випадках вона істинна. Це означає, що навіть від'ємні значення розглядаються як істинні. До того ж, умова, що перевіряється, повинна бути скалярною, тобто зводитися до простого значення, яке можливо перевірити на рівність нулю. Взагалі не рекомендується використання змінних типу float або double в логічних виразах перевірки умов з причини недостатньої точності подібних виразів. Більш досвідчені програмісти скорочують оператори типу:
if (вираз!=0) оператор;
до наступного:
if (вираз) оператор;
Обидва логічні вирази функціонально еквівалентні, тому що будь-яке ненульове значення розцінюється як істина. Це можна довести наступними програмами:
Приклад 1.
/* програма виводить результат ділення двох дійсних чисел */
#include<stdio.h>
#include<conio.h>
void main()
{
float a,b,c;
printf("Введiть число a:\n");
scanf("%f",&a);
printf("Введiть число b:\n");
scanf("%f",&b);
if (b==0) printf("Дiлення да нуль!\n");
else
{
c=a/b;
printf("a: b == %g",c);
};
}

Приклад 2.
/* застосування умовного розгалужування */
#include <stdio.h>
main()
{
int number;
int ok;
printf("Введіть число з інтервалу 1..100: ");
scanf("%d",&number);
ok=(1<=number) && (number<=100);
if (!ok)
printf("Не коректно!!\n");
return ok;
}
Змінній ok присвоюється значення результату виразу: ненульове значення, якщо істина, і в протилежному випадку - нуль. Умовний оператор if(!ok) перевіряє, якщо ok дорівнюватиме нулю, то!ok дасть позитивний результат й відтоді буде отримано повідомлення про некоректність, виходячи з контексту наведеного прикладу.

1.6.2 Оператор switch
Синтаксис:
switch(<вираз цілого типу>)
{
case <значення_1>:
<послідовність_операторів_1>;
break;
case <значення_2>:
<послідовність_операторів_2>;
break;
..............................................................
case <значення_n>:
<послідовність_операторів_n>;
break;
[default:
<послідовність_операторів_n+1>;]
}
Оператор-перемикач switch призначений для вибору одного з декількох альтернативних шляхів виконання програми. Виконання оператора switch починається з обчислення значення виразу (виразу, що слідує за ключовим словом switch у круглих дужках). Після цього управління передається одному з <операторів>. Оператор, що отримав управління - це той оператор, значення константи варіанту якого співпадає зі значенням виразу перемикача.
Вітка default (може опускатися, про що свідчить наявність квадратних дужок) означає, що якщо жодна з вищенаведених умов не задовольнятиметься (тобто вираз цілого типу не дорівнює жодному із значень, що позначені у саse-фрагментах), керування передається по замовчуванню в це місце програми. Треба також зазначити обов'язкове застосування оператора break у кожному з case-фрагментів (цей оператор застосовують для негайного припинення виконання операторів while, do, for, switch), що негайно передасть керування у точку програми, що слідує відразу за останнім оператором у switch-блоці.
Приклад 1:
switch(i)
{
case -1:
n++;
break;
case 0:
z++;
break;
case 1:
p++;
break;
}

Приклад 2:
switch(c)
{
case 'A':
capa++;
case 'a':
lettera++;
default:
total++;
}
В останньому прикладі всі три оператори в тілі оператора switch будуть виконані, якщо значення с рівне 'A', далі оператори виконуються в порядку їх слідування в тілі, так як відсутні break.

1.6.3 Оператор циклу з передумовою while
Оператор while використовується для організації циклічного виконання оператора або серії операторів, поки виконується певна умова.
Синтаксис:
while (<логічний вираз>)
оператор;

Рис. 1.7. Синтаксис оператора while

Цикл закінчується у наступних випадках:
1. умовний вираз у заголовку приймає нульове значення;
2. у тілі циклу досягнуто місця, де розташований оператор break;
3. у тілі циклу виконаний оператор return;
У перших двох випадках керування передається оператору, розташованому безпосередньо за циклом, у третьому випадку активна на той момент функція завершує свою роботу, повертаючи якесь значення.
Знову ж таки нерідкою помилкою програмістів, що працювали раніше на Паскалі, є використання замість оператора порівняння (==) оператора присвоювання (=). Наприклад, наступний фрагмент створить нескінчений цикл:
/* некоректне використання оператору циклу */
int main(void)
{
int j=5;
while(j=5) /* змінній j присвоїти значення 5 */
{
printf("%d\n",j);
j++;
}
}
Компілятор Сі попередить про некоректне присвоювання в даному випадку, виправити яке особливих труднощів не викличе.
Втім, часто такий цикл використовується для перевірки відповіді користувача на питання з програми ("так чи ні?"):

/* фрагмент використання while */
printf ("Підтверджуєте? Так чи ні?(y/n);");
scanf("%c",&ch);
while (ch!='y' && ch!='n')
{
printf("\n Відповідайте так чи ні.. (y/n);");
scanf("%c",&ch);
}
Тіло циклу почне виконуватися, якщо користувач введе будь-який символ, відмінний від у або n. Цикл виконується доти, доки користувач не введе або 'у', або 'n'.
Цікаво розглянути й наступний приклад, що застосовує оператор while у функції підрахунку факторіалу:
long factorial(int number)
{
long total;
total=number;
while (--number)
total*=number;
return total;
}

1.6.4 Оператор циклу з постумовою do … while
Оператор do…while використовується для організації циклічного виконання оператора або серії операторів, які називаються тілом циклу, до тих пір, поки умова не стане хибною.
Синтаксис:
do
<оператор>;
while (<логічний_вираз>);

Рис. 1.8. Синтаксис оператора do … while

Ситуації, що призводять до виходу з циклу, аналогічні наведеним для циклу while із передумовою. Характерним є те, що тіло циклу виконається хоча б один раз. На відміну від Паскаля, в якому цикл з постумовою repeat operator until умова виконується, поки умова невірна, цикл do... while навпаки припиняє виконання, коли умовний вираз обертається в нуль (стає невірним).
Приклад 1.
printf ("Підтверджуєте? Так чи ні?(y/n);");
do
scanf("%c",&ch);
while (ch!='y' && ch!='n')
Приклад 2.
#include<stdio.h>
#include<conio.h>
void main()
{
int n,i;
float fact;
printf("Програма обчислення n!.\n");
printf("Введiть число n:\n");
scanf("%d",&n);
i = 1;
fact = 1;
do {
fact *= i;
i++;
} while (i <= n);
printf("n!==%g",fact);
}

1.6.5 Оператор розриву break
Синтаксис:
break;
Оператор розриву break перериває виконання операторів do, for, while або switch.
В операторі switch він використовується для завершення блоку case.
В операторах циклу - для негайного завершення циклу, що не зв'язане з перевіркою звичайної умови завершення циклу. Коли оператор break зустрічається всередині оператора циклу, то здійснюється негайний вихід з циклу і перехід до виконання оператору, що слідує за оператором циклу.
Приклад:
main()
{
int i;
for (i=0;i<1000;i++)
{
printf("%d - %d\n",i,i*i*i);
if (i*i*i>=10000) break;
}
return 0;
}

1.6.6 Оператор продовження continue
Синтаксис:
continue;
Оператор continue передає управління на наступну ітерацію в операторах циклу do, for, while. Він може розміщуватися тільки в тілі цих операторів. В операторах do і while наступна ітерація починається з обчислення виразу умови. Для оператора for наступна ітерація починається з обчислення виразу зміни значення лічильника.
Приклад:
while (i-- > 0)
{
x=f(i);
if (x == 1) continue;
else y=x*x;
}
В даному прикладі тіло циклу while виконується якщо i більше нуля. Спочатку значення f(i) присвоюється змінній x;потім, якщо x не рівний 1, то y присвоюється значення квадрата числа х, і управління передається на "заголовок" циклу, тобто на обчислення виразу (i-- > 0). Якщо ж х рівний 1, то виконується оператор продовження continue, і виконання продовжується з "заголовку" оператора циклу while, без обчислення квадрата x.

1.6.7 Оператор циклу for
Оператор for забезпечує циклічне повторення деякого оператора певне число разів. Оператор, який повторюється називається тілом циклу. Повторення циклу звичайно здійснюється з використанням деякої змінної (лічильника), яка змінюється при кожному виконанні тіла циклу. Повторення завершується, коли лічильник досягає заданого значення.
Синтаксис оператора:
for([ініціалізація];[перевірка_умови];[нове_значення])
оператор;

Рис. 1.9. Синтаксис оператора for

Звернемо увагу на те, що кожен з трьох виразів може бути відсутнім. Перший вираз служить для ініціалізації лічильника, другий - для перевірки кінця циклу, а третій вираз - для зміни значення лічильника. Формально роботу циклу можна описати такими кроками:
1. якщо перший вираз (ініціалізація) присутній, то він обчислюється;
2. обчислюється вираз умови (якщо він присутній). Якщо умова виробляє значення 0, тобто вона невірна, цикл припиняється, у протилежному випадку він буде продовжений;
3. виконується тіло циклу;
4. якщо присутній вираз зміни лічильника, то він обчислюється;
5. надалі перехід до пункту під номером 2.
Поява у будь-якому місці циклу оператора continue призведе до негайного переходу до пункту 4.
Приклад використання циклу for:
/* друк парних чисел у проміжку від 500 до 0 */
#include <stdio.h>
void main(void)
{
long i;
for(i=500;i>=0;i-=2)
printf("\n%ld",i);
printf("\n");
}
Для того, щоб продемонструвати гнучкість даного різновиду циклу, розглянемо інші варіанти цієї ж програми. У першому випадку представимо весь перелік обчислень лише в одному операторі for, за яким слідує порожній оператор:

#include <stdio.h>
int main(void)
{
long i;
for(i=500;i>=0;printf("\n%ld",i),i-=2);
}
Другий варіант використовує оператор continue:
#include <stdio.h>
int main(void)
{
long i;
for(i=500;i>=0;i--)
if (i%2 == 1)
continue;
else
printf("\n %ld", i);
printf("\n");
}
Справа програміста, який з варіантів обрати - надати перевагу більш стислому викладанню або навіть взагалі скористатися іншим оператором. Цікаво, що різновид циклу for можна звести до циклу while наступним чином:
for(вираз1;вираз2;вираз3)
оператор;

/* далі - аналогічний цикл while */
вираз1;
while (вираз2)
{
оператор;
вираз3;
}
Інша справа - чи є в такій заміні необхідність? Не завжди гнучкість переважає стислість та навпаки. Справа за конкретною ситуацією. Зрештою, вибір циклу може бути й справою смаку конкретного програміста - саме йому вирішувати, які оператори застосувати для вірного запису того чи іншого алгоритму.

1.6.8 Оператор переходу goto
Синтаксис:
goto <мітка>;
/*... */
<мітка>: <оператор>;
Оператор безумовного переходу goto передає управління безпосередньо на <оператор>, перед яким розташована <мітка>. Область дії мітки обмежена функцією, в якій вона визначена. Тому, кожна мітка повинна бути відмінною від інших в одній і тій самій функції. Також, неможливо передати управління оператором goto в іншу функцію.
Оператор, перед яким розташована <мітка> виконується зразу після виконання оператора goto.
Якщо оператор з міткою відсутній, то компілятор видасть повідомлення про помилку.
Приклад використання goto:
if (errorcode>0)
goto exit;
…
exit:
return errorcode;
В свою чергу при появі концепції структурного програмування оператор goto піддався критиці, і його використання стало розглядатися як ознака поганого стилю програмування. Дійсно, надмірно широке використання goto робить структуру програми надмірно заплутаною, тому без особливої необхідності намагайтесь обходитися без оператора goto.

1.6.9 "Порожній" оператор
Синтаксис:
;
Порожній оператор - це оператор що складається лише з крапки з комою. Він може використовуватися в будь-якому місці програми, де за синтаксисом потрібний оператор.
for (i=0;i<10;printf("%d\n",i););

1.6.10 "Складений" оператор
"Складений" оператор представляє собою два або більше операторів. Його також називають "блоком".
Синтаксис:
{
[<оператори>]
}
Дія складеного оператора полягає в обов'язковому послідовному виконанні операторів, які містяться між { та }, за виключенням тих випадків, коли який-небудь оператор явно не передасть управління в інше місце програми.
if (i>0)
{
printf("i == %d\n",i);
i--;
}

Дата добавления: 2014-01-07