Algoritmide tüübid - Lugege 6 peamist olulist tüüpi algoritmi

Lang L: none (table-of-contents):

Anonim

Sissejuhatus algoritmidesse

Algoritm on etappide jada, mis kirjeldavad, kuidas probleemi saab lahendada. Iga arvutiprogramm, mis lõpeb tulemusega, põhineb põhimõtteliselt algoritmil. Algoritmid ei piirdu siiski ainult arvutiprogrammides kasutamisega, neid saab kasutada ka matemaatiliste probleemide lahendamiseks ja paljudes igapäevase elu küsimustes. Selle põhjal, kuidas nad toimivad, saame jagada algoritmid mitut tüüpi. Vaatame mõnda olulist.

Algoritmi tüübid

Algoritme on palju liike, kuid nende algtüübid on järgmised:

1) Rekursiivne algoritm

See on üks huvitavamaid algoritme, kuna see nimetab ennast sisenditeks väiksema väärtusega, mille ta saab pärast praeguste sisendite lahendamist. Lihtsamalt öeldes on see algoritm, mis kutsub ennast korduvalt, kuni probleem on lahendatud.

Neid algoritme kasutades saab hõlpsasti lahendada selliseid probleeme nagu Hanoi torn või graafiku DFS.

Näiteks siin on kood, mis leiab fakultaatori, kasutades rekursiooni algoritmi:

Fakt (y)

Kui y on 0

tagasi 1

tagasi (y * Fakt (y-1)) / * siin toimub kordus * /

2) Algoritm jagada ja vallutada

See on veel üks tõhus viis paljude probleemide lahendamiseks. Jagades ja vallutades algoritmid, jagage algoritm kaheks osaks, esimesed osad jagavad käsitsi oleva probleemi väiksemateks sama tüüpi alamprobleemideks. Seejärel teises osas need väiksemad probleemid lahendatakse ja seejärel ühendatakse (kombineeritakse), et saada probleemi lõplik lahendus.

Ühendamise ja kiire sortimise saab teha jagamise ja vallutamise algoritmide abil. Siin on näide ühendamise sortimisalgoritmi pseudokoodist:

MergeSorting (ar (), l, r)

Kui r> l

  1. Leidke keskpunkt, et jagada antud massiiv kaheks pooleks:

keskmine m = (l + r) / 2

  1. Esimese poole kõne ühendamineSortimine:

Kõne ühendamineSortimine (ar, l, m)

  1. Teise poolaasta kõnede liitmineSortimine:

Kõne ühendamineSortimine (ar, m + 1, r)

  1. Ühendage 2. ja 3. astmes järjestatud pooled:

Kõnede ühendamine (ar, l, m, r)

3) dünaamilise programmeerimise algoritm

Need algoritmid toimivad nii, et nad mäletavad eelmise töö tulemusi ja kasutavad neid uute tulemuste leidmiseks. Teisisõnu, dünaamiline programmeerimisalgoritm lahendab keerulised probleemid, jagades selle mitmeks lihtsaks alamprobleemiks ja lahendab seejärel kõik neist üks kord ning seejärel salvestab need edaspidiseks kasutamiseks.

Fibonacci jada on hea näide dünaamilise programmeerimise algoritmidest, näete seda pseudokoodis töötamas:

Fibonacci (N) = 0 (n = 0 korral)

= 0 (n = 1)

= Fibonacci (N-1) + Finacchi (N-2) (kui n> 1)

4) ahne algoritm

Neid algoritme kasutatakse optimeerimisprobleemide lahendamiseks. Selles algoritmis leiame lokaalselt optimaalse lahenduse (arvestamata tulevikus võimalike tagajärgedega) ja loodame leida optimaalseima lahenduse globaalsel tasandil.

Meetod ei taga, et suudame leida optimaalse lahenduse.

Algoritm koosneb 5 komponendist:

  • Esimene neist on kandidaatide komplekt, kust proovime leida lahendust.
  • Valimisfunktsioon, mis aitab valida parimat võimalikku kandidaati.
  • Teostatavusfunktsioon, mis aitab otsustada, kas kandidaati saab kasutada lahenduse leidmiseks.
  • Objektiivne funktsioon, mis omistab väärtuse võimalikule lahendusele või osalisele lahendusele
  • Lahendusfunktsioon, mis annab teada, kui oleme probleemile lahenduse leidnud.

