Vrste algoritama informatike. Algoritamske strukture (vrste algoritama). Verbalni način pisanja algoritama

Algoritam prikazan na slici 12 naziva se ciklički algoritam preduvjeta, budući da se stanje provjerava na početku petlje ili na ulazu u petlju. > x na ulazu u petlju. Ako je uvjet ispunjen, idite na blok 4, u suprotnom na blok 6.

U četvrtom bloku izračunava se vrijednost varijable na i= i+1 .

Peti blok prikazuje rezultat:

Promjenjiva vrijednost na,

i.

Primjer : Napravite blok dijagram primjera (slika 12), provjeravajući uvjete za izlaz iz petlje. U ovom primjeru uvjet zadatka se ne mijenja, a izlaz je isti, ali će dijagram toka biti drugačiji.

Riješenje : U tom slučaju provjerava se uvjet za izlazak iz petlje: y<=x ... Pod ovim uvjetom, petlja se ne izvršava. Uvjet u blok dijagramu treba premjestiti na kraj ciklusa, nakon što se ispiše. Ciklus se izvodi sve dok je uvjet zadovoljen y> x.

Algoritam se, ako se uvjet prenese na kraj ciklusa, zove algoritam petlje s postuslovom... Algoritam za ovaj problem prikazan je na Sl. 13.

Drugi blok predstavlja y=30 , x=4 .

Treći blok izračunava vrijednost varijable na , broji se broj dovršenih ciklusa i= i+1 .

Četvrti blok prikazuje rezultat:

Promjenjiva vrijednost na,

Broj izvedenih ciklusa i.

Peti blok provjerava stanje y <= x za izlaz iz petlje. Ako je uvjet ispunjen, tada se prelazi u blok 6, u suprotnom, u blok 3 i ciklus se ponavlja.

Slika 13. Algoritam petlje s postuslovom

Kontrolna pitanja

1. Pojam algoritma.

2. Vrste algoritama.

3. Osnovne algoritamske strukture.

4. Glavni blokovi grafičkog algoritma.

5. Linearna algoritamska struktura. Primjer.

6. Grananje. Primjer.

7. Ciklične algoritamske strukture. Primjer.

U praksi su sljedeći oblici predstavljanja algoritama najčešći:

· Verbalno (zapisi na prirodnom jeziku);

· Grafički (slike iz grafičkih simbola);

· Pseudokodovi (poluformalizirani opisi algoritama u uvjetnom algoritamskom jeziku, uključujući i elemente programskog jezika i izraze prirodnog jezika, općeprihvaćeni matematički zapis itd.);

· Softver (tekstovi na programskim jezicima).

Verbalni način Zapisi algoritama opis su uzastopnih faza obrade podataka. Algoritam je postavljen u slobodnom obliku na prirodnom jeziku. Na primjer. Zapišite algoritam za pronalaženje najvećeg zajedničkog djelitelja (GCD) dva prirodna broja.

Algoritam može biti sljedeći:

· Postavite dva broja;

Ako su brojevi jednaki, uzmite bilo koji od njih kao odgovor i zaustavite se na

u suprotnom, nastavite s izvršavanjem algoritma;

· Odredi veći broj;

· Zamijenite veći broj s razlikom između većeg i manjeg broja;

· Ponovite algoritam iz koraka 2.

Opisani algoritam primjenjiv je na sve prirodne brojeve i trebao bi dovesti do rješenja problema.

Verbalni način se ne koristi naširoko iz sljedećih razloga:

· Takvi opisi nisu strogo formalizirani;

· Pate od opsežnosti zapisa;

· Dopustiti nejasnoće u tumačenju pojedinih propisa.

Grafički način prikaz algoritama je kompaktniji i intuitivniji u usporedbi s verbalnim.

Ovaj grafički prikaz naziva se algoritamska shema ili blok dijagram.

U grafičkom prikazu, algoritam je prikazan kao niz međusobno povezanih funkcionalnih blokova, od kojih svaki odgovara izvršavanju jedne ili više radnji.

