Типови алгоритама и примери

Програмирање снима нешто користећи непознат језик другог. Развојем ове области знања, програмери су отишли ​​још даље и научили како да пишу "нешто", чак и без разумевања како то звучи на руском. Почетници уче да пишу код одједном у Ц ++ или пхп користећи многе библиотеке, а чак ни не разумеју како оно што стварају звукове на свом матерњем језику. Алгоритмизација се бави објашњавањем и разумевањем овог “нечега”.

Алгоритхмизатион

Већина примера алгоритама за рачунарске науке, чак и на универзитетима, проучавају се на осредњем нивоу. Уобичајена пракса је бескрајно писање све сложенијих кодова. Покушаји неискусних програмера да одмах почну да пишу програме у програмском језику могу се упоредити са радом новинара који једва да је савладао основе страног језика, пише чланак за часопис. Овај проблем можете да избегнете ако почнете да снимате свој рад прво на свом језику, да га уредите, проверите да ли постоје грешке и на крају преведете на жељени језик.

Предност овог приступа је углавном у томе што ће се програмер бавити превођењем само 25% времена, док ће писати програм на новом језику, а потрошит ће 100% на рад са непознатим језиком. У исто време, он ће бити у скученим условима и неће моћи да провери добру проверу грешака и усавршавање пројекта.

Алгоритмизација помаже у имплементацији пројекта на компјутеру да опише процес рјешавања на изворном и разумљивом језику у облику дијаграма међусобно повезаних алгоритама, да анализира идеје и добије најквалитетнији и замишљенији код који ће бити отпорнији на грешке и радити ефикасније.

Појам алгоритма

Рачунар не зна како да реши проблеме, већ може да обавља само једноставне радње у одређеном редоследу. "Како је калкулатор?" - питаш. То је уједно и плод рада програмера који су креирали програм који користи одређене алгоритме за добијање потребних резултата. Размотрите апстрактну ситуацију. Шта би требало урадити ако се од вас тражи да пронађете корене квадратног тродимента особе која није упозната са методама решавања једначина?

Очигледно, он мора бити обучен да решава. квадратне једначине. Ово се дешава на следећи начин:

1. Изаберите решење.
2. Прегледајте све детаље одабраног метода.
3. Објасните прве две тачке будућем уметнику на језику који разуме.

Тада ће бити могуће дати задатке извођачу радова за рјешавање квадратне једнаџбе. А ако су прва два корака једноставна и јасна - сва решења су описана у релевантној литератури, онда је трећи корак тежак.

Како можете осигурати да ће идеје кориштене у рјешавању проблема бити перципиране од стране извођача онако како ви то разумијете? Овде се приближавамо концепту алгоритма. Пракса показује да, да би неко нешто исправно објаснио, морају се слиједити сљедећи кораци:

• одредити изворне податке (варијаблу и коефицијенте квадратне једнаџбе);
• раздвојити процес одлучивања на јединствено познате компоненте за извођача (дискриминантне формуле и проналажење коријена);
• одредите редослед корака (прво израчунајте дискриминант, затим корене);
• успоставити услов под којим се решење сматра комплетним (проверити пронађене корене, замењујући их у једначину за место променљивих);
• навести тачно како би требало да буде резултат решења (корени припадају скупу реалних бројева).

Описани скуп корака у општем смислу је алгоритам. Дакле, алгоритам се може схватити као метод решавања проблема, написан уз помоћ одређених правила, омогућавајући недвосмислено разумевање извршених радњи и њиховог поретка. У наставку ће се детаљније расправљати о алгоритмима и примјерима проблема.

Главна својства алгоритма

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

Сигурност Сваки корак треба да буде јасан и недвосмислен, како по значењу тако иу кључу акције коју треба предузети.

Перформансе. Алгоритам би требао дати резултат. У овом случају, број корака може бити у хиљадама или милијунима, али они увијек морају довести до резултата.

Масс. Било који алгоритам развијен да реши проблем треба да буде применљив на све проблеме овог типа за све валидне улазне податке.

Рачунарске функције

Да би се исправно креирали алгоритми за рачунаре, важно је разумети њихове могућности. Прво размотрите количине којима рачунар ради. У принципу, могу се поделити на нумеричке и текстуалне, константне и променљиве.

Константни бројеви су сви бројеви: 3.15, 100, 10 ⁵ , њихова специфичност је инваријантност кроз програм. Варијабле мењају своју вредност у току извршавања кода и означене су, по правилу, словима: к, и, мак, мин, итд.

Текстуалне варијабле, као што су нумеричке, су константне или променљиве. У првом случају, ово је само текст: "добар", "а и б", итд. У другом, симбол је исти симбол као нумеричке варијабле: име, град, итд. Разлика између њих углавном лежи у меморији рачунара. под чувањем такве променљиве.

