Модул 13

Алгоритми и блок-схеми

Първите стъпки в програмирането, преди първия ред код: какво е алгоритъм и кои пет свойства трябва да има, как се описва словесно, с псевдокод и с блок-схема и как блоковете се подреждат в линейни, разклонени и циклични структури. Завършва с пътя от изходния код до изпълнението: езици за програмиране, компилатор срещу интерпретатор и какво правят `dotnet build` и `dotnet run`. Включва и правилата за безопасна работа в компютърния кабинет.

Теория

Преди първия ред код идва инструктажът за безопасна работа в компютърния кабинет: не пипаме кабели и контакти, не включваме и не изключваме устройства без разрешение, не ядем и не пием до компютрите, сядаме изправени на 50–70 см от монитора, а при мирис на изгоряло, искри или повреда веднага уведомяваме учителя. Не инсталираме програми и не сваляме файлове без разрешение — така пазим и техниката, и собствените си данни. Самият предмет учи как да накараме компютъра да реши задача вместо нас, а за това първо трябва да опишем решението като алгоритъм (algorithm). Алгоритъмът е крайна, наредена последователност от точно определени стъпки, които превръщат входни данни в резултат. Познавате го от ежедневието: рецептата за кекс, упътването до училище и правилото за деление с остатък са алгоритми. Този, който изпълнява стъпките, се нарича изпълнител (executor) — може да е човек, робот или компютър, но компютърът разбира само стъпки, записани на език, който познава.

За да е наистина алгоритъм, описанието трябва да има пет свойства. Дискретност: решението е разделено на отделни стъпки, които се изпълняват една след друга, и следващата започва едва когато предишната е завършила. Определеност: всяка стъпка е еднозначна — „добави 1 към x“ е определена стъпка, а „добави малко“ не е, защото двама изпълнители ще я разберат различно. Крайност: алгоритъмът завършва след краен брой стъпки; ако нещо се повтаря безкрайно, това не е алгоритъм, а грешка. Масовост: алгоритъмът решава цял клас от задачи, а не една — „събери 3 и 5“ работи само веднъж, докато „прочети a и b и изведи a + b“ работи за всякакви числа. Резултатност: след края винаги има резултат — число, текст или поне съобщение, че решение няма (например при деление на нула).

Един и същ алгоритъм може да се опише по три начина. Словесното описание е номериран списък от изречения на български език: „1. Прочети a. 2. Прочети b. 3. Изведи a + b.“ — най-лесно за начало, но при по-дълги задачи става двусмислено и трудно за следене. Псевдокодът (pseudocode) е структуриран текст, който прилича на програма, но не зависи от конкретен език: малко ключови думи (ВХОД, ИЗХОД, АКО ... ТО ... ИНАЧЕ, ДОКАТО ... ПОВТАРЯЙ), присвояване със стрелка x <- 5 и отместване навътре за стъпките, които принадлежат на условие или цикъл. Блок-схемата (flowchart) е графично описание: всяка стъпка е фигура, а стрелките показват реда на изпълнение. Фигурите са стандартни — овал за начало и край, успоредник за вход и изход, правоъгълник за действие (изчисление, присвояване), ромб за проверка на условие с два изхода „Да“ и „Не“, а малко кръгче (съединител) свързва части от схемата, когато стрелките не стигат. Всяка схема има точно едно начало и един край, стрелките винаги показват посока, от правоъгълник излиза една стрелка, а от ромб — точно две.

Според начина, по който стъпките следват една след друга, алгоритмите са три вида, а блок-схемата веднага показва кой е. Линейният алгоритъм изпълнява всяка стъпка точно по веднъж, в реда на записване, без избор: блок-схемата е права верига от овал през успоредници и правоъгълници до овал — например „прочети страните, изчисли лицето, изведи го“. Разклоненият алгоритъм съдържа условие (ромб): според това дали то е вярно, се изпълнява единият или другият клон, а после двата клона се събират отново в една стрелка. Разклонението е пълно, когато има действие и за „Да“, и за „Не“ (по-голямото от две числа), и непълно, когато при „Не“ просто се продължава напред (ако числото е отрицателно, смени знака му). Условието е сравнение (a > b, x == 0, n % 2 == 0) и винаги има само два отговора; ако случаите са три, слагаме втори ромб в някой от клоновете. В C# ромбът става if, а двата клона — if ... else.