U blok dijagramu svaka vrsta radnje (unos početnih podataka, izračun vrijednosti izraza, uvjeti provjere, kontrola ponavljanja radnji, završetak obrade itd.) Odgovara geometrijskoj slici predstavljenoj kao simbol bloka. Simboli bloka povezani su prijelaznim linijama koje određuju redoslijed izvođenja radnji.

1) Početno-završni blok

Element prikazuje izlaz u vanjsko okruženje i ulaz iz vanjskog okruženja (najčešća upotreba je početak i kraj programa). Odgovarajuća radnja zabilježena je unutar slike.

2) Akcijski blok

Izvođenje jedne ili više operacija, obrada podataka bilo koje vrste (promjena vrijednosti podataka, oblika prezentacije, lokacije). Unutar slike same su operacije napisane izravno, na primjer, operacija dodjeljivanja: a = 10 * b + c

3) Logički blok

Prikazuje rješenje ili funkciju sklopnog tipa s jednim ulazom i dva ili više alternativnih izlaza, od kojih se samo jedan može odabrati nakon procjene uvjeta definiranih unutar ovog elementa. Unos u element označen je linijom, koja obično ulazi u gornji vrh elementa. Ako postoje dva ili tri izlaza, tada je obično svaki izlaz označen linijom koja izlazi iz preostalih vrhova (bočni i donji). Ako postoji više od tri izlaza, onda ih treba prikazati kao jednu liniju koja izlazi s vrha (češće s dna) elementa, koji se zatim grana. Odgovarajući rezultati izračuna mogu se zapisati pored redaka koji predstavljaju te staze. Primjeri rješenja: općenito - usporedba (tri izlaza:>,<, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).

Pretvaranje podataka u oblik prikladan za obradu (unos) ili prikaz rezultata obrade (izlaz). Ovaj simbol ne definira nosač podataka (posebni simboli koriste se za označavanje vrste nositelja podataka).

Vrste algoritama

Algoritam grananja je algoritam koji sadrži najmanje jedan uvjet, čija se provjera može izvršiti podjelom na nekoliko paralelnih grana algoritma.

Linearni algoritam je skup naredbi (uputa) koje se izvršavaju uzastopno u vremenu jedna za drugom.

Ciklički algoritam - algoritam koji omogućuje višestruko ponavljanje iste radnje (iste operacije) na novim izvornim podacima. Većina metoda izračuna, nabrajanje opcija svedene su na ciklične algoritme. Programski ciklus je niz naredbi (niz, tijelo petlje) koje se mogu izvršiti više puta (za nove početne podatke) sve dok se ne ispuni određeni uvjet.

Programiranje je pisanje nečim nepoznatim jezikom. Razvojem ovog područja znanja programeri su otišli još dalje i naučili zapisati "nešto", a da uopće nisu razumjeli kako zvuči na ruskom. Početnici uče pisati kôd izravno na C ++ ili php, koristeći mnoge biblioteke, i zapravo uopće ne razumiju kako ono što stvaraju zvuči na njihovom materinjem jeziku. Algoritmizacija se bavi pojašnjavanjem i dovođenjem do razumijevanja ovog "nečega".

Algoritmizacija

Većina primjera algoritama u računalnoj znanosti, čak i na sveučilištima, proučava se na osrednjoj razini. Uobičajena je praksa beskonačno pisati sve složeniji kod. Pokušaji neiskusnih programera da odmah počnu pisati programe na programskom jeziku mogu se usporediti s radom novinara koji, jedva ovladavši osnovama stranog jezika, piše članak za časopis. Takav problem možete izbjeći ako prvo počnete snimati svoje djelo na svom materinjem jeziku, urediti ga, provjeriti ima li pogrešaka i na kraju ga prevesti na traženi jezik.

Prednost ovog pristupa uglavnom leži u činjenici da će se programer baviti prevođenjem samo 25% vremena, dok će pri pisanju programa na novom jeziku potrošiti 100% na rad s nepoznatim jezikom. Istodobno, naći će se u skučenim uvjetima i neće moći dobro provjeriti greške i revidirati projekt.