Операције које рачунар може да обавља:

1. Читање података са улазних уређаја (тастатура, миш, датотеке).
2. Израчунавање вриједности помоћу математичких функција: збрајање, одузимање, син, цос, лн, итд. - сваки програмски језик има свој властити скуп уграђених функција.
3. Излаз података (на екрану, на папиру, у мрежном интерфејсу).
4. Транзиција између фаза програма.
5. Поређење две величине (више, мање, једнако).

Ово су основне операције које се могу изводити на већини програмских језика.

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

Вербал. Ово је најлакши начин. Пример је рецепт. Употреба једноставних математичких формула је дозвољена.

Грапхиц. Опис користећи шеме. Ово је посебан начин за писање алгоритама користећи врсту општеприхваћеног алгоритамског језика - фигуре и блокови који имају специфично значење: правоугаоник је једноставна акција, укошени паралелограм је улаз / излаз, ромб је услов, итд.

Употреба алгоритамског језика. Слично графици, ово је такође посебан начин за писање алгоритма. Постоји много алгоритамских језика. Њихова правила нису строга, иначе би то био програмски језик. Размотримо пример алгоритма платног списка, у зависности од дужине радног стажа, који се снима помоћу алгоритамског језика.

 алг заработная плата (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. Означите прелаз на излазни круг.

Алгоритам дебуггинг

Човек прави грешке, а то је чињеница. Главни параметар било којег алгоритма треба да буде исправност његовог рада. Дебуггинг је процес идентификације и исправљања грешака алгоритма. Да бисте то урадили, узмите одређени скуп изворних података, назван тест. Они су, по правилу, све врсте изворних података. На пример, ако се унесе број, алгоритам треба проверити да ли је исправан, узимајући у обзир: позитивне, негативне, целобројне и реалне бројеве, нулте вредности, итд.

Главни алат за проверу тачности алгоритма остаје људски мозак. Наравно, дозвољено је користити и друге компјутерске алате за аутоматизацију верификације, али на овај или онај начин, особа се бави припремом тестова и анализом резултата. У овом случају, поставља се питање, зашто нам је потребан алгоритам ако особа све уради сам? Затим, да је главни задатак алгоритма вишеструко рјешење одређеног типа проблема.

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

Линеарни алгоритам је онај у којем кораци слиједе један за другим. Сваки алгоритам који не садржи гране и циклусе је линеаран. Размотримо пример алгоритма који решава следећи проблем: вук и зец седе у два кавеза, морате их заменити.

Кључ за решавање овог проблема је додатна ћелијска темп, која би требало користити за замену животиња.

Алгоритми гранања

Као што име имплицира, алгоритам има неколико грана. Суштина рада је да се изабере једна од могућих варијанти рачунског процеса, у зависности од услова. Шематско гранање је представљено блоком у облику дијаманта, унутар којег је назначено стање, а на његовим странама су гране избора, у зависности од тога да ли је услов истинит или лажан. Алгоритам гранања и примјери његове примјене могу се наћи свуда. У програмирању, ово је типичан иф-елсе конструкт, који је на готово сваком језику.

Дајемо пример алгоритма за решавање проблема проналажења највећег међу три броја.

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

Циклични је алгоритам у којем се јављају вишеструка понављања истих корака, у којима се може променити само вредност специфичне променљиве изнад које се израђују. Типови цикличног алгоритма и примера ће бити размотрени у наставку, али за сада ћемо навести главне кораке за изградњу циклуса.

1. Додељивање почетне вредности променљивих. Без испуњења овог услова, циклус највероватније неће бити у стању да ради или ће направити грешке.
2. Јединица израчунава резултате. Ово је главно тело циклуса.
3. Проверите крајње стање цикличног процеса. Ако заборавите да наведете услов под којим ћете завршити циклус, алгоритам ће радити бесконачно.
4. Промени променљиве Овај блок ступа на снагу након провере услова завршетка, ако је лаж. Ако заборавимо на овај блок, циклус ће увек извести једну акцију и никада се неће завршити. Због тога је важно да променљиве пролазе било какве промене на свакој итерацији петље.

Постоји неколико типова цикличних алгоритама: са посткондицијом, предусловом и параметром.

Конструишемо циклични алгоритам користећи пример проналажења факторијала Н.

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

Постоји више алгоритама који се разликују по класификацији или пореклу.

• Мецханицал алгоритхмс. На пример, рад мотора са унутрашњим сагоревањем или монтажне линије.
• Пробабилистички алгоритми. Њихов рад се заснива на теорији вероватноће и математичкој статистици.
• Хеуристички алгоритми. Користите практична разматрања у свом раду, без ригорозног математичког оправдања.
• Генетски алгоритми. Примијенити биолошке идеје у свом раду.

И други.