Описание на алгоритми чрез блок-схеми

Естествените езици не могат да бъдат използвани за описание на формализирани модели заради възможните неясноти, двусмислици и т.н. Това се отнася и до алгоритмите заради изискването за детерминираност.

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

 Съществуват средства за точно представяне на алгоритмите и ние ще разгледаме някои от тях.

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

Блок-схемите представляват графични средства за изрязяване на алгоритми.

Изграждат се от няколко вида геометрични фигури: правоъгълник, ромб, успоредник, овал и др.

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

Всяка блок-схема има начален блок, с който се посочва от коя команда трябва да започне изпълнението на алгоритъма и поне един блок, с който се посочва краят на изпълнението на алгоритъма.

Правоъгълникът се използва за описание на безусловни команди. Нарича се функционален блок.

Ромбът или условният блок се използва за описание на разклонения в изчислителния процес в зависимост от условието, което е записано в него. Ако условието е удовлетворено, изчислителният процес продължава с блока, към който сочи стрелката, означена с “Да”. В противен случай се продължава с блока, към който води стрелката, означена с “Не”. Условието се записва с логически израз.

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

При описанието на един алгоритъм е възможно да се използва друг алгоритъм. Този алгоритъм се указва с правоъгълник, чиито вертикални страни са удвоени, и се нарича блок за обръщение към подалгоритъм.

Вижте основните типове блокове , които изграждат блоковата схема

Често блоковете се номерират по подобие на номерирането на командите при словесното записване на алгоритъма. Обикновено номерата се поставят в лявата част на всеки блок, както е показано на следващата блок-схема за намиране на НОД (Алгоритъм на Евклид с изваждане):

 

 

Да разгледаме примери на алгоритми, описани с блок-схема.

Пример 1

От 9 броя видимо еднакви монети едната е по-лека (“фалшива”). Опишете чрез блокова схема начин за намирането и, ако се допускат две претегляния с везни без теглилки.

 

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

Данните ще представяме, както е прието в математиката, с променливи - малки или големи букви от латинската азбука, със или без индекси. За всяка такава буква ще си мислим като за място, в което могат да се съхраняват различни еднотипни данни. Буквата е постоянното име на това място, а стойностите, т.е. конкретните съхранявани данни, могат да се изменят по време на изпълнение на алгоритъма. Операцията „смяна на стойност” се отбелязва със знака :=, като в лявата страна се записва името, а в дясната - новата стойност. Например А:=0 означава, че докато не се срещне подобна операция с А в лявата страна, стойността на името А е 0. Малко по-сложни са такива смени на стойността като А:=А+1 .Това означава, че новата стойност е с единица по-голяма от старата.

Пример 2.  Да се опише с блок-схема алгоритъм, който по зададени радиуси R1 и R2 на две концентрични окръжности, R1>R2, намира лицето на фигурата, ограничена от двете окръжности. Алгоритъмът трябва да въведе числата R1 и R2, след което да пресметне последователно лицата S1 и S2 на двата кръга и лицето на фигурата S=S1-S2 и да изведе така пресметнатото лице S.

 

Пример 3 Опишете с блок-схема алгоритъма за решаване на линейното уравнение Ax+B=0.

В случай, че A=0 и B=0 всяко число х е решение на уравнението . Ако A=0 и B≠0 - уравнението няма решения.
Ако А≠0, уравнението има единствено решение x=-B/A.

 

 

Задачи за самостоятелна работа:

Задача 1. Опишете чрез блок-схема алгоритъм за намиране и извеждане лицето на квадрат със страна а.

Задача 2. Опишете чрез блок-схема алгоритъм за намиране и извеждане дължината на окръжност с радиус r, като предварително се направи проверка дали r>0. Ако r>0 да се намери и изведе дължината на окръжността. Ако r≤0 да се изведе подходящо съобщение.