Vrste algoritama i primjera

Programiranje snima nešto pomoću nepoznatog jezika nekog drugog. Razvojem ovog područja znanja, programeri su otišli još dalje i naučili kako pisati "nešto", čak i bez razumijevanja kako to zvuči na ruskom. Početnici uče pisati kod odjednom u C ++-u ili php-u koristeći mnoge knjižnice, a čak ni ne shvaćaju kako zapravo stvaraju zvukove na svom materinjem jeziku. Algoritmizacija se bavi objašnjavanjem i razumijevanjem ovog “nečega”.

Algorithmization

Većina primjera algoritama za računalne znanosti, čak i na sveučilištima, proučava se na prosječnoj razini. Uobičajena praksa je beskrajno pisanje sve složenijih kodova. Pokušaji neiskusnih programera da odmah počnu pisati programe u programskom jeziku mogu se usporediti s radom novinara koji, jedva da je savladao osnove stranog jezika, piše članak za časopis. Ovaj problem možete izbjeći ako počnete snimati svoj rad najprije na svom jeziku, urediti ga, provjeriti pogreške i na kraju prevesti na željeni jezik.

Prednost ovog pristupa je uglavnom u tome što će se programer baviti prevođenjem samo 25% vremena, dok će pisati program na novom jeziku, a potrošit će 100% na rad s nepoznatim jezikom. Istodobno, on će biti u skučenim uvjetima i neće moći provesti dobru provjeru pogrešaka i usavršavanja projekta.

Algoritmizacija pomaže u provedbi projekta na računalu kako bi opisala proces rješavanja na izvornom i razumljivom jeziku u obliku dijagrama međusobno povezanih algoritama, analizirati ideje i dobiti najkvalitetniji i zamišljeniji kod koji će biti otporniji na pogreške i učinkovitije raditi.

Pojam algoritma

Računalo ne zna kako riješiti probleme, već može izvoditi jednostavne radnje u navedenom redoslijedu. "Kako je kalkulator?" - pitaš. To je ujedno i plod rada programera koji su stvorili program koji koristi određene algoritme za dobivanje potrebnih rezultata. Razmotrite apstraktnu situaciju. Što bi trebalo učiniti ako se od vas traži da nađete korijene kvadratnog trojnika osobe koja nije upoznata s metodama rješavanja jednadžbi?

Očito, on mora biti obučen za rješavanje. kvadratne jednadžbe. To se događa na sljedeći način:

1. Odaberite rješenje.
2. Pregledajte sve pojedinosti odabrane metode.
3. Objasnite prve dvije točke budućem umjetniku na jeziku koji razumije.

Tada će biti moguće dati izvođaču zadatke za rješavanje kvadratne jednadžbe. A ako su prva dva koraka jednostavna i jasna - sva rješenja su opisana u relevantnoj literaturi, onda je treći korak težak.

Kako možete osigurati da će izvođači percipirati ideje korištene u rješavanju problema kao što ih razumijete? Ovdje se približavamo konceptu algoritma. Praksa pokazuje da, da bi netko nešto ispravno objasnio, moraju se slijediti sljedeći koraci:

• odrediti izvorne podatke (varijablu i koeficijente kvadratne jednadžbe);
• razdvojiti proces odlučivanja na jedinstveno poznate komponente izvođača (diskriminantne formule i pronalaženje korijena);
• odredite redoslijed koraka (najprije izračunajte diskriminant, zatim korijene);
• utvrditi stanje pod kojim se rješenje smatra potpunim (provjeriti pronađene korijene, zamjenjujući ih jednadžbom za mjesto varijabli);
• navesti točno kako bi trebao biti rezultat rješenja (korijeni pripadaju skupu realnih brojeva).

Opisani skup koraka u općem smislu je algoritam. Dakle, algoritam se može shvatiti kao metoda rješavanja problema, napisana uz pomoć određenih pravila, koja omogućuje nedvosmisleno razumijevanje izvedenih radnji i njihovog poretka. U nastavku će se detaljnije raspravljati o algoritmima i primjerima problema.

Glavna svojstva algoritma

Diskretna. Proces rješavanja problema uvijek se sastoji od strogo odvojenih akcija, nazvanih koraka, koje imaju određeni redoslijed izvršenja.

Izvjesnost. Svaki korak treba biti jasan i nedvosmislen, kako po značenju tako iu ključu akcije koju treba poduzeti.

