Tip:
Highlight text to annotate it
X
Какво е алгоритъм?
В компютърните науки,
алгоритъмът е набор от инструкции
за решаване на някакъв проблем, стъпка по стъпка.
Обикновено алгоритмите се изпълняват от компютри,
но ние, хората, също имаме алгоритми.
Например, как бихте преброили
броят на хората в една стая?
Ами, ако сте като мен,
вероятно ще посочите към всеки човек,
един по един,
и ще броите от 0:
1, 2, 3, 4 и т.н.
Ами, това е алгоритъм.
В действителност, нека се опитаме да го представим
малко по-формално като псевдокод,
В синтаксис наподобяващ английския,
който прилича на език за програмиране.
Нека n е равно на 0.
За всеки човек в стаята, задайте n = n + 1.
Как да се тълкува този псевдокод?
Ами, ред 1 декларира, така да се каже,
променлива, наречена n
и инициализира стойността ѝ на нула.
Това просто означава, че в началото на нашия алгоритъм,
нещото, с което броим
има стойност равна на нула.
В края на краищата, преди да започнем да броим,
ние все още не сме преброили нищо.
Наричайки тази променлива n е просто установена практика.
Бих могъл да я нарека почти всичко друго.
Сега, ред 2 обозначава началото на цикъл,
поредица от стъпки, които ще се повторят няколко пъти.
Така че в нашия пример, стъпката която правим
е преброяване на хората в стаята.
Под ред 2 е ред 3,
който описва точно как ще проведем броенето.
Абзацът предполага, че ред 3 е този,
който ще се повтаря.
Така че това, което казва псевдокода
е, че след като се започне от нула,
за всеки човек в стаята,
ние ще увеличим n с 1.
Сега, дали този алгоритъм е правилен?
Добре, нека да го тестваме малко.
Дали работи ако има 2 души в стаята?
Нека да видим.
В ред 1, ние инициализираме n с нула.
За всеки един от тези двама души,
след това увеличаваме n с 1.
Така че при първото преминаване през цикъла,
ние актуализираме n от 0 до 1,
през второто преминаване през същият цикъл,
ние актуализираме n от 1 до 2.
И така, в края на този алгоритъм, n е 2,
което всъщност съвпада с броя на хората в стаята.
Дотук добре.
Какво ще кажете за граничен случай, обаче?
Да предположим, че има нула хора в стаята,
освен мен, който прави броенето.
В ред 1, отново инициализираме n с нула.
Този път, обаче, ред 3 не се изпълнява въобще,
тъй като няма хора в стаята,
и така, n остава нула,
което всъщност съвпада с броя на хората в стаята.
Доста просто, нали?
Но преброяването на хора, един по един е също и доста неефективно, нали?
Разбира се, че можем да се справим по-добре!
Защо да не броим двама души наведнъж?
Вместо да броим 1, 2, 3, 4, 5, 6, 7, 8 и т.н.,
защо да не броим
2, 4, 6, 8 и така нататък?
Това дори звучи по-бързо, и със сигурност е.
Нека представим тази оптимизация като псевдокод.
Нека n е равно на нула.
За всяка двойка от хора в стаята,
задайте n = n + 2.
Доста проста промяна, нали?
Вместо да броим хората един по един,
вместо това ги броим по двама наведнъж.
Този алгоритъм е следователно два пъти по-бърз от последния.
Но дали е правилен?
Нека да видим.
Дали работи ако има 2 души в стаята?
В ред 1, ние инициализираме n с нула.
За тази една двойка от хора, след това увеличаваме n с 2.
И така, в края на този алгоритъм, n е 2,
което всъщност съвпада с броя на хората в стаята.
Да предположим след това, че има нула хора в стаята.
В ред 1, ние инициализираме n с нула.
Както преди, ред 3 не се изпълнява въобще,
тъй като няма никакви двойки хора в стаята,
и така, n остава нула,
което всъщност съвпада с броя на хората в стаята.
Но какво ще стане, ако в стаята има 3-ма души?
Как ще се справи алгоритъмът?
Нека да видим.
В ред 1, ние инициализираме n с нула.
За една двойка от тези хора,
след това увеличаваме n с 2,
но после какво?
Няма друга пълна двойка хора в стаята,
така ред 2 вече не се прилага.
И така, в края на този алгоритъм,
n е все още 2, което не е вярно.
В действителност този алгоритъм се нарича бъгав,
защото има грешка.
Нека го поправим с нов псевдокод.
Нека n е равно на нула.
За всяка двойка от хора в стаята,
задайте n = n + 2.
Ако 1 човек остане сам, без двойка,
задайте n = n + 1.
За решаването на този проблем,
ние въведохме в ред 4 условие,
иначе известно като разклонение,
което се изпълнява само ако има един човек,
който не може да групираме с друг.
Така че сега, дали има 1 или 3,
или всеки нечетен брой на хора в стаята,
този алгоритъм ще ги преброи.
Можем ли да се справим дори по-добре?
Ами, можем да броим по 3-ки или 4-ки или дори 5-ци и 10-ци,
но отвъд това ще стане
малко по-трудно за отбелязване.
В края на краищата,
дали изпълнени от компютри или от хора,
алгоритмите са просто набор от инструкции,
с които решаваме проблеми.
Това бяха само три.
Какви проблеми бихте решили с алгоритъм?