Цикличният алгоритъм повтаря група стъпки, наречена тяло на цикъла, докато е изпълнено условие. На блок-схемата това е ромб, от който единият изход води надолу към тялото, а от края на тялото стрелка се връща нагоре към ромба — именно връщащата се стрелка отличава цикъла от разклонението. Всеки цикъл има четири части: начална стойност (i <- 1, sum <- 0), условие за продължаване (i <= n), тяло и промяна (i <- i + 1), която приближава условието към „Не“. Ако условието се проверява преди тялото, цикълът е с предусловие (в C# — while) и тялото може да не се изпълни нито веднъж; ако се проверява след него — с постусловие (do ... while) и тялото се изпълнява поне веднъж; когато броят повторения е известен предварително, използваме цикъл с брояч (for). Най-честата грешка е забравената промяна: без i <- i + 1 условието никога не става лъжа и алгоритъмът нарушава свойството крайност. Затова преди да нарисувате цикъл, отговорете на въпроса „кое ще го спре?“.

Блок-схемата е за хора; процесорът разбира само машинен код — двоични числа, които означават елементарни команди като „събери“ или „премести“. За да не пишем такива числа, използваме език за програмиране (programming language): изкуствен език със строги правила за запис (синтаксис) и за значение (семантика), в който една команда отговаря на много машинни. Езиците са стотици — C#, Python, Java, C++, JavaScript — и всеки има преводач (translator), който превръща нашия изходен код (source code) в команди за машината. Компилаторът (compiler) превежда целия изходен код наведнъж, преди изпълнението, и създава отделен изпълним файл; ако има синтактична грешка, той спира и я докладва с номер на ред и колона, а готовата програма работи бързо и без нужда от компилатора при потребителя. Интерпретаторът (interpreter) чете и изпълнява изходния код ред по ред при всяко стартиране — удобно за бързи експерименти, но по-бавно, а грешка в ред, до който изпълнението не е стигнало, остава скрита. C, C++ и C# са компилирани езици, а Python, JavaScript и PHP — интерпретирани.

При C# преводът е на две стъпки. Компилаторът на C# (част от .NET SDK, извиква се с dotnet build) превръща файловете .cs в междинен код (Intermediate Language, IL), записан във файл .dll; при стартиране с dotnet run средата за изпълнение .NET (CLR) превежда междинния код в машинен за точно този процесор с JIT компилатор (just-in-time, „точно навреме“), затова една и съща .dll работи и на Windows, и на Linux, и на macOS. Пътят от идеята до работещата програма е винаги един и същ: анализираме задачата (какъв е входът и какъв — изходът), съставяме алгоритъм и го проверяваме на ръка, записваме го като изходен код в редактор (Visual Studio или VS Code), компилираме, изпълняваме и тестваме с различни входни данни. Грешките са три вида: синтактични (компилаторът не разбира записа — липсваща точка и запетая, незатворена скоба) се хващат при компилиране; грешки по време на изпълнение (деление на нула, въведен текст вместо число) спират програмата, когато вече работи; логически грешки (компилира се, работи, но дава грешен резултат) не ги открива никой освен вас — чрез тестване. Хубавата новина: ако блок-схемата е вярна, писането на кода е почти механично, защото успоредникът става Console.ReadLine() и Console.WriteLine(), правоъгълникът — присвояване, ромбът — if, а връщащата се стрелка — while или for.

Златни правила

Първо алгоритъм, после код

Не сядайте да пишете код, преди да можете да разкажете решението на стъпки или да го нарисувате. Грешка в алгоритъма се поправя с гумичка; грешка в кода — с часове търсене.

Една стъпка — едно еднозначно действие

Всяка стъпка трябва да се разбира само по един начин и да е ясно коя е следващата. Това са свойствата дискретност и определеност: „направи нещо“ или „вземи по-голямото“ без да е казано от кои числа не са стъпки.

Всеки цикъл има начало, условие, тяло и промяна

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

Ромбът има точно два изхода, надписани Да и Не

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

Компилира се не значи работи вярно

Компилаторът проверява само синтаксиса. Дали резултатът е верен, се разбира единствено с изпълнение и тестове с различни входни данни, включително гранични — 0, отрицателно число, равни числа.

Бърз справочник

Фигури в блок-схемата

ФигураКак се рисуваЗа какво служиВ C#
Начало / КрайОвал (заоблен правоъгълник)Отбелязва къде започва и къде свършва алгоритъмът; точно по един от всекиНачалото и краят на Main
ВходУспоредникЧетене на данни от потребителяConsole.ReadLine()
ИзходУспоредникИзвеждане на резултатConsole.WriteLine()
Действие (обработка)ПравоъгълникИзчисление или присвояване; една входяща и една изходяща стрелкаsum = sum + i;
Условие (решение)РомбПроверка с два изхода, надписани Да и Неif (a > b) ... else ...
ЦикълРомб + стрелка, връщаща се към негоПовтаряне на тялото, докато условието е вярноwhile (i <= n) { ... }
Цикъл с броячШестоъгълник (или ромб с брояч)Известен брой повторения: от, до, стъпкаfor (int i = 1; i <= n; i++)
СъединителМалко кръгче с буква или числоСвързва части от схемата на различни места или странициНяма — кодът е последователен
СтрелкаЛиния със стрелкаПосоката на изпълнение; надолу и надясно, нагоре само в цикълРедът на операторите

Компилатор срещу интерпретатор

ХарактеристикаКомпилаторИнтерпретатор
Кога превеждаЦелия изходен код наведнъж, преди изпълнениетоРед по ред, по време на самото изпълнение
Резултат от преводаОтделен файл — изпълним .exe или междинен код .dllНяма отделен файл; изходният код се изпълнява директно
Откриване на грешкиСинтактичните — всички наведнъж, преди стартиране, с ред и колонаПо време на изпълнение; грешка в ред, до който не се стига, остава скрита
Скорост на изпълнениеПо-висока — машината изпълнява готов кодПо-ниска — всеки ред се превежда при всяко стартиране
Какво трябва на потребителяСамо изпълнимият файл (и среда за изпълнение като .NET)Самият интерпретатор, инсталиран на машината
Промяна и пробаПромяна, компилиране, стартиранеПромяна, стартиране; има интерактивен режим (REPL)
ПримериC, C++, Go; C# и Java — до междинен код, после JITPython, JavaScript, PHP, Bash

Код за анализ и пренаписване

Един алгоритъм, три описания: по-голямото от две числа

бележки.txt
ДАДЕНО: две цели числа a и b
ТЪРСИ СЕ: по-голямото от тях (max)

1) СЛОВЕСНО ОПИСАНИЕ
1. Прочети a.
2. Прочети b.
3. Ако a > b, запомни max = a; иначе запомни max = b.
4. Изведи max.
5. Край.