Učinkovitost. Algoritam bi trebao dati rezultat. U ovom slučaju, broj koraka može biti u tisućama ili milijunima, ali oni uvijek moraju dovesti do rezultata.

Masačusets Bilo koji algoritam razvijen za rješavanje problema treba biti primjenjiv na sve probleme ovog tipa za sve valjane ulazne podatke.

Računalne značajke

Za pravilno stvaranje algoritama za računala važno je razumjeti njihove sposobnosti. Prvo razmotrite količine s kojima računalo radi. Općenito, mogu se podijeliti na numeričke i tekstualne, konstantne i varijabilne.

Konstantni brojevi su svi brojevi: 3.15, 100, 10 ⁵ , njihova osobitost je invarijantnost u cijelom programu. Varijable mijenjaju svoju vrijednost tijekom izvršavanja koda i označene su, u pravilu, slovima: x, y, max, min, itd.

Tekstualne varijable, poput numeričkih, su konstantne ili varijabilne. U prvom slučaju, to je samo tekst: "dobar", "a i b", itd. U drugom, simbol je isti simbol kao numeričke varijable: ime, grad, itd. Razlika između njih uglavnom leži u dodijeljenoj memoriji računala. pod pohranjivanjem takve varijable.

Operacije koje računalo može izvesti:

1. Čitanje podataka s ulaznih uređaja (tipkovnica, miš, datoteke).
2. Izračunavanje vrijednosti pomoću matematičkih funkcija: zbrajanje, oduzimanje, sin, cos, ln, itd. - svaki programski jezik ima svoj vlastiti skup ugrađenih funkcija.
3. Izlaz podataka (na zaslonu, na papiru, u mrežnom sučelju).
4. Prijelaz između faza programa.
5. Usporedba dviju veličina (više, manje, jednake).

To su osnovne operacije koje se mogu izvoditi na većini programskih jezika.

Načini opisivanja algoritama

Verbalno. To je najlakši način. Primjer je recept. Dopuštena je uporaba jednostavnih matematičkih formula.

Grafička. Opis pomoću shema. To je poseban način pisanja algoritama pomoću vrste općeprihvaćenog algoritamskog jezika - figure i blokovi koji imaju specifično značenje: pravokutnik je jednostavna radnja, kosi paralelogram je ulaz / izlaz, romb je uvjet, itd.

Korištenje algoritamskog jezika. Slično grafici, to je također poseban način pisanja algoritma. Postoje mnogi algoritamski jezici. Njihova pravila nisu stroga, inače bi to bio programski jezik. Razmotrite primjer algoritma za obračun plaća, ovisno o dužini radnog staža, snimljenom pomoću algoritamskog jezika.

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

Algoritamski jezik može se nazvati rigoroznijim oblikom pisanja od verbalnog. Koristi se ograničen skup riječi i njihovih konstrukcija, kao i uvlačenje. Loša strana verbalnog oblika i algoritamskog jezika je pogoršanje vidljivosti algoritma s povećanjem njegove veličine. Stoga se ove metode mogu koristiti samo za prenošenje značenja malih algoritama.

Vrste algoritama

Postoji ogromna raznolikost algoritama za rješavanje raznih problema. Na primjer, svaki udžbenik više matematike sadrži stotine algoritama: sustavno rješenje linearne jednadžbe pronalaženje ekstrema funkcije, izračunavanje integrala itd. Međutim, nakon detaljnog ispitivanja njihove strukture, ispada da se svi algoritmi mogu podijeliti u nekoliko tipova. Razmotrite ove vrste algoritama s primjerima.

• linearno (izračun rezultata zbrajanja ili množenja, razmjena vrijednosti nekoliko varijabli);
• grananje (određivanje najvećeg od nekoliko brojeva);
• ciklički (sortiranje nizova, faktorski izračun).

To su osnovni tipovi. Također je vrijedno spomenuti da je u velikom broju literature istaknuta i četvrta vrsta - rekurzivna. No, ona nema posebnu oznaku u shematskom zapisu i provodi se kroz osnovne.

Više pojedinosti o svakom algoritmu izračuna s primjerima će biti opisano u nastavku.

Principi algoritma