Algoritmizacija pomaže pri provedbi projekta na računalu opisati proces rješenja na izvornom i razumljivom jeziku u obliku dijagrama međusobno povezanih algoritama, analizirati ideje i dobiti najkvalitetniji i promišljeni kod koji bit će otporniji na pogreške i učinkovitije će raditi.

Koncept algoritma

Računalo ne može riješiti probleme, može izvesti samo jednostavne radnje određenim redoslijedom. "Što je s kalkulatorom?" - pitaš. I to je plod rada programera koji su stvorili program koji koristi određene algoritme za postizanje željenih rezultata. Razmotrimo apstraktnu situaciju. Što biste trebali učiniti ako se od vas traži da pronađete korijene kvadratnog trinoma osobe koja nije upoznata s metodama rješavanja jednadžbi?

Očito ga je potrebno osposobiti za rješavanje kvadratnih jednadžbi. To se događa prema sljedećoj shemi:

1. Odaberite rješenje.
2. Proučite sve detalje odabrane metode.
3. Objasnite prve dvije točke budućem izvođaču na jeziku koji razumije.

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

Kako možete osigurati da će izvođač shvatiti ideje korištene u rješavanju problema na isti način na koji ga vi razumijete? Tu se približavamo konceptu algoritma. Praksa pokazuje da kako bi nekome nešto ispravno objasnili, potrebno je slijediti sljedeće korake:

• odrediti početne podatke (varijablu i koeficijente kvadratne jednadžbe);
• raščlaniti postupak rješenja na jedinstveno poznate komponente za izvođača (diskriminatorne formule i pronalaženje korijena);
• navedite redoslijed faza (prvo izračunajte diskriminator, zatim korijene);
• uspostaviti uvjet pod kojim se rješenje smatra potpunim (provjerite pronađene korijene zamjenjujući ih u jednadžbu umjesto varijabli);
• naznačiti što bi točno 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 način rješavanja zadatka, napisan pomoću određenih pravila koja omogućuju nedvosmisleno razumijevanje izvedenih radnji i njihovog redoslijeda. Algoritmi i primjeri zadataka bit će detaljnije razmotreni u nastavku.

Osnovna svojstva algoritma

Diskretnost. Postupak rješavanja problema uvijek se sastoji od radnji strogo odvojenih jedna od druge, nazvanih koraci, koji imaju određeni redoslijed izvođenja.

Sigurnost. Svaki korak trebao bi biti jasan i nedvosmislen i po značenju i po ključu radnje koju treba izvršiti.

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

Masovni lik. Svaki algoritam razvijen za rješavanje problema mora biti primjenjiv na sve probleme ove vrste za sve valjane ulazne podatke.

Mogućnosti računala

Za ispravno stvaranje algoritama za računala važno je razumjeti njihove mogućnosti. Razmotrimo najprije količine s kojima računalo radi. Općenito se mogu podijeliti na numeričke i tekstualne, konstante i varijable.

Stalni brojevi znače sve brojeve: 3,15, 100, 105, njihova je značajka nepromjenjivost tijekom cijelog rada programa. Promjenjive mijenjaju svoju vrijednost tijekom izvršavanja koda i obično se označavaju slovima: x, y, max, min itd.

Tekstualne varijable, poput numeričkih, mogu biti konstantne ili varijabilne. U prvom slučaju to je samo tekst: "dobro", "a i b" itd. U drugom je to ista simbolična oznaka kao i za numeričke varijable: ime, grad itd. Razlika među njima uglavnom je u memorija računala dodijeljena za pohranu takve varijable.

Radnje koje računalo može izvesti:

1. Očitavanje 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 skup ugrađenih funkcija.
3. Izlaz podataka (na zaslon, na papir, na mrežno sučelje).
4. Prijelaz između faza programa.
5. Usporedba dviju vrijednosti (veće, manje, jednake).

To su osnovne operacije koje većina programskih jezika može izvesti.

Metode za opisivanje algoritama

Verbalno. Ovo je najjednostavniji način. Primjer za to je kulinarski recept. Dopuštena je uporaba jednostavnih matematičkih formula.