2) ПСЕВДОКОД
ВХОД: a, b
АКО a > b ТО
    max <- a
ИНАЧЕ
    max <- b
КРАЙ АКО
ИЗХОД: max

3) БЛОК-СХЕМА      ( ) овал   / / успоредник   [ ] правоъгълник   < > ромб

               ( Начало )
                    |
                    v
              / Вход: a, b /
                    |
                    v
               < a > b ? >
              Да /     \ Не
                /       \
               v         v
          [max <- a] [max <- b]
                \       /
                 \     /
                  v   v
              / Изход: max /
                    |
                    v
                ( Край )

Какво се случва тук?

  • Първите два реда фиксират входа (a, b) и изхода (max) — това е проверката за масовост: алгоритъмът работи за всякакви две числа, а не само за конкретни.
  • Словесното описание е най-близо до говоримия език, но вижте стъпка 3: тя крие и условие, и две действия, затова при по-сложни задачи става трудна за следене.
  • В псевдокода условието АКО a > b ТО ... ИНАЧЕ ... КРАЙ АКО показва ясно кой ред в кой клон е, а присвояването max <- a означава „запиши стойността на a в max“ (в C# това е max = a;).
  • В блок-схемата ромбът a > b ? има точно два изхода, надписани „Да“ и „Не“; всеки клон съдържа по един правоъгълник, след което двете стрелки се събират преди успоредника за изход — това е пълно разклонение.
  • Схемата има един овал „Начало“ и един „Край“, а всички стрелки сочат надолу — няма връщаща се стрелка, следователно алгоритъмът е разклонен, но не цикличен.
  • Проверете го на ръка: при a = 7, b = 3 условието е „Да“ и max става 7; при a = 3, b = 7 — „Не“ и max е 7; при равни числа a = 5, b = 5 условието е „Не“, max е 5 — резултатът е верен и в граничния случай.
  • Същите фигури ще срещнете в C#: Console.ReadLine() за успоредника за вход, if (a > b) { max = a; } else { max = b; } за ромба с двата клона и Console.WriteLine(max) за изхода.

От цикъл в блок-схема до работеща C# програма: сума от 1 до n

бележки.txt
ДАДЕНО: цяло число n >= 0
ТЪРСИ СЕ: сумата 1 + 2 + ... + n

ПСЕВДОКОД
ВХОД: n
sum <- 0
i <- 1
ДОКАТО i <= n ПОВТАРЯЙ
    sum <- sum + i
    i <- i + 1
КРАЙ ДОКАТО
ИЗХОД: sum

БЛОК-СХЕМА
          ( Начало )
               |
               v
          / Вход: n /
               |
               v
     [ sum <- 0 ; i <- 1 ]
               |
               v
 +-----> < i <= n ? > --Не--> / Изход: sum / --> ( Край )
 |             | Да
 |             v
 |    [ sum <- sum + i ]
 |             |
 |             v
 |      [ i <- i + 1 ]
 |             |
 +-------------+

ТАБЛИЦА ЗА ПРОСЛЕДЯВАНЕ (n = 3)
стъпка       | i | sum | i <= n ?
старт        | 1 |  0  | Да
повторение 1 | 2 |  1  | Да
повторение 2 | 3 |  3  | Да
повторение 3 | 4 |  6  | Не  -> ИЗХОД: 6

Program.cs (същият алгоритъм на C#)
using System;

class Program
{
    static void Main()
    {
        Console.Write("n = ");
        int n = Convert.ToInt32(Console.ReadLine());
        int sum = 0;
        int i = 1;
        while (i <= n)
        {
            sum = sum + i;
            i = i + 1;
        }
        Console.WriteLine($"Сумата от 1 до {n} е {sum}");
    }
}

ТЕРМИНАЛ (компилиране и изпълнение)
> dotnet new console -n Suma --use-program-main
> cd Suma
  (заменете съдържанието на Program.cs с кода по-горе)
> dotnet build
  Suma -> C:\Proekti\Suma\bin\Debug\net8.0\Suma.dll
  Build succeeded.
> dotnet run
n = 10
Сумата от 1 до 10 е 55

Какво се случва тук?

  • Псевдокодът показва четирите части на цикъла: начална стойност (sum <- 0, i <- 1), условие (i <= n), тяло (sum <- sum + i) и промяна (i <- i + 1); махнете промяната и цикълът никога не свършва.
  • В блок-схемата цикълът се познава по стрелката, която от последния правоъгълник се връща нагоре към ромба; изходът „Не“ на ромба е единственият път към края — това е цикъл с предусловие, защото проверката е преди тялото.
  • Таблицата за проследяване изпълнява алгоритъма на ръка: при n = 3 тялото се изпълнява три пъти и sum минава през 1, 3, 6; при n = 0 условието е „Не“ още на първата проверка, тялото не се изпълнява нито веднъж и резултатът е 0 — вярно.
  • Програмата Program.cs е превод едно към едно: успоредникът за вход е Console.ReadLine() (с Convert.ToInt32, защото от конзолата идва текст), правоъгълниците са присвоявания, а ромбът с връщащата се стрелка е while (i <= n) { ... }.
  • dotnet new console създава проект, а dotnet build извиква компилатора на C#, който проверява синтаксиса и записва междинния код в Suma.dll; ако забравите точка и запетая, тук ще видите error CS1002 с номер на ред и колона и .dll няма да се създаде.
  • dotnet run компилира (ако нещо е променено) и стартира програмата: средата .NET зарежда Suma.dll, JIT компилаторът превежда междинния код в машинен и чак тогава се появява подканата n = .
  • Успешната компилация не доказва, че алгоритъмът е верен — затова последната стъпка е тест с няколко стойности: n = 10 дава 55, n = 1 дава 1, n = 0 дава 0.

Внимавай! Чести грешки

Грешките, които почти всеки прави в тази тема — виж разликата между грешния и правилния код.

Неопределена стъпка

Грешно

1. Прочети числата.
2. Намери по-голямото.
3. Изведи резултата.

Правилно

1. Прочети a.
2. Прочети b.
3. Ако a > b, max <- a; иначе max <- b.
4. Изведи max.

Кои числа, колко са и как точно се намира „по-голямото“ — изпълнителят компютър не може да се досети. Всяка стъпка трябва да назовава конкретни данни и конкретно действие (свойство определеност).

Безкраен цикъл

Грешно

i <- 1
ДОКАТО i <= 10 ПОВТАРЯЙ
    ИЗХОД: i
КРАЙ ДОКАТО

Правилно

i <- 1
ДОКАТО i <= 10 ПОВТАРЯЙ
    ИЗХОД: i
    i <- i + 1
КРАЙ ДОКАТО

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

Ромб с един изход

Грешно

      < x > 0 ? >
           | Да
           v
/ Изход: положително /
           |
           v
       ( Край )

Правилно

      < x > 0 ? > --Не--+
           | Да         |
           v            |
/ Изход: положително /  |
           |            |
           +<-----------+
           |
           v
       ( Край )

Условието винаги има два отговора и за двата трябва да има път нататък. При непълно разклонение клонът „Не“ просто заобикаля действието и се събира с другия клон преди края — но стрелката трябва да я има.

Компилира се, значи е вярно

Грешно

> dotnet build
  Build succeeded.
Готово, задачата е решена!

Правилно

> dotnet run
n = 10  ->  55   (очаквано 55)
n = 1   ->  1    (очаквано 1)
n = 0   ->  0    (очаквано 0)
Резултатите съвпадат -> задачата е решена.

Компилаторът проверява само дали записът спазва правилата на езика. Логическа грешка (например i < n вместо i <= n) се компилира без забележка и се открива само с изпълнение и сравнение с предварително изчислени очаквани резултати.

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

Опитай първо сам — подсказката е там само ако наистина закъсаш.

Линеен алгоритъм: лице и периметър

Съставете словесно описание и блок-схема на алгоритъм, който въвежда дължините a и b на правоъгълник и извежда лицето S и периметъра P. Определете вида на алгоритъма и проверете всяко от петте свойства.

Разклонен алгоритъм: знак на число

Съставете псевдокод и блок-схема на алгоритъм, който въвежда цяло число x и извежда „положително“, „отрицателно“ или „нула“. Проследете го на ръка за x = -4, x = 0 и x = 9.

Цикличен алгоритъм: най-голямото от n числа

Въвежда се броят n (n >= 1), а след това едно по едно n цели числа. Съставете псевдокод и блок-схема на алгоритъм, който извежда най-голямото от тях, без да ги запазва всичките. Проследете го с таблица за n = 4 и числата 3, 8, 2, 8, а после запишете същия алгоритъм на C#.

Мини-тест за проверка

Отговори си наум (или на глас!) и чак тогава разкрий отговора.

1. Алгоритъм гласи: „Прочети `a`. Докато `a > 0`, извеждай `a`.“ Кое от петте свойства е нарушено и как ще го поправите?

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

3. Каква е разликата между компилатор и интерпретатор и какво точно се случва с C# програма при `dotnet build` и `dotnet run`?

4. За задачата „намери сумата на две числа“ ученик предава алгоритъм с една стъпка: „Изведи 8“, защото в условието числата били 3 и 5. Кое свойство липсва и как изглежда правилният алгоритъм?

Речник на термините

Виж пълния речник на курса
Алгоритъм (algorithm)
Крайна наредена последователност от точно определени стъпки, която превръща входни данни в резултат. Притежава свойствата дискретност, определеност, крайност, масовост и резултатност.
Изпълнител (executor)
Този, който изпълнява стъпките на алгоритъма — човек, устройство или компютър. Компютърът изпълнява само стъпки, записани на език за програмиране, който разбира.
Псевдокод (pseudocode)
Структуриран текстов запис на алгоритъм с малко ключови думи (ВХОД, АКО, ДОКАТО) и отместване навътре, който прилича на програма, но не зависи от конкретен език.
Блок-схема (flowchart)
Графично описание на алгоритъм, в което стъпките са стандартни фигури (овал, успоредник, правоъгълник, ромб), а стрелките показват реда на изпълнение.
Разклонение (branching)
Част от алгоритъм, в която според истинността на условие се изпълнява единият или другият клон. Пълно е, когато има действие и за „Да“, и за „Не“; в C# — if ... else.
Цикъл (loop)
Повтаряне на група стъпки (тяло), докато условието е вярно. Има начална стойност, условие, тяло и промяна; в C# — while, do ... while и for.
Изходен код (source code)
Текстът на програмата, написан от човек на език за програмиране — при C# това са файловете .cs. Компютърът не може да го изпълни направо, нужен е преводач.
Компилатор (compiler)
Програма, която превежда целия изходен код наведнъж в машинен или междинен код и докладва синтактичните грешки преди изпълнението. Компилаторът на C# създава междинен код (IL) във файл .dll.
Интерпретатор (interpreter)
Програма, която чете изходния код и го изпълнява ред по ред при всяко стартиране, без да създава отделен изпълним файл. Така работят Python и JavaScript.

Провери знанията

Бърз тест с избор от отговори върху термините на модула — с точки и моментална обратна връзка.

Провери знанията си

9 въпроса върху термините от модула. Показваме определение — ти избираш правилния термин.

Препоръки за този модул

  • Преди всяка блок-схема напишете два реда: „Дадено:“ (входът) и „Търси се:“ (изходът). Когато те са ясни, стъпките между тях се подреждат много по-лесно.
  • Проверявайте алгоритъма с таблица за проследяване: колона за всяка променлива, ред за всяка стъпка. Пуснете го на ръка поне с два набора данни — обичаен и граничен (0, отрицателно число, n = 1).
  • Рисувайте схемите с молив и линия или в безплатен инструмент като diagrams.net (draw.io), където фигурите са готови. Стрелките вървят надолу или надясно, а нагоре се връща само стрелката на цикъл.
  • Инсталирайте .NET SDK у дома и проверете с dotnet --version; направете първия проект с dotnet new console -n Proba --use-program-main и го пуснете с dotnet run. Когато компилаторът покаже грешка, прочетете номера на реда и колоната — те сочат точно къде е проблемът.

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

Натисни Ctrl K или / отвсякъде, за да търсиш.