Johdanto algoritmeihin

Algoritmi on vaiheiden sarja, joka kuvaa kuinka ongelma voidaan ratkaista. Jokainen tietokoneohjelma, joka loppuu tuloksella, perustuu periaatteessa algoritmiin. Algoritmeja ei kuitenkaan rajoiteta vain käytettäväksi tietokoneohjelmissa, vaan niitä voidaan käyttää myös ratkaisemaan matemaattisia ongelmia ja monissa arjen asioissa. Niiden toiminnan perusteella voimme jakaa algoritmit useisiin tyyppeihin. Katsotaanpa joitain tärkeitä.

Algoritmin tyypit

Algoritmeja on monen tyyppisiä, mutta algoritmit ovat tyypillisiä:

1) Rekursiivinen algoritmi

Tämä on yksi mielenkiintoisimmista algoritmeista, koska se kutsuu itseään pienemmäksi arvoksi tuloina, jotka se saa ratkaistuaan nykyisille tuloille. Yksinkertaisemmin sanottuna, se on algoritmi, joka kutsuu itseään toistuvasti, kunnes ongelma on ratkaistu.

Hanoi-torni tai kuvaajan DFS-kaltaiset ongelmat voidaan ratkaista helposti käyttämällä näitä algoritmeja.

Tässä on esimerkiksi koodi, joka löytää tekijän rekursioalgoritmin avulla:

Itse asiassa (y)

Jos y on 0

palauta 1

paluu (y * tosiasia (y-1)) / * tässä rekursio tapahtuu * /

2) Jaa ja valloita algoritmi

Tämä on toinen tehokas tapa ratkaista monia ongelmia. Jaa Divide and Conquer -algoritmeissa algoritmi kahteen osaan, ensimmäiset osat jakaa käsillä olevan ongelman samantyyppisiin pienempiin aliohjelmiin. Sitten toisessa osassa nämä pienet ongelmat ratkaistaan ​​ja yhdistetään sitten (yhdistetään) ongelman lopullisen ratkaisun tuottamiseksi.

Yhdistämislajittelu ja nopea lajittelu voidaan suorittaa jakamis- ja valloitusalgoritmeilla. Tässä on yhdistämisjärjestysalgoritmin pseudokoodi, joka antaa sinulle esimerkin:

Yhdistäminen (ar (), l, r)

Jos r> l

  1. Löydä keskipiste jakamalla annettu taulukko kahteen puolikkaaseen:

keskimmäinen m = (l + r) / 2

  1. Call mergeSorting ensimmäisen vuosipuoliskon aikana:

Soita mergeSorting (ar, l, m)

  1. Soita mergeSorting toiselle puoliskolle:

Soita mergeSorting (ar, m + 1, r)

  1. Yhdistä vaiheissa 2 ja 3 lajitellut puolikkaat:

Kutsu yhdistäminen (ar, l, m, r)

3) Dynaaminen ohjelmointialgoritmi

Nämä algoritmit toimivat muistamalla aiemman ajon tulokset ja käyttämällä niitä uusien tulosten löytämiseen. Toisin sanoen dynaaminen ohjelmointialgoritmi ratkaisee monimutkaiset ongelmat jakamalla se useiksi yksinkertaisiksi alioikeiksi ja ratkaisee ne sitten kerran ja tallentaa ne sitten tulevaa käyttöä varten.

Fibonacci-sekvenssi on hyvä esimerkki dynaamisen ohjelmoinnin algoritmeille, voit nähdä sen toimivan pseudokoodissa:

Fibonacci (N) = 0 (n = 0)

= 0 (n = 1)

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

4) ahne algoritmi

Näitä algoritmeja käytetään optimointiongelmien ratkaisemiseen. Tästä algoritmista löydämme paikallisesti optimaalisen ratkaisun (ottamatta huomioon tulevaisuuden seurauksia) ja toivomme löytävänsä optimaalisen ratkaisun maailmanlaajuisesti.

Menetelmä ei takaa, että pystymme löytämään optimaalisen ratkaisun.

Algoritmissa on 5 komponenttia:

  • Ensimmäinen on ehdokasjoukko, josta yritämme löytää ratkaisun.
  • Valintatoiminto, joka auttaa valitsemaan parhaan mahdollisen ehdokkaan.
  • Toteutettavuustoiminto, joka auttaa päättämään, voidaanko ehdokasta käyttää ratkaisun löytämiseen.
  • Objektiivinen toiminto, joka antaa arvon mahdolliselle ratkaisulle tai osaratkaisulle
  • Ratkaisutoiminto, joka kertoo, kun olemme löytäneet ratkaisun ongelmaan.