Grafički. Opis pomoću dijagrama. Ovo je poseban način pisanja algoritama pomoću svojevrsnog općeprihvaćenog algoritamskog jezika - oblika i blokova koji imaju određeno značenje: pravokutnik je jednostavna radnja, kosi paralelogram je ulaz / izlaz, romb je uvjet itd.

Korištenje algoritamskog jezika. Slično grafičkom, također je poseban način pisanja algoritma. Dostupni su mnogi algoritamski jezici. Njihova pravila nisu stroga, inače bi to bio programski jezik. Razmotrimo primjer algoritma za izračunavanje plaća ovisno o dužini radnog staža, napisanog pomoću algoritamskog jezika.

Alg plaće (int ST, stvarni ZP) arg ST res ZP počinju ako ST

Algoritamski se jezik može nazvati strožim oblikom zapisa u odnosu na verbalni. Koristi se ograničen skup riječi i njihovih konstrukcija, kao i dizajn s uvlakama. Nedostatak verbalnog oblika i algoritamskog jezika je sve lošija jasnoća algoritma s povećanjem njegove veličine. Stoga se ove metode mogu koristiti samo za prenošenje značenja malih algoritama.

Vrste algoritama

Postoji veliki broj algoritama dizajniranih za rješavanje širokog spektra problema. Na primjer, svaki udžbenik više matematike sadrži stotine algoritama: rješavanje sustava linearnih jednadžbi, pronalaženje ekstrema funkcije, izračunavanje integrala itd. Međutim, nakon detaljnog ispitivanja njihove strukture, ispostavlja se da svi algoritmi mogu podijeliti u nekoliko vrsta. Razmotrimo ove vrste algoritama s primjerima.

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

To su osnovne vrste. Također je vrijedno napomenuti da u brojnoj literaturi postoji 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 bit će opisano u nastavku.

Principi algoritmizacije

1. Odredite izvorne podatke.
2. Odaberite rješenje.
3. Odabranu metodu podijelite u korake na temelju mogućnosti računala (programski jezik).
4. Izvedite algoritam u obliku dijagrama, definirajući jasan redoslijed koraka.
5. Izlazni rezultati izračuna.
6. Označite prijelaz na izlaz kruga.

Otklanjanje pogrešaka u algoritmu

Čovjek griješi, i to je činjenica. Glavni parametar bilo kojeg algoritma trebao bi biti ispravnost njegova rada. Otklanjanje pogrešaka je proces identificiranja i ispravljanja pogrešaka u algoritmu. Za to se uzima određeni skup početnih podataka, koji se nazivaju testni podaci. U pravilu su to sve vrste izvornih podataka. Na primjer, ako se na unos unese broj, tada treba provjeriti ispravan rad algoritma, uzimajući u obzir: pozitivne, negativne, cjelobrojne i stvarne brojeve, nulte vrijednosti itd.

Ljudski mozak ostaje glavni alat za provjeru točnosti algoritma. Naravno, dopušteno je koristiti druge računalne alate za automatizaciju provjere, ali na ovaj ili onaj način, osoba je koja priprema testove i analizira rezultate. U ovom slučaju postavlja se pitanje, zašto nam je potreban algoritam ako osoba sve radi sama? Zatim je glavni zadatak algoritma ponovljeno rješavanje određene vrste problema.

Linearni algoritmi

Linearni je algoritam u kojem su koraci uzastopni jedan za drugim. Svaki algoritam koji ne sadrži grane i petlje je linearan. Razmotrimo primjer algoritma koji rješava sljedeći problem: vuk i zec sjede u dvije ćelije, morate ih zamijeniti.

Ključ za rješavanje ovog problema je dodatni privremeni kavez koji bi se trebao koristiti za zamjenu životinja.

Algoritmi račvanja

Kao što naziv govori, algoritam ima nekoliko grana. Bit rada je odabir jedne od mogućih opcija za računalni proces, ovisno o bilo kojim uvjetima. Shematski grananje predstavljeno je kutijom u obliku dijamanta, unutar koje je naznačeno stanje, a na njenim stranama nalaze se grane za odabir ovisno o tome je li uvjet istinit ili lažan. Algoritam grananja i primjeri njegove primjene mogu se pronaći posvuda. U programiranju je ovo tipična konstrukcija if-else koja se nalazi u gotovo svakom jeziku.

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

