Vrste algoritmov in primeri

Programiranje snema nekaj z neznanim jezikom nekoga drugega. Z razvojem tega področja znanja so razvijalci šli še dlje in se naučili pisati »nekaj«, ne da bi sploh razumeli, kako se sliši v ruskem jeziku. Začetniki se naučijo pisati kodo v C ++ ali php z uporabo številnih knjižnic in sploh ne razumejo, kako ustvarjajo zvoke v svojem maternem jeziku. Algoritemizacija se ukvarja s pojasnjevanjem in razumevanjem tega "nečesa".

Algoritemizacija

Večina primerov algoritmov za računalništvo, tudi na univerzah, se preučuje na povprečni ravni. Običajna praksa je neskončno pisanje vse bolj kompleksne kode. Poskusi neizkušenih programerjev, da bi takoj začeli pisati programe v programskem jeziku, lahko primerjamo z delom novinarja, ki je komaj obvladal osnove tujega jezika in piše članek za revijo. Tej težavi se lahko izognete, če začnete s snemanjem svojega dela najprej v svojem jeziku, ga uredite, preverite za napake in na koncu prevedete v želeni jezik.

Prednost tega pristopa je predvsem v tem, da se bo razvijalec ukvarjal s prevajanjem le 25% časa, pri pisanju programa v novem jeziku pa bo 100% porabil za delo z neznanim jezikom. Hkrati bo v skrčenih razmerah in ne bo sposoben dobro preveriti napak in izpopolniti projekta.

Algoritemizacija pomaga pri izvajanju projekta na računalniku, da opisuje proces rešitve v domačem in razumljivem jeziku v obliki diagrama medsebojno povezanih algoritmov, da analizira ideje in dobi najbolj kakovostno in premišljeno kodo, ki bo bolj odporna na napake in deluje bolj učinkovito.

Koncept algoritma

Računalnik ne ve, kako rešiti težave, lahko opravlja preprosta dejanja v določenem vrstnem redu. Kako je kalkulator? - vprašaš. Je tudi plod dela programerjev, ki so ustvarili program, ki uporablja določene algoritme za pridobitev potrebnih rezultatov. Razmislite o abstraktnem položaju. Kaj je treba storiti, če vas prosimo, da najdete korenine kvadratnega trinoma osebe, ki ni seznanjena z metodami reševanja enačb?

Očitno mora biti usposobljen za reševanje. kvadratne enačbe. To se zgodi tako:

1. Izberite rešitev.
2. Preglejte vse podrobnosti izbrane metode.
3. Pojasnite prve dve točki bodočemu umetniku v jeziku, ki ga razume.

Nato bodo izvajalcu lahko dali naloge za reševanje kvadratne enačbe. In če sta prva dva koraka preprosta in jasna - vse rešitve so opisane v ustrezni literaturi, potem je tretji korak težaven.

Kako lahko zagotovite, da bodo ideje, uporabljene pri reševanju problema, izvajalec dojemale, kot ga razumete? Tu se približujemo konceptu algoritma. Praksa kaže, da je za to, da lahko nekdo pravilno razloži nekaj, slediti naslednjim korakom:

• določitev izvornih podatkov (spremenljivka in koeficienti kvadratne enačbe);
• razdeli postopek odločanja na enolično znane komponente izvajalca (diskriminantne formule in iskanje korenin);
• določite vrstni red korakov (najprej izračunajte diskriminantno, nato korenine);
• ugotovi, pod kakšnim pogojem se raztopina šteje za popolno (preveri najdene korenine, jih nadomestimo z enačbo za mesto spremenljivk);
• natančno navedite, kako naj bi bil rezultat rešitve (korenine pripadajo množici realnih števil).

Opisan sklop korakov v splošnem pomenu je algoritem. Tako lahko algoritem razumemo kot metodo reševanja problema, napisano s pomočjo določenih pravil, ki omogoča nedvoumno razumevanje izvedenih dejanj in njihovega reda. V nadaljevanju bomo podrobneje obravnavali algoritme in primere problemov.

Glavne lastnosti algoritma

Diskretnost Proces reševanja problema je vedno sestavljen iz strogo ločenih dejanj, imenovanih koraki, ki imajo določen vrstni red izvršitve.

Zanesljivost Vsak korak mora biti jasen in nedvoumen, tako po pomenu kot v ključu dejanja, ki ga je treba sprejeti.

