Увод у алгоритме
Алгоритам је низ корака који описују како се проблем може решити. Сваки рачунарски програм који се заврши резултатом у основи је заснован на алгоритму. Алгоритми, међутим, нису ограничени само за употребу у рачунарским програмима, већ се могу користити и за решавање математичких проблема и у многим стварима свакодневног живота. На основу начина на који функционишу, алгоритме можемо поделити на више типова. Погледајмо неке од важних.
Врсте алгоритма
Постоји много типова алгоритама, али основне врсте алгоритама су:
1) рекурзивни алгоритам
Ово је један од најзанимљивијих алгоритама јер себе назива мањом вредношћу као улазима који добија након решавања за тренутне улазе. Једноставније речено, то је алгоритам који се понавља више пута док проблем не буде решен.
Проблеми као што су Ханојски торањ или ДФС графикона могу се лако решити коришћењем ових алгоритама.
На пример, ево кода који налази фактороријум користећи алгоритам рекурзије:
Чињеница (и)
Ако је и 0
повратак 1
повратак (и * чињеница (и-1)) / * овде се догађа рекурзија * /
2) Поделите и освојите алгоритам
Ово је још један ефикасан начин решавања многих проблема. У алгоритмима Дивиде анд Цонкуер алгоритам поделите на два дела, први део проблема је подељен на мање подпроблеме истог типа. Затим се у другом делу ти мањи проблеми решавају и затим сабирају (комбинују) како би се добило коначно решење проблема.
Спајање и брзо сортирање могу се извршити алгоритмима за поделу и освајање. Ево псеудокод алгоритма сортирања сортирања који ће вам дати пример:
МергеСортинг (ар (), л, р)
Ако је р> л
- Пронађите средину да бисте подијелили дати низ на двије половине:
средња м = (л + р) / 2
- Назовите спајањеСортинг за прво полувреме:
Позовите мергеСортинг (ар, л, м)
- Назовите мергеСортинг за другу половину:
Позовите мергеСортинг (ар, м + 1, р)
- Спојите половине сортиране у 2. и 3. кораку:
Спајање позива (ар, л, м, р)
3) Алгоритам динамичког програмирања
Ови алгоритми функционишу тако што памте резултате протеклог покретања и користе их за проналажење нових резултата. Другим речима, алгоритам динамичког програмирања решава сложене проблеме разбијајући га на више једноставних потпроблема и затим сваки од њих решава једном, а затим их складишти за будућу употребу.
Секвенце Фибонацције је добар пример за алгоритме динамичког програмирања, а то можете видети у псеудо коду:
Фибонацције (Н) = 0 (за н = 0)
= 0 (за н = 1)
= Фибонацције (Н-1) + Финацчи (Н-2) (за н> 1)
4) похлепни алгоритам
Ови алгоритми се користе за решавање проблема оптимизације. У овом алгоритму проналазимо локално оптимално решење (без имало обзира на било какве последице у будућности) и надамо се да ћемо пронаћи оптимално решење на глобалном нивоу.
Метода не гарантује да ћемо успети да нађемо оптимално решење.
Алгоритам има 5 компоненти:
- Први је скуп кандидата из којег покушавамо пронаћи рјешење.
- Изборна функција која помаже да се изабере најбољи могући кандидат.
- Функција изводљивости која помаже у одлучивању може ли се кандидат користити за проналажење решења.
- Објективна функција која додељује вредност могућем решењу или делимичном решењу
- Решење функција која говори када смо пронашли решење проблема.
Хуффман Цодинг и Дијкстра алгоритам су два главна примера где се користи похлепни алгоритам.
У Хуффмановом кодирању, алгоритам пролази кроз поруку и зависно од фреквенције знакова у тој поруци, за сваки знак додјељује кодирање промјењиве дужине. Да бисмо урадили Хуффманово кодирање, прво морамо да направимо Хуффманово стабло од улазних знакова, а затим га прођемо кроз дрво да бисмо додељивали кодове ликовима.
5) Алгоритам бруталне силе
Ово је један од најједноставнијих алгоритама у концепту. Алгоритам бруталне силе слепо понавља све могуће решења за тражење једног или више решења која могу да реше функцију. Замислите грубу силу као коришћење свих могућих комбинација бројева да бисте отворили сеф.
Ево примера Секвенцијалне претраге која се врши употребом грубе силе:
Алгоритам С_претраживање (А (0..н), Кс)
А (н) ← Кс
и ← 0
Док А (и) = Кс то раде
и ← и + 1
ако се вратим и н
врати се -1
6) Алгоритам повратног хода
Повлачење уназад је техника проналаска решења проблема у инкременталном приступу. Решава проблеме рекурсивно и покушава да дође до решења проблема решавањем једног дела проблема. Ако једно од решења не успе, уклањамо га и уклањамо поново да бисмо пронашли друго решење.
Другим речима, алгоритам повратног праћења решава потпроблем и ако не успе да реши проблем, поништава последњи корак и поново почиње да проналази решење проблема.
Н Куеенс проблем је добар пример за приказ алгоритма повратног праћења у акцији. Проблем Н Куеен каже да у шаховској табли има Н комада краљице и морамо их распоредити тако да ниједна краљица не може напасти ниједну другу краљицу у одбору једном организованом.
Сада погледајмо алгоритам СолвеНК и провери ваљане функције за решавање проблема:
ЦхецкВалид (Шаховска табла, ред, ступац)
Почетак
Ако је краљица на левој страни тренутне колоне, вратите се лажно
Ако је краљица на горњој левој дијагонали, вратите се лажно
Ако је краљица у доњој левој дијагонали, вратите се лажно
Ретурн труе
Крај
СолвеНК (Одбор, Ступац)
Почетак
Ако су сви ступци пуни, вратите се тачно
За сваки ред присутан на шаховској плочи
Урадити
Ако је, ЦхецкВалид (табла, к, ступац), онда
Поставите краљицу у ћелију (к, ступац) на плочи
Ако је СолвеНК (табла, колона + 1) = Тачно, вратите истину.
Иначе, уклоните краљицу из ћелије (к, ступац) са плоче
Готово
Врати лажно
Крај
Закључак - Врсте алгоритама
Алгоритми стоје иза већине импресивних ствари које рачунари могу радити и они су у сржи већине рачунарских задатака. Ако будете бољи са алгоритмима, не само да ће вам помоћи да будете успешан програмер, већ ћете и постати ефикаснији.
Препоручени чланци
Ово је водич за Врсте алгоритама. Овдје смо расправљали о топ 6 важних врста алгоритама са њиховим функцијама. Можете и да прођете кроз друге наше предложене чланке да бисте сазнали више -
- Увод у алгоритам
- Алгоритам у програмирању
- Питања о интервјуу за алгоритам
- Фацториал у Питхон-у | Технике
- Брзо сортирање алгоритама на Јави
- Топ 6 Алгоритам сортирања у ЈаваСцрипт-у