Ciklički algoritam

Ciklički algoritam je algoritam u kojem se isti koraci ponavljaju mnogo puta, u kojem se može promijeniti samo vrijednost određene varijable, nad kojom se vrše izračuni. Vrste algoritma petlje i primjer bit će razmotreni u nastavku, ali za sada ćemo navesti glavne korake za izgradnju petlje.

1. Dodjeljivanje početne vrijednosti varijablama. Bez ovog uvjeta petlja će najvjerojatnije propasti ili pogriješiti.
2. Jedinica za izračunavanje rezultata. Ovo je glavno tijelo petlje.
3. Provjera uvjeta za završetak cikličkog procesa. Ako zaboravite navesti uvjet pod kojim bi petlja trebala završiti, algoritam će se raditi neograničeno dugo.
4. Promjena varijabli. Ovaj blok stupa na snagu nakon provjere uvjeta prekida ako je bio netočan. Ako zaboravite na ovaj blok, tada će ciklus izvoditi jednu radnju zauvijek i nikada se neće dovršiti. Stoga je važno da varijable dožive neke promjene pri svakoj iteraciji petlje.

Postoji nekoliko vrsta algoritama petlje: s postuslovom, preduvjetom i parametrom.

Konstruirajmo ciklički algoritam na primjeru pronalaska faktorijala broja N.

Druge vrste algoritama

Postoji niz drugih algoritama koji se razlikuju po klasifikaciji ili podrijetlu.

• Mehanički algoritmi. Na primjer, rad motora s unutarnjim izgaranjem ili montažne trake.
• Vjerojatni algoritmi. Njihov se rad temelji na teoriji vjerojatnosti i matematičkoj statistici.
• Heuristički algoritmi. U svom radu koristite praktična razmatranja, bez strogog matematičkog opravdanja.
• Genetski algoritmi. Primijeniti biološke ideje u svom radu.

Algoritmi mogu biti jednostavni, složeni, ali svi imaju zajedničke značajke. Prema tim značajkama uobičajeno je razlikovati tri vrste algoritama, s kojima ćemo se upoznati.

U algoritmima se naredbe pišu jedna za drugom određenim redoslijedom. Ne moraju se nužno izvoditi u snimljenom slijedu. Mogu postojati interne reference na različite timove.

Općenito, izvršavanje naredbi prema algoritmu donekle podsjeća na društvene igre u kojima se sudionici izmjenjuju bacajući kockice i hodajući po poljima. Štoviše, na marginama mogu postojati komentari u stilu: "Idi 2 ćelije natrag" ili "Idi 5 ćelija naprijed" (slika 1).

Riža. 1. Društvena igra ()

Poznata igra "Monopoly" ili "Manager" složeniji je model izvođenja algoritma (slika 2).

Riža. 2. Igra "Monopol" ()

Bitna razlika između ove igre i jednostavnog izvođenja algoritma je u tome što konačni cilj sudionika nije prijeći put, već skupljati novac kroz određene radnje.

Ovisno o redoslijedu izvršavanja naredbi, mogu se razlikovati tri vrste algoritama:

Linearni algoritmi;

Algoritmi grananja;

Algoritmi ponavljanja.

"Monopol"

Monopol je jedna od najpopularnijih društvenih igara. Njegova su pravila prilično jednostavna i razumljiva svima koji su ga barem jednom igrali (slika 4).

Riža. 4. Igra "Monopol" ()

U trenutku početka igrači imaju jednaku količinu gotovine. Bacajući kockice i pomičući svoje žetone po petljastom igralištu, stječu nekretnine u mnogo različitih boja. Nakon što je neprijatelj došao na web mjesto, igrač je dužan platiti utvrđenu stanarinu. Nakon što je kupio sve parcele iste skupine boja, sudionik može na njima izgraditi kuće i hotele, što povećava veličinu najma. Cilj svega što se događa je banalan - uništiti sve suparnike.