Uspešnost. Algoritem mora dati rezultat. V tem primeru je lahko število korakov v tisočih ali milijonih, vendar morajo vedno pripeljati do rezultata.

Masa. Vsak algoritem, ki je bil razvit za reševanje problema, bi moral veljati za vse težave tega tipa za vse veljavne vhodne podatke.

Računalniške funkcije

Za pravilno izdelavo algoritmov za računalnike je pomembno razumeti njihove zmožnosti. Najprej preučite količine, s katerimi računalnik deluje. Na splošno jih lahko razdelimo na številčne in besedilne, konstantne in spremenljive.

Konstantne številke so vse številke: 3,15, 100, 10 ⁵ , njihova posebnost je invarianca v celotnem programu. Spremenljivke spremenijo vrednost med izvajanjem kode in so praviloma označene s črkami: x, y, max, min itd.

Besedilne spremenljivke, kot so številske, so konstantne ali spremenljive. V prvem primeru gre le za besedilo: "dobro", "a in b" itd. V drugem je simbol enak simbolu kot numerične spremenljivke: ime, mesto itd. Razlika med njimi je v glavnem v pomnilniku računalnika. shranjevanje takšne spremenljivke.

Operacije, ki jih računalnik lahko izvaja:

1. Branje podatkov iz vhodnih naprav (tipkovnica, miška, datoteke).
2. Izračun vrednosti z uporabo matematičnih funkcij: seštevanje, odštevanje, sin, cos, ln itd. - vsak programski jezik ima svoj nabor vgrajenih funkcij.
3. Izhod podatkov (na zaslonu, na papirju, v omrežnem vmesniku).
4. Prehod med fazami programa.
5. Primerjava dveh količin (več, manj, enakih).

To so osnovne operacije, ki jih lahko izvaja večina programskih jezikov.

Načini za opis algoritmov

Verbalno. To je najlažji način. Primer je recept. Dovoljena je uporaba preprostih matematičnih formul.

Grafika. Opis z uporabo shem. To je poseben način za pisanje algoritmov z uporabo neke vrste splošno sprejetega algoritmičnega jezika - številke in bloki, ki imajo poseben pomen: pravokotnik je preprosto dejanje, poševni paralelogram je vhod / izhod, romb je pogoj itd.

Uporaba algoritemskega jezika. Podobno kot grafika je to tudi poseben način za pisanje algoritma. Obstaja veliko algoritemskih jezikov. Njihova pravila niso stroga, sicer bi bil programski jezik. Razmislite o primeru algoritma plačne liste, ki je odvisen od trajanja službe, zapisane z algoritmičnim jezikom.

 алг заработная плата (int ST, real ZP)арг STрез ZPначалоесли ST < 5 то zp = 150иначеесли ST <= 15 то ZP = 180иначе ZP = 180 + (ST - 15)*10конец 

Algoritemski jezik lahko imenujemo bolj strogo obliko pisanja kot verbalno. Uporablja se omejen nabor besed in njihovih konstrukcij, pa tudi vdolbina. Slaba stran besedne oblike in algoritemskega jezika je slabšanje vidnosti algoritma s povečanjem njegove velikosti. Zato se te metode lahko uporabijo samo za prenos pomena majhnih algoritmov.

Vrste algoritmov

Obstaja veliko različnih algoritmov, namenjenih reševanju različnih problemov. Na primer, vsak učbenik višje matematike vsebuje na stotine algoritmov: sistemske rešitve linearne enačbe iskanje ekstremov funkcije, izračunavanje integralov itd. Vendar pa se po podrobni preučitvi njihove strukture izkaže, da lahko vse algoritme razdelimo na več tipov. Razmislite o teh vrstah algoritmov s primeri.

• linearni (izračun rezultata dodajanja ali množenja, izmenjava vrednosti več spremenljivk);
• razvejanje (določanje največjega števila);
• ciklično (sortiranje nizov, faktorski izračun).

To so osnovni tipi. Omeniti je treba tudi, da je v številni literaturi poudarjen tudi četrti tip - rekurzivni. Vendar pa v shematskem zapisu nima posebne oznake in se izvaja skozi osnovne.

Več podrobnosti o vsakem algoritmu izračuna s primeri bo opisano spodaj.

Načela algoritemizacije