1. Identificirajte izvorne podatke.
2. Odaberite rješenje.
3. Podijelite odabranu metodu na korake temeljene na mogućnostima računala (programski jezik).
4. Pokrenite algoritam u obliku sheme, definirajući jasan redoslijed koraka.
5. Prikazuje rezultate izračuna.
6. Označite prijelaz u izlazni krug.

Algoritam debugging

Osoba čini pogreške, a to je činjenica. Glavni parametar bilo kojeg algoritma trebao bi biti ispravnost njegova rada. Ispravljanje pogrešaka je proces identificiranja i ispravljanja pogrešaka algoritma. Da biste to učinili, uzmite određeni skup izvornih podataka, nazvan test. Oni su, u pravilu, sve vrste izvornih podataka. Na primjer, ako je unesen broj, algoritam treba provjeriti radi ispravnog rada, uzimajući u obzir: pozitivne, negativne, cjelobrojne i realne brojeve, nulte vrijednosti itd.

Glavni alat za provjeru točnosti algoritma ostaje ljudski mozak. Naravno, dopušteno je koristiti i druge računalne alate za automatizaciju provjere, ali na ovaj ili onaj način, osoba se bavi pripremom testova i analizom rezultata. U ovom slučaju, postavlja se pitanje, zašto nam je potreban algoritam ako osoba sve obavlja sam? Zatim, da je glavni zadatak algoritma višestruko rješenje određenog tipa problema.

Linearni algoritmi

Linearni algoritam je onaj u kojem koraci slijede jedan za drugim. Svaki algoritam koji ne sadrži grane i cikluse je linearan. Uzmimo primjer algoritma koji rješava sljedeći problem: vuk i zec sjede u dva kaveza, morate ih zamijeniti.

Ključ za rješavanje ovog problema je dodatna temp. Stanica, koja bi se trebala koristiti za zamjenu životinja.

Algoritmi grananja

Kao što ime implicira, algoritam ima nekoliko grana. Suština rada je odabrati jednu od mogućih varijanti računskog procesa, ovisno o bilo kojim uvjetima. Shematski razgranatost predstavljena je blokom u obliku dijamanta, unutar kojeg je naznačeno stanje, a na njegovim stranama su grane izbora, ovisno o tome je li uvjet istinit ili lažan. Algoritam grananja i primjeri njegove primjene mogu se naći posvuda. U programiranju je to tipičan if-else konstrukt, koji je na gotovo svakom jeziku.

Dajemo primjer algoritma za rješavanje problema pronalaženja najvećeg među tri broja.

Ciklički algoritam

Ciklično je algoritam u kojem se javljaju višestruka ponavljanja istih koraka, u kojima se može promijeniti samo vrijednost specifične varijable nad kojom se izračuni izrađuju. Tipovi cikličkog algoritma i primjera bit će razmotreni u nastavku, ali za sada ćemo navesti glavne korake za izgradnju ciklusa.

1. Dodjeljivanje početne vrijednosti varijabli. Bez ispunjenja ovog uvjeta, ciklus vjerojatno neće moći raditi ili će napraviti pogreške.
2. Jedinica izračunava rezultate. To je glavno tijelo ciklusa.
3. Provjerite krajnji uvjet cikličkog procesa. Ako zaboravite navesti uvjet pod kojim želite dovršiti ciklus, algoritam će raditi beskonačno.
4. Promijeni varijable Ovaj blok stupa na snagu nakon provjere uvjeta završetka, ako je laž. Ako zaboravimo na ovaj blok, ciklus će uvijek izvesti jednu radnju i nikada se neće završiti. Stoga je važno da varijable prolaze bilo kakve promjene na svakoj iteraciji petlje.

Postoji nekoliko vrsta cikličkih algoritama: s postkondicijom, preduvjetom i parametrom.

Konstruiramo ciklički algoritam na primjeru pronalaženja faktorijala N.

Ostale vrste algoritama

Postoji nekoliko algoritama koji se razlikuju u klasifikaciji ili podrijetlu.

• Mehanički algoritmi. Primjerice, rad motora s unutarnjim izgaranjem ili proizvodne trake.
• Probabilistički algoritmi. Njihov se rad temelji na teoriji vjerojatnosti i matematičkoj statistici.
• Heuristički algoritmi. Koristite praktična razmatranja u njihovom radu, bez strogog matematičkog opravdanja.
• Genetski algoritmi. Primijeniti biološke ideje u njihovom radu.

I drugima.