Prema službenim izvorima - Parker Brothers, koji proizvodi Monopoly od 1935. do danas - legendarna društvena igra rođena je na sljedeći način. Godine 1934. nezaposleni inženjer Charles Darrow (slika 5) ponudio je gore navedenom uredu da objavi igru ​​koju je izumio o trgovini nekretninama.

Riža. 5. Charles Darrow ()

Otkrivši 52 greške u dizajnu u društvenoj igri, braća Parker odbila su izumitelja. On je, čisto američkog poduzetničkog duha, otišao u tiskaru, naručio 5 tisuća primjeraka igre i prilično ih brzo rasprodao. Shvativši da im profit izmiče iz nosa, Parker Brothers žurno je stekao prava na Monopoly, a sljedeće je godine postala najprodavanija društvena igra u Sjedinjenim Državama, a Darrow - živo utjelovljenje američkog sna.

Međutim, u isto vrijeme, poznate su i ranije igre koje upečatljivo podsjećaju na "Monopoly". Ispostavilo se da je Darrow tek prvi požurio i dobio patent za "narodnu" zabavu? Da i ne. Istrage posljednjih godina rasvijetlile su misteriju podrijetla Monopolyja.

U drugoj polovici devetnaestog stoljeća politički ekonomist Henry George živio je i radio u Sjedinjenim Državama. Predložio je zamjenu svih nameta jednim porezom - na zemljište. Prožeta njegovim idejama, u siječnju 1904. Maggie je dobila patent za društvenu igru ​​The Landlord's Game, koja i po pravilima i po izgledu podsjeća na trenutni "Monopol". Vjeruje se da je "Igra vlasnika zemlje" imala dvije varijante pravila: igrajući igru ​​prema važećim zakonima o oporezivanju, igrači su prešli na model koji je predložio George - i navodno su se uvjerili da je to potrebno prednosti. Dakle, igra nije bila zabava, već instrument ideološke borbe.

Nije došlo do masovne proizvodnje, ali se The Landlord's Game postupno proširila Sjevernom Amerikom u rukotvorinama. Nalet interesa za društvenu igru ​​pao je u godinama Velike depresije: tisuće nezaposlenih ljudi rado su se zamišljali kao vreće novca, barem za stolom za kockanje. Pojava poduzetnog čovjeka poput Charlesa Darrowa potrajala je nekoliko mjeseci - i došao je, mnogo desetljeća preuzevši slavu jedinog izumitelja "Monopola".

Bilo je, naravno, i onih koji su smatrali da je potrebno vlasnicima autorskih prava oteti komad. Monopoli bez licence preplavili su Kinu. A kod nas su se proizvodili i proizvode vitki redovi klonova - "Posrednik", "Zadruga", "Upravitelj" (slika 6) ...

Riža. 6. Igra "Upravitelj" ()

U svjetlu nedavnog preispitivanja Darrowove uloge u stvaranju Monopola i isteka autorskih prava, takve tvrtke neće biti tužene. Čak i ako pretpostavimo da na svijetu nije bilo Elizabeth Maggie, pravila "Monopola" odavno su prešla u javnu domenu. Međutim, Hasbro i dalje zadržava dio patenta kod sebe: dizajn čipova, grafički dizajn, slijed ćelija na igralištu.

Algoritam u kojem se naredbe izvršavaju redoslijedom njihova pisanja, to jest uzastopno jedna za drugom, naziva se linearni.

Riža. 3. Sijalica ()

Na primjer, sljedeći algoritam za zamjenu izgorjele žarulje je linearan (slika 3):

1. isključite prekidač svjetla;

2. odvrnite izgorjelu žarulju;

3. uvrnite novu žarulju;

4. Uključite prekidač da provjerite je li svjetlo upaljeno.

Pomoću blok dijagrama ovaj algoritam se može prikazati na sljedeći način:

(dijagram toka (slika 7.) vidi na kraju sinopsisa)

