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

Програмирането записва нещо, използвайки непознат чужд език. С развитието на тази област на знание, разработчиците отидоха още по-далеч и се научиха да пишат „нещо”, без дори да разбират как звучи на руски. Начинаещите се учат да пишат код наведнъж в C ++ или php, използвайки много библиотеки, и дори не разбират как наистина създават звуци на родния си език. Алгоритмизацията се занимава с обяснение и разбиране на това „нещо”.

алгоритмизация

Повечето примери на алгоритми за компютърни науки, дори и в университетите, се изучават на посредствено ниво. Честа практика е безкрайното писане на все по-сложен код. Опитите на неопитни програмисти да започнат веднага да пишат програми в езика за програмиране могат да се сравнят с работата на журналист, който едва усвоил основите на чужд език, пише статия за списание. Можете да избегнете този проблем, ако започнете да записвате работата си първо на собствения си език, да го редактирате, да проверявате за грешки и най-накрая да го превеждате на желания език.

Предимството на този подход е главно, че предприемачът ще се занимава с превод само 25% от времето, докато пише програма на нов език, той ще харчи 100% за работа с непознат език. В същото време той ще бъде в тесни условия и няма да бъде в състояние да извърши добра проверка за грешки и усъвършенстване на проекта.

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

Понятие за алгоритъм

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

Очевидно е, че той трябва да бъде обучен да решава. квадратични уравнения. Това се случва по следния начин:

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

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

Как можете да гарантирате, че идеите, използвани при решаването на проблема, ще се възприемат от изпълнителя, както го разбирате? Тук се доближаваме до концепцията на алгоритъма. Практиката показва, че за да може някой да обясни нещо, трябва да се следват следните стъпки:

• определяне на изходните данни (променлива и коефициенти на квадратичното уравнение);
• разделяне на процеса на вземане на решение на уникално познати компоненти за изпълнителя (дискриминантни формули и коренни находки);
• посочете реда на стъпките (първо изчислете дискриминанта, след това корените);
• да се установи условието, при което решението се счита за завършено (да се проверят намерените корени, като се замени с уравнението за мястото на променливите);
• посочете точно как трябва да бъде резултатът от решението (корените принадлежат към множеството реални числа).

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

Основните свойства на алгоритъма

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

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

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

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

Компютърни функции

За правилното създаване на алгоритми за компютрите е важно да се разберат техните възможности. Разгледайте първо количествата, с които компютърът работи. Като цяло те могат да бъдат разделени на числови и текстови, постоянни и променливи.

Постоянните числа са всички числа: 3.15, 100, 10 ⁵ , тяхната особеност е инвариантност по време на програмата. Променливите променят стойността си по време на изпълнението на кода и се определят по правило от буквите: x, y, max, min и т.н.

Текстовите променливи, като числовите, са постоянни или променливи. В първия случай това е само текстът: "добър", "а и б" и т.н. Във втория, символът е същият символ като числови променливи: име, град и т.н. Разликата между тях основно е в разпределената памет на компютъра под съхранението на такава променлива.

Операции, които компютърът може да изпълнява:

1. Четене на данни от входни устройства (клавиатура, мишка, файлове).
2. Изчисляване на стойности с помощта на математически функции: събиране, изваждане, sin, cos, ln и т.н. - всеки език за програмиране има свой собствен набор от вградени функции.
3. Извеждане на данни (на екрана, на хартия, в мрежовия интерфейс).
4. Преходът между етапите на програмата.
5. Сравнение на две величини (повече, по-малко, равни).

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

Начини за описване на алгоритми

Вербална. Това е най-лесният начин. Пример за това е рецептата. Допуска се използването на прости математически формули.

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

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

 алг заработная плата (int ST, real ZP)арг STрез ZPначалоесли ST < 5 то zp = 150иначеесли ST <= 15 то ZP = 180иначе ZP = 180 + (ST - 15)*10конец 

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

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

Има голямо разнообразие от алгоритми, предназначени за решаване на различни проблеми. Например, всеки учебник по висша математика съдържа стотици алгоритми: системно решение линейни уравнения намиране на екстремумите на функцията, изчисляване на интеграла и т.н. При подробен преглед на тяхната структура се оказва, че всички алгоритми могат да бъдат разделени на няколко типа. Разгледайте тези типове алгоритми с примери.