1. Ugotovite izvorne podatke.
2. Izberite rešitev.
3. Razdelite izbrano metodo na korake, ki temeljijo na zmožnostih računalnika (programski jezik).
4. Zaženite algoritem v obliki sheme, ki določa jasen vrstni red korakov.
5. Prikaže rezultate izračunov.
6. Označite prehod na izhodno vezje.

Razhroščevanje algoritmov

Oseba dela napake, in to je dejstvo. Glavni parameter vsakega algoritma mora biti pravilnost njegovega dela. Odpravljanje napak je proces prepoznavanja in popravljanja napak algoritma. Če želite to narediti, vzemite določen nabor izvornih podatkov, imenovan test. Praviloma so vse vrste izvornih podatkov. Na primer, če je vneseno število, je treba algoritem preveriti za pravilno delovanje ob upoštevanju: pozitivnih, negativnih, celih in realnih števil, ničelnih vrednosti itd.

Glavno orodje za preverjanje točnosti algoritma ostaja človeški možgani. Seveda je dovoljeno uporabljati tudi druga računalniška orodja za avtomatizacijo preverjanja, vendar se tako ali drugače oseba ukvarja s pripravo testov in analiziranjem rezultatov. V tem primeru se postavlja vprašanje, zakaj potrebujemo algoritem, če oseba vse opravi sam? Nato je glavna naloga algoritma večkratna rešitev določene vrste problemov.

Linearni algoritmi

Linearni algoritem je tisti, v katerem koraki sledijo eden za drugim. Vsak algoritem, ki ne vsebuje vej in ciklov, je linearen. Razmislite o primeru algoritma, ki rešuje naslednji problem: volk in zajec sedita v dveh kletkah, zato ju morate zamenjati.

Ključ do reševanja tega problema je dodatna temperatura celice, ki jo je treba uporabiti za zamenjavo živali.

Razdelitveni algoritmi

Kot že ime pove, ima algoritem več vej. Bistvo dela je izbrati eno od možnih variant računalniškega procesa, odvisno od pogojev. Shematsko razvejanje je predstavljeno z blokom v obliki diamanta, znotraj katerega je označen pogoj, in na njegovih straneh so izbrane veje, odvisno od tega, ali je pogoj resničen ali napačen. Algoritem razvejanosti in primeri njegove uporabe najdemo povsod. Pri programiranju je to tipičen konstrukt if-else, ki je v skoraj vsakem jeziku.

Prikazan je primer algoritma za reševanje problema iskanja največjega izmed treh številk.

Ciklični algoritem

Cikličen je algoritem, v katerem se pojavijo večkratne ponovitve enakih korakov, v katerih se lahko spremeni samo vrednost določene spremenljivke, nad katero so izdelani izračuni. O vrsti cikličnega algoritma in primera bomo razpravljali spodaj, za zdaj pa bomo našteli glavne korake za izgradnjo cikla.

1. Določitev začetne vrednosti spremenljivk. Brez izpolnjevanja tega pogoja cikel najverjetneje ne bo sposoben delati ali bo delal napake.
2. Enota izračuna rezultate. To je glavno telo cikla.
3. Preverite končno stanje cikličnega procesa. Če pozabite določiti pogoj za zaključek cikla, bo algoritem potekal za nedoločen čas.
4. Spremeni spremenljivke Ta blok začne veljati po preverjanju pogoja prekinitve, če je bil napačen. Če pozabimo na ta blok, bo cikel vedno izvajal eno dejanje in se nikoli ne bo končal. Zato je pomembno, da se spremenljivke spreminjajo pri vsaki ponovitvi zanke.

Obstaja več vrst cikličnih algoritmov: s postkondicijo, predpogojem in parametrom.

Konstruiramo ciklični algoritem na primeru iskanja faktorije N.

Druge vrste algoritmov

Obstaja več algoritmov, ki se razlikujejo po klasifikaciji ali izvoru.

• Mehanski algoritmi. Na primer, delovanje motorja z notranjim izgorevanjem ali montažne linije.
• Verjetnostni algoritmi. Njihovo delo temelji na teoriji verjetnosti in matematični statistiki.
• Hevristični algoritmi. Uporabite praktične vidike pri njihovem delu, brez stroge matematične utemeljitve.
• Genetski algoritmi. Pri svojem delu uporabite biološke ideje.

In drugi.