І. Алгоритъм - понятие, свойства, представяне.

 

1. Понятие

 

Алгоритъм представлява всяко точно и еднозначно описана крайна последователност от действия над определени входни данни, която винаги води до резултат, който е във функционална зависимост от стойностите на входните данни.

Ако така описаната последователност завършва не винаги, а само за определена област от стойности на входните данни, такъв алгоритъм се нарича частичен алгоритъм или процедура.

 

2. Свойства на алгоритмите

 

  1. Дискретност – всеки алгоритъм трябва да се състои от отделни, разграничени по време една от друга стъпки, всяка от които се извършва за крайно време.
  2. Детерминираност – Резултатът от действията върху данните и посочването на следващото стъпка трябва да бъдат еднозначно определени от действията, извършвани в текущия момент.
  3. Масовост – процедурата трябва да дава резултат на за краен брой съчетания на входните данни, а за едно потенциално безкрайно множество от входни данни.
  4. Резултатност – процедурата трябва винаги да дава резултат, ако входните данни принадлежат на допустимото подмножество.
  5. Крайност – процедурата трябва да завършва с резултат за краен брой стъпки.

 

Пример: Алгоритъм на Евклид за намиране на най-големият общ делител на две цели положителни числа p и q.

Описание:

Входни данни: p и q, p>0 и q>0;

Резултат: да се намери най-големият общ делител на p и q;

Процедура:

стъпка1: r = остатъка от p/q;

стъпка2: Ако r = 0, се предполага, че делителя е равен на q и край. В противен случай p = q, q = r и се преминава към стъпка1.

 

3. Видове алгоритми

 

Според последователността на действията, които се изпълняват алгоритмите биват:

1.      Линейни – характеризират се с последователен ред на изпълнение на действията, който винаги е един и същ, независимо от набора данни, за които се прилага.

 

Пример: Да се определи обиколката на триъгълник със страни a, b и c.

Входни данни: a, b и c, a>0, b>0, c>0;

Резултат: P – обиколка;

Процедура:

стъпка1: задава се стойност за a;

стъпка2: задава се стойност за b;

стъпка3: задава се стойност за c;

стъпка4: P = a+b+c;

 

  1. Разклонени – В практиката често присъстват ситуации, при които трябва да се вземе решение и да се изпълни едно или друго действие. За да се отразява по-точно действителността и да се описва се налага въвеждането на разклонени алгоритми. Разклонението дава възможност да се избере една от две възможности за продължаване на изчислителния процес.

 

Пример: Деление на две числа x и y.

Величини: x, y;

Резултат: z;

Действия:

стъпка1: задава се стойност за x;

стъпка2: задава се стойност за y;

стъпка3: Ако y = 0 делението е невъзможно. В противен случай z = x/y.

 

  1. Циклични – Тези при които една стъпка или група от стъпки се изпълняват многократно.

 

Пример: Намиране на сумата на числата от 1 до 100.

Данни: Целите числа от 1 до 100 и br;

Резултат: S – сумата;

Действия:

стъпка1: S = 0;

стъпка2: br = 1;

стъпка3: S = S+br;

стъпка4: Ако стойността на брояча е по.малка или равна на 100, стойността на брояча се увеличава с еденица и се преминава към стъпка3. В противен случай - край;

 

  1. Рекурсивни – Казва се, че един обект е рекурсивен, ако той частично се съдържа в себе си или е дефиниран чрез себе си.

 

Примери:

·         Дефиниране на естествени числа:

а) 1 е естествено число;

б) приемникът на естественото число е естествено число;

·         Дървовидни структури:

а) 0 е дърво (наречено празно);

б) ако t1 и t2 са дървета, то е дърво (начертано на обратно);

·         n!

а) 0! = 1;

б) ако n>0, то n! = n*(n-1)!;

 

  1. Евристични – Това е алгоритъм, който притежава следните свойства:

·         води до решение, макар и не оптимално;

Използват се различни критерии и подходи при търсенето на решение.

 

  1. Вероятностни – Поредното решение се приема с някаква вероятност между няколко възможности.

 

  1. Паралелни – Имат два основни блока, които ги отличават от последователните. Това са блок “разпаралелване”, чрез който се задават за изпълнение паралелни блокове, и блок “обединяване”, който обединява резултатите след паралелното изпълнение, преди процесът да се разпаралели отново.

Много задачи се подават на паралелна обработка. Такива са сортиране, матрични изчисления, изчисления на изрази и полиноми.

 

4. Описание на алгоритмите

 

Съществуват три подхода при записване на алгоритмите: текстови, графичен и посредством формални езици. Всеки един от трите подхода има своите предимства и недостатъци.

 

a)      Текстови подход

 

При текстовия подход се описват словесно последователност от стъпки, които трябва да се изпълнят за да се реши задачата.

Всички стъпки са номерирани според реда на тяхното изпълнение. Ако се налага нарушаване на този ред (за реализация на разклонения или цикли) се описва изрично коя е следващата стъпка.

 

Пример:

Намиране корените на едно квадратно уравнение y = ax2+bx+c.

Стъпки:

1.      Изчислява се D=b2-4ac.

  1. Проверява се знака на D. Ако D<0 се преминава към точка 3. В противен случай се изчислява x1= (-b+√D) / (2a), x1= (-b-√D) / (2a).
  2. Прекратява се изчисляването.

 

b)      Графично представяне - блокови схеми

 

Всяка стъпка се представя като възел в един насочен граф. Потокът на управление се оказва от свързващите стрелки.

Видове възли според ANSI X3.5-1970 стандарта:

·         Едновходови:

 

 

 

 

 

 

 

 

·         Двувходови:

 

 

 

 

 

 

 

 

 


·         Тривходови:

 

 

 

 

 

 

 

 

 

 


Пример:

Намиране корените на едно квадратно уравнение  y=ax2+bx+c (фиг.1).

 

 

Новият стандарт ANSI/ISO 5807-1985 разширява допустимите възли:

Начална инициализация.

Множествено разклонение.

Извеждане на екран.

Запис в двоичен файл.

Запис в текстови файл, предназначен за печат.

 

 

 

 

Основни свойства на блоковите схеми

 

1.      Точно едно “начало” и поне един “край”.

  1. През всеки един възел да има път от началото към края.
  2. Да не се позволява зацикляне.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


b) Чрез формални езици (езици за програмиране)

 

Пример

Да се напише програма, която въвежда n на брой числа от клавиатурата и намира сумата само на онези от тях, които са  положителни. Описана е с блоковата схема на фиг.5.

 

 

#include <iostream.h>

void main(void)

{

  int i,n;

  float x,s;   

  do{ 

     cout<<”n=”;  cin>>n;

  }while (n<1 || n>1000);

 

  for(s=0,i=1;i<=n;i++)

  {

       cout<<”x=”;  cin>>x;

       if(x>0) s+=x;

  }

  cout<<”s=”<<s<<”\n”;

}