• линейни (изчисляване на резултата от добавяне или умножение, обмен на стойности на няколко променливи);
• разклоняване (определяне на най-голямото от няколко числа);
• цикличен (сортиране на масив, факторно изчисление).

Това са основни типове. Също така трябва да се отбележи, че в редица литература се подчертава и четвъртият вид - рекурсивен. Но тя няма специално обозначение в схематичната нотация и се изпълнява чрез базовите.

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

Принципи на алгоритмизация

1. Идентифицирайте изходните данни.
2. Изберете решение.
3. Разделете избрания метод на стъпки въз основа на възможностите на компютъра (език за програмиране).
4. Изпълнете алгоритъма под формата на схема, дефинирайки ясна последователност от стъпки.
5. Показва резултатите от изчисленията.
6. Маркирайте прехода към изходната верига.

Отстраняване на грешки в алгоритъма

Човек прави грешки и това е факт. Основният параметър на всеки алгоритъм трябва да бъде коректността на работата му. Отстраняване на грешки е процес на идентифициране и коригиране на грешки на алгоритъм. За да направите това, вземете определен набор от изходни данни, наречени тест. Те са, като правило, всички видове изходни данни. Например, ако е въведен номер, алгоритъмът трябва да се провери за правилна работа, като се вземат предвид: положителни, отрицателни, цяло число и реални числа, нулеви стойности и др.

Основният инструмент за проверка на точността на алгоритъма остава човешкият мозък. Разбира се, позволено е да се използват други компютърни средства за автоматизиране на проверката, но така или иначе човек се занимава с подготовка на тестове и анализиране на резултатите. В този случай възниква въпросът, защо се нуждаем от алгоритъм, ако човек изпълнява всичко сам? Тогава, че основната задача на алгоритъма е множественото решаване на определен тип проблеми.

Линейни алгоритми

Линейният алгоритъм е този, в който стъпките следват една след друга. Всеки алгоритъм, който не съдържа разклонения и цикли, е линеен. Помислете за пример на алгоритъм, който решава следния проблем: вълк и заек седят в две клетки, трябва да ги замените.

Ключът към решаването на този проблем е допълнителната температура на клетката, която трябва да се използва за размяна на животни.

Алгоритми на разклоняване

Както подсказва името, алгоритъмът има няколко клона. Същността на работата е да се избере един от възможните варианти на изчислителния процес, в зависимост от всякакви условия. Схематичното разклонение е представено от блок с форма на ромб, в който е посочено условието, а от двете му страни са избрани клоните, в зависимост от това дали условието е вярно или невярно. Разклонителният алгоритъм и примери за неговото приложение могат да бъдат намерени навсякъде. В програмирането, това е типичен if-else конструкт, който е на почти всеки език.

Даваме пример за алгоритъм за решаване на проблема за намиране на най-голямото между трите числа.

Цикличен алгоритъм

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

1. Присвояване на първоначалната стойност на променливите. Без изпълнение на това условие, цикълът най-вероятно няма да може да работи или да прави грешки.
2. Единицата изчислява резултатите. Това е основното тяло на цикъла.
3. Проверете крайното състояние на цикличния процес. Ако забравите да посочите условията, при които да завършите цикъла, алгоритъмът ще работи безкрайно.
4. Промяна на променливите Този блок влиза в сила след проверка на условието за прекратяване, ако е невярно. Ако забравим за този блок, цикълът винаги ще изпълнява едно действие и никога няма да свърши. Ето защо е важно променливите да претърпят всякакви промени при всяка итерация на цикъла.

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

Конструираме цикличен алгоритъм, като използваме примера за намиране на факториал на N.

Други типове алгоритми

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

• Механични алгоритми. Например, работата на двигател с вътрешно горене или на поточна линия.
• Вероятностни алгоритми. Тяхната работа се основава на теория на вероятностите и математическа статистика.
• Евристични алгоритми. Използвайте практически съображения в работата си, без строго математическо оправдание.
• Генетични алгоритми. Прилагайте биологични идеи в работата си.

И други.