Huffman-koodaus ja Dijkstra-algoritmi ovat kahta esimerkkiä, joissa käytetään ahneutta algoritmia.

Huffman-koodauksessa algoritmi kulkee viestin läpi ja riippuen sanoman merkkien taajuudesta, kullekin merkille se antaa muuttuvan pituisen koodauksen. Huffman-koodauksen tekemistä varten on ensin rakennettava Huffman-puu syöttömerkeistä ja kuljettava sen jälkeen puun läpi koodien osoittamiseksi merkkeille.

5) Brute Force -algoritmi

Tämä on yksi konseptin yksinkertaisimmista algoritmeista. Raakavoima-algoritmi sokeasti toistaa kaikki mahdolliset ratkaisut etsimään yhtä tai useampaa ratkaisua, joka voi ratkaista funktion. Ajattele raakaa voimaa käyttäessäsi kaikkia mahdollisia numeroyhdistelmiä turvallisen avaamiseen.

Tässä on esimerkki peräkkäishausta, joka tehdään käyttämällä raa'aa voimaa:

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

A (n) ← X

i ← 0

Vaikka A (i) ≠ X tekevät

i ← i + 1

jos i <n palauttaa i

muuten palauta -1

6) Takaisinottoalgoritmi

Takaisinotto on tekniikka ratkaisun löytämiseksi ongelmalle inkrementaalisen lähestymistavan avulla. Se ratkaisee ongelmat rekursiivisesti ja yrittää päästä ratkaisuun ongelmaan ratkaisemalla yhden osan ongelmasta kerrallaan. Jos jokin ratkaisuista epäonnistuu, poistamme sen ja taaksepäin löytääksemme toisen ratkaisun.

Toisin sanoen, takaisinottoalgoritmi ratkaisee aliohjelman, ja jos se ei ratkaise ongelmaa, se peruuttaa viimeisen vaiheen ja alkaa jälleen löytää ratkaisu ongelmaan.

N Queens -ongelma on yksi hyvä esimerkki nähdä Backtracking-algoritmi toiminnassa. N kuningatar -ongelmassa todetaan, että shakkipöydässä on N kappaletta Queensia ja meidän on järjestettävä ne siten, että kukaan kuningatar ei voi hyökätä mihinkään muuhun hallituksen kuningataron kerran järjestettyään.

Katsotaanpa nyt SolveNQ-algoritmia ja Check Valid -toimintoja ongelman ratkaisemiseksi:

CheckValid (shakkilauta, rivi, sarake)

alkaa

Jos nykyisen sarakkeen vasemmalla puolella on kuningatar, palaa väärä

Jos kuningatar on vasemmassa yläkulmassa, palauta virhe

Jos kuningatar on vasemmassa alakulmassa, palauta väärät

Palata totta

pää

SolveNQ (hallitus, sarake)

alkaa

Jos kaikki sarakkeet ovat täynnä, palaa totta

Jokaisesta shakkilaudalla olevasta rivistä

Tehdä

Jos, CheckValid (taulu, x, sarake), niin

Aseta kuningatar pöydän soluun (x, sarake)

Jos SolveNQ (taulu, sarake + 1) = totta, palauta sitten tosi.

Muuta, poista kuningatar solusta (x, sarake) aluksella

Tehty

Palauta väärä

pää

Johtopäätös - Algoritmien tyypit

Algoritmit ovat takana useimmista vaikuttavista asioista, joita tietokoneet voivat tehdä, ja nämä ovat useimpien laskutoimitusten ytimessä. Algoritmien paremmuus ei vain autta sinua olemaan onnistunut ohjelmoija, vaan sinusta tulee myös entistä tehokkaampaa.

Suositellut artikkelit

Tämä on opas tyyppeihin algoritmeja. Tässä keskustellaan kuudesta tärkeimmästä algoritmityypistä niiden toimintojen kanssa. Voit myös käydä läpi muiden ehdotettujen artikkeleidemme saadaksesi lisätietoja -

  1. Johdanto algoritmiin
  2. Algoritmi ohjelmoinnissa
  3. Algoritmihaastattelukysymykset
  4. Tehtaalla Pythonissa Tekniikat
  5. Pikalajittelualgoritmit Java-sovelluksessa
  6. Kuusi suosituinta lajittelualgoritmia JavaScriptissä

Luokka:

Ohjelmistokehitys