Huffmani kodeerimine ja Dijkstra algoritm on kaks peamist näidet, kus kasutatakse Greedy algoritmi.

Huffmani kodeeringus läbib algoritm teate ja sõltuvalt selle sõnumi tähemärkide sagedusest määrab iga märk iga muutuva pikkusega kodeeringu. Huffmani kodeerimise jaoks peame kõigepealt ehitama Huffmani puu sisestusmärkidest ja seejärel liikuma läbi puu, et määrata märkidele koodid.

5) julma jõu algoritm

See on kontseptsiooni üks lihtsamaid algoritme. Jõhkrate jõudude algoritm kordab pimesi kõiki võimalikke lahendusi, et otsida ühte või mitut lahendust, mis võiks funktsiooni lahendada. Mõelge julmale jõule, kui kasutate seifi avamiseks kõiki võimalikke numbrikombinatsioone.

Siin on näide järjestikuse otsingu kohta, mida tehakse jõhkra jõu abil:

Algoritm S_Search (A (0..n), X)

A (n) ← X

i ← 0

Kuigi A (i) ≠ X teevad

i ← i + 1

kui i <n tagasi i

muidu tagasi -1

6) Tagasiulatuva algoritm

Tagasijõudmine on tehnika probleemile lahenduse leidmiseks järkjärgulise lähenemise abil. See lahendab probleemid rekursiivselt ja püüab probleemile lahenduse leida, lahendades probleemi ühe osa korraga. Kui üks lahendustest ebaõnnestub, eemaldame selle ja jätkame teise lahenduse leidmiseks.

Teisisõnu lahendab tagasiulatuv algoritm alamprobleemi ja kui see probleemi lahendada ei õnnestu, tühistab ta viimase sammu ja alustab uuesti probleemile lahenduse otsimist.

N Queens'i probleem on üks hea näide, kuidas näha tagasiulatuva algoritmi toimimist. N kuninganna probleem väidab, et malelauas on N kuninganna tükki ja me peame need korraldama nii, et ükski kuninganna ei saaks rünnata ühtegi teist lauda korraldatud kuningannat.

Nüüd vaatame probleemi lahendamiseks SolveNQ algoritmi ja funktsioone Check Valid:

CheckValid (malelaud, rida, veerg)

Alusta

Kui praeguse veeru vasakpoolses servas on kuninganna, tagastage vale

Kui kuninganna on vasakpoolses diagonaalis, tagastage vale

Kui kuninganna on vasakpoolses diagonaalis, tagastage vale

Naase tõsi

Lõpp

SolveNQ (juhatus, veerg)

Alusta

Kui kõik veerud on täis, tagastage väärtus tõene

Iga malelauas oleva rea ​​kohta

Tehke

Kui, CheckValid (tahvel, x, veerg), siis

Seadke kuninganna tahvli lahtrisse (x, veerg)

Kui SolveNQ (tahvel, veerg + 1) = tõene, tagastage tõene.

Muul juhul eemaldage kuninganna lahtrist (x, veerg) laualt

Valmis

Tagasi vale

Lõpp

Järeldus - algoritmide tüübid

Algoritmid on enamiku muljetavaldavate asjade taga, mida arvutid saavad teha. Need on enamiku arvutiülesannete keskmes. Algoritmidega parem olemine ei aita teid mitte ainult eduka programmeerijana, vaid muutub ka efektiivsemaks.

Soovitatavad artiklid

See on juhend algoritmide tüüpide kohta. Siin käsitleme 6 kõige olulisemat algoritmide tüüpi koos nende funktsioonidega. Lisateavet leiate ka meie muudest soovitatud artiklitest -

  1. Sissejuhatus algoritmi
  2. Algoritm programmeerimisel
  3. Algoritmi intervjuu küsimused
  4. Faktoriaal Pythonis | Tehnika
  5. Kiire sortimise algoritmid Java-s
  6. Kuus parimat sortimisalgoritmi JavaScriptis