Izuzetno su rijetke situacije u kojima je unaprijed poznat slijed potrebnih radnji. U životu često morate donositi odluku ovisno o trenutnoj situaciji. Ako pada kiša, uzimamo kišobran i oblačimo kabanicu; ako je vruće, nosite laganu odjeću. Postoje i složeniji uvjeti odabira. U nekim slučajevima sudbina osobe ovisi o odabranoj odluci.

Logika odlučivanja može se opisati na sljedeći način:

AKO<условие>, ONDA<действия 1>,

INAČE<действия 2>

AKO imate novaca, ONDA kupujte kruh, NE KUPITE GA DRUGI.

AKO ćete danas biti u centru, tada me pozovite, OSTALO nemojte.

AKO su lekcije naučene, ONDA idite u šetnju, OSTALO naučite lekcije.

U nekim slučajevima<действия 2>može biti odsutan. To može biti posljedica i njegove očiglednosti (kao što je, na primjer, u prvom primjeru - jasno je da ako nemate novca, onda jednostavno ne možete kupiti kruh), i nedostatka potrebe za njim.

AKO<условие>, ONDA<действия 1>

AKO se nazvao teretom, onda se popnite straga.

AKO želite biti zdravi, budite raspoloženi.

Oblik organizacije radnji u kojem se, ovisno o ispunjenosti ili neispunjenosti određenog uvjeta, izvodi jedan ili drugi slijed radnji, naziva se grananje.

Prikažimo u obliku dijagrama toka slijed radnji učenika 6. razreda koji je zaboravio ključeve od stana, a koji zamišlja na sljedeći način: „Ako je moja majka kod kuće, doći ću i sjesti da to učinim moja domaća zadaća. Ako mama nije kod kuće, ići ću igrati nogomet sa svojim prijateljima dok mama ne dođe. Ako nema prijatelja na ulici, onda ću se voziti ljuljačkom dok mi ne dođe majka. "

(dijagram toka (slika 8.) vidi na kraju sinopsisa)

Potrebni i dovoljni uvjeti

Već smo razgovarali s vama da postoje potrebni i dovoljni uvjeti.

Primjer preduvjeta bio bi:

Da biste postali liječnik, morate završiti medicinski stupanj.

Uvjet da imate medicinsko obrazovanje nužan je za rad kao liječnik, ali nije dovoljan. Doista, svi diplomirani medicinari ne postaju liječnici.

Primjer dovoljnog uvjeta bio bi:

Da biste se ohladili, samo uključite klima uređaj.

Ovaj uvjet je dovoljan: ako uključite klima uređaj, doista će se ohladiti. Međutim, ovaj uvjet nije nužan, jer za postizanje ovog cilja možete uključiti ventilator, otvoriti prozor itd.

Naravno, postoje i potrebni i dovoljni uvjeti u isto vrijeme (takvi uvjeti se nazivaju ravno). Na primjer:

Da bi došlo ljeto, potrebno je i dovoljno da završi proljeće.

Doista, ako je proljeće prošlo, onda dolazi ljeto, a ako proljeće nije završilo, onda ljeto ne može doći. Odnosno, uvjeti za kraj proljeća i početak ljeta su ekvivalentni.

Koncepti nužnih, dovoljnih i ekvivalentnih uvjeta vrlo su važni u takvoj grani matematike kao što je matematička logika. Osim toga, vrlo su česti u dokazivanju raznih teorema.

U praksi često postoje zadaci u kojima je potrebno nekoliko puta ponoviti jednu ili više radnji, dok je ispunjen neki prethodno utvrđeni uvjet.

Na primjer, ako trebate sortirati kutiju jabuka kako biste odvojili trule od zrelih, moramo ponoviti sljedeće korake:

1. Uzmi jabuku.

2. Provjerite je li pokvaren.

3. Ako je pokvaren - bacite ga, ako nije - prenesite ga u drugu kutiju.

Ovaj skup radnji potrebno je provoditi dok se jabuke u kutiji ne potroše.

Oblik organizacije radnji u kojem se ponavlja izvršenje istog niza radnji dok je ispunjen određeni unaprijed određeni uvjet naziva se ciklus (ponavljanje).

Zove se situacija u kojoj se izvršavanje petlje nikada ne završava petljanje.

Algoritme treba razviti kako bi se izbjegle takve situacije.

Razmotrite algoritam za budilicu na telefonu koja bi trebala zvoniti u 8:00 ujutro, a zatim zvoniti svakih 10 minuta dok se ne isključi.

U ovom slučaju njegov blok dijagram izgleda ovako: (blok dijagram (slika 9.) vidi na kraju sinopsisa)

U ovoj lekciji smo raspravljali o tri vrste algoritama - linearnim algoritmima, algoritmima grananja i algoritmima koji se ponavljaju.

U sljedećoj lekciji ćemo razgovarati o tome kako napisati algoritme u praksi.

Eratostenovo sito

Prisjetimo se definicije prosteg prirodnog broja.

Prirodan broj naziva se prost ako jest ima samo dva djelitelja: jedan i sam broj. Ostatak brojeva se naziva sastavni... Štoviše, broj 1 nije ni jednostavan ni složen.

Primjeri prostih brojeva: 2, 3, 5, 7.

Primjeri složenih brojeva: 4, 6, 8.

U 3. stoljeću prije Krista grčki matematičar Eratos-phene predložio je sljedeći algoritam za pronalaženje svih prostih brojeva manjih od zadanog broja NS:

1.ispišite sve prirodne brojeve od 1 do n;

2. brisati 1;

3. podcrtaj najmanji od neoznačenih brojeva;

4. Precrtajte sve brojeve koji su višekratnici broja podcrtanog u prethodnom koraku;

5. ako popis sadrži neoznačene brojeve, prijeđite na korak 3, inače su svi podcrtani brojevi prosti.

Ovo je ciklički algoritam. Kada se izvrši, koraci 3-5 se ponavljaju sve dok na izvornom popisu nema neoznačenih brojeva.

Razmotrimo rezultat ovog algoritma. Zapišimo sve proste brojeve od 1 do 25.

Zapišimo brojeve od 1 do 25.

Izbrišimo 1. Sada ćemo naglasiti dva. Precrtajte sve parne brojeve.

Budući da nisu svi brojevi označeni, podcrtajte 3. Sada prekrižite sve brojeve koji su djeljivi s 3.

Budući da nisu svi brojevi označeni, podcrtajte 5. Sada prekrižite broj 25.

Budući da nisu označeni svi brojevi, naglašavamo 7.

Ne možete ništa precrtati, ali nisu svi brojevi označeni pa naglašavamo 11.

Ne možete ništa precrtati, ali nisu svi brojevi označeni, pa naglašavamo 13. Opet, ne možemo ništa precrtati - podcrtavamo 17, zatim 19 i 23.

Svi su brojevi sada označeni.

Dobivamo proste brojeve: 2, 3, 5, 7, 11, 13, 17, 19, 23.

Riža. 7.Blok dijagram za promjenu žarulje

Riža. 8. Dijagram toka radnji učenika šestog razreda

Riža. 9. Blok dijagram budilice

Bibliografija

1. Bosova L.L. Informatika i ICT: Udžbenik za 6. razred. - M.: BINOM. Laboratorij znanja, 2012.

2. Bosova L.L. Informatika: Radna bilježnica za 6. razred. - M.: BINOM. Laboratorij znanja, 2010.

3. Bosova L.L., Bosova A.Yu. Satovi informatike u 5-6 razredima: Metodičko uputstvo. - M.: BINOM. Laboratorij znanja, 2010.

1. Internetski portal "Naša mreža" ()

2. Internetski portal "Hipermarket znanja" ()

3. Internetski portal "kaz.docdat.com" ()

Domaća zadaća

1. §3.4 (Bosova L.L. Informatika i ICT: Udžbenik za 6. razred).

2. Stranica 81 zadatak 2, 6 (Bosova L.L. Informatika i ICT: Udžbenik za 6. razred).

3. Stranica 82 zadatak 9, 11, 13, 14 (Bosova L.L Informatika i ICT: Udžbenik za 6. razred).

4. * Stranica 83 zadatak 15 (Bosova L.L. Informatika i ICT: Udžbenik za 6. razred).