Въведение в алгоритмите
Алгоритъмът е последователност от стъпки, които описват как даден проблем може да бъде решен. Всяка компютърна програма, която завършва с резултат, в основата си се основава на алгоритъм. Алгоритмите обаче не са ограничени само за използване в компютърни програми, те могат да се използват и за решаване на математически проблеми и по много въпроси от ежедневния живот. Въз основа на това как функционират, можем да разделим Алгоритмите на няколко типа. Нека да разгледаме някои от важните.
Видове алгоритъм
Има много видове алгоритми, но основните типове алгоритми са:
1) Рекурсивен алгоритъм
Това е един от най-интересните алгоритми, тъй като той се нарича с по-малка стойност като вход, който получава след решаването на текущите входове. С по-прости думи, това е алгоритъм, който се обажда многократно, докато проблемът не бъде решен.
Проблеми като Ханойската кула или DFS на графика могат лесно да бъдат решени с помощта на тези алгоритми.
Например, тук е код, който намира факториал, използвайки рекурсивен алгоритъм:
Факт (у)
Ако y е 0
връщане 1
връщане (y * Факт (y-1)) / * тук се случва рекурсията * /
2) Разделете и завладете алгоритъм
Това е друг ефективен начин за решаване на много проблеми. В алгоритмите Divide and Conquer разделете алгоритъма на две части, като първите части разделят проблема на ръка на по-малки подпроблеми от същия тип. След това във втората част тези по-малки проблеми се решават и след това се добавят заедно (комбинирани), за да се получи окончателното решение на проблема.
Обединяване сортиране и бързо сортиране може да се направи с алгоритми за разделяне и завладяване. Ето псевдокода на алгоритъма за сортиране на сливане, за да ви даде пример:
MergeSorting (ar (), l, r)
Ако r> l
- Намерете средната точка, за да разделите дадения масив на две половини:
средна m = (l + r) / 2
- Обадете се mergeSorting за първата половина:
Обадете се mergeSorting (ar, l, m)
- Обадете се mergeSorting за втората половина:
Обадете се mergeSorting (ar, m + 1, r)
- Обединете половините, сортирани в стъпки 2 и 3:
Обединяване на повикване (ar, l, m, r)
3) Алгоритъм за динамично програмиране
Тези алгоритми работят като запомнят резултатите от миналото изпълнение и ги използват за намиране на нови резултати. С други думи, алгоритъмът за динамично програмиране решава сложни проблеми, като го разбива на множество прости подпроблеми и след това решава веднъж всяка от тях и след това ги съхранява за бъдеща употреба.
Последователността на Фибоначи е добър пример за алгоритмите за динамично програмиране, можете да го видите в псевдокода:
Фибоначи (N) = 0 (за n = 0)
= 0 (за n = 1)
= Фибоначи (N-1) + Финачи (N-2) (за n> 1)
4) Алчен алгоритъм
Тези алгоритми се използват за решаване на задачи за оптимизация. В този алгоритъм намираме локално оптимално решение (без да се съобразяваме с каквито и да е последици в бъдеще) и се надяваме да намерим оптималното решение на глобално ниво.
Методът не гарантира, че ще успеем да намерим оптимално решение.
Алгоритъмът има 5 компонента:
- Първият е набор от кандидати, от който се опитваме да намерим решение.
- Функция за подбор, която помага да изберете най-добрия възможен кандидат.
- Функция за осъществимост, която помага при вземането на решение дали кандидатът може да бъде използван за намиране на решение.
- Обективна функция, която присвоява стойност на възможно решение или на частично решение
- Функция за решение, която казва кога сме намерили решение на проблема.
Кодиране на Huffman и алгоритъмът на Dijkstra са два основни примера, при които се използва алчен алгоритъм.
При кодирането на Huffman, алгоритъмът преминава през съобщение и в зависимост от честотата на знаците в това съобщение, за всеки символ той приписва кодиране с променлива дължина. За да направим Huffman кодиране, първо трябва да изградим Huffman дърво от въвежданите символи и след това да преминем през дървото, за да присвоим кодове на героите.
5) Алгоритъм на грубата сила
Това е един от най-простите алгоритми в концепцията. Алгоритъмът на груба сила сляпо итератира всички възможни решения за търсене на едно или повече от едно решение, което може да реши функция. Помислете за грубата сила като използване на всички възможни комбинации от числа, за да отворите сейф.
Ето пример за последователно търсене, извършено чрез груба сила:
Алгоритъм S_Search (A (0..n), X)
A (n) ← X
i ← 0
Докато A (i) ≠ X правя
i ← i + 1
ако аз <n се върна i
друго върнете -1
6) Алгоритъм за изтегляне
Обратното проследяване е техника за намиране на решение на проблем при инкрементален подход. Той решава проблемите рекурсивно и се опитва да стигне до решение на проблем, като решава по едно парче от проблема наведнъж. Ако едно от решенията се провали, ние го премахваме и отстъпваме, за да намерим друго решение.
С други думи, алгоритъмът за обратно проследяване решава подпроблема и ако не успее да реши проблема, той отменя последната стъпка и започва отново да намери решението на проблема.
Проблемът с N Queens е един добър пример за разглеждане на алгоритъм за проследяване в действие. Проблемът с N Queen казва, че в шахматната дъска има N парчета кралици и трябва да ги подредим така, че нито една кралица да не може да атакува друга кралица в дъската веднъж организирана.
Сега нека да разгледаме алгоритъма на SolveNQ и да проверим валидни функции за решаване на проблема:
CheckValid (Шахматна дъска, ред, колона)
начало
Ако вляво от текущата колона има кралица, върнете фалшиво
Ако кралицата е в горния ляв диагонал, върнете невярно
Ако кралицата е в долния ляв диагонал, върнете невярно
Върнете се вярно
Край
SolveNQ (съвет, колона)
начало
Ако всички колони са пълни, върнете истина
За всеки ред, присъстващ в шахматната дъска
Do
Ако, CheckValid (дъска, х, колона), тогава
Задайте кралицата в клетка (х, колона) на дъската
Ако SolveNQ (дъска, колона + 1) = True, върнете true.
Иначе, премахнете кралицата от клетката (x, колона) от дъската
Свършен
Върнете невярно
Край
Заключение - Видове алгоритми
Алгоритмите стоят зад повечето впечатляващи неща, които компютрите могат да правят и те са в основата на повечето компютърни задачи. По-доброто с алгоритмите не само ще ви помогне да бъдете успешен програмист, но и ще станете по-ефективни.
Препоръчителни статии
Това е ръководство за Видовете алгоритми. Тук обсъждаме топ 6 важни вида алгоритми с техните функции. Можете да разгледате и другите ни предложени статии, за да научите повече -
- Въведение в алгоритъма
- Алгоритъм в програмирането
- Въпроси за интервю за алгоритъм
- Факториал в Python | техники
- Бързо сортиране на алгоритми в Java
- Топ 6 алгоритъм за сортиране в JavaScript