Linearni prikaz algoritma. Vrste algoritama: linearni, granajući, ciklični. Metode za opisivanje algoritama

Petlja s preduvjetom

U okviru strukturirano programiranje problemi s algoritamskim rješenjem mogu se opisati na sljedeći način algoritamske strukture:

• Slijedeći... Pretpostavlja uzastopno izvršavanje naredbi odozgo prema dolje. Ako se algoritam sastoji samo od sukcesivnih struktura, onda je linearan.
• Grananje... Izvođenje program ide jedna od dvije, nekoliko ili više grana. Izbor grane ovisi o stanju na ulazu grane i podacima koji se ovdje primaju.
• Ciklus... Pretpostavlja mogućnost ponavljanja određenih radnji. Broj ponavljanja ovisi o stanju ciklusa.
• Funkcija (potprogram)... Naredbe odvojene od glavnog programa izvršavaju se samo ako su pozvane iz glavnog programa (s bilo kojeg mjesta u njemu). Ista se funkcija može pozvati iz glavnog programa neograničeni broj puta.

Opis različitih algoritamskih struktura na jeziku blok dijagrama

Grananje ako
Ovo je najjednostavniji tip grananja. Ako rezultat vrednovanja uvjetnog izraza vrati vrijednost true, izvršavanje algoritma ide duž grane "Da", koja uključuje dodatne izraze radnji. Ako uvjet vrati vrijednost false, izvršavanje algoritma ide duž grane "ne", odnosno glavna grana programa nastavlja se izvršavati.

Grananje if-else
Ako izraz uvjeta vrati vrijednost true, tada izvršavanje algoritma ide duž grane "Da", ako uvjet nije ispunjen (netočno), tada izvršenje ide uz granu "Ne". Za bilo koji rezultat uvjetnog izraza nemoguće je vratiti se na glavnu granu programa zaobilazeći dodatne korake.

Grananje if-elif-else
Broj uvjeta može biti različit. Ako se prva izvrši, program se nakon izvođenja radnji prebacuje na glavnu granu bez provjere daljnjih uvjeta. Ako prvi uvjet vrati vrijednost false, provjerava se drugi uvjet. Ako se drugi uvjet vrati točno, tada se izvršavaju radnje uključene u drugu granu konstrukcije. Posljednji uvjet provjerava se samo ako nijedan od uvjeta prije nego što se vratio nije istinit. Ovu algoritamsku konstrukciju (ako - elif - drugo) ne treba miješati s algoritmskom konstrukcijom izbora.

Dok petlja
Dok je uvjet ispunjen (rezultat logički izraz daje true), radnje tijela petlje će se izvršiti. Nakon sljedećeg izvođenja ugniježđenih radnji, uvjet se ponovno provjerava. Kako se izvršavanje algoritma ne bi petljalo, u tijelu petlje (između ostalih radnji) mora postojati izraz, uslijed čega će se promijeniti varijabla korištena u uvjetu. Tijelo petlje možda se nikada neće izvršiti ako je uvjet od samog početka bio lažan.

Do petlje
U ovoj petlji uvjet se prvi put provjerava tek nakon što su izvedene radnje tijela petlje. Ako se uvjet vrati istina, tada se izrazi radnji ponovno ponavljaju. Bez obzira na uvjete, tijelo ovog ciklusa bit će izvedeno barem jednom.

Za petlju
Ova petlja se naziva i "for" petlja. Njegov naslov označava tri parametra: početnu vrijednost varijable (od), naravno vrijednost (do) i njezinu promjenu pomoću aritmetička operacija pri svakom "okretanju" ciklusa (korak).

>> Vrste algoritama

U algoritmima se naredbe pišu jedna za drugom određenim redoslijedom. Ne moraju se nužno izvršavati u snimljenom slijedu: ovisno o redoslijedu izvođenja naredbi, mogu se razlikovati tri vrste algoritama:

Linearni algoritmi;
algoritmi grananja;
algoritmi s ponavljanjima.

Linearni algoritmi

U kojim se naredbama izvršava redoslijedom kojim su napisane, to jest uzastopno jedna za drugom, naziva se linearno.

Na primjer, sljedeći algoritam sadnje stabala je linearan:

1) iskopati rupu u zemlji;
2) spustite sadnicu u rupu;
3) rupu sa sadnicom napuniti zemljom;
4) zalijte sadnicu vodom.

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

Algoritmi grananja

Izuzetno su rijetke situacije u kojima je unaprijed poznat slijed potrebnih radnji. U životu često morate donositi odluku ovisno o prevladavajućoj 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<условие>ZATIM<действия 1>INAČE<действия 2>

Primjeri:

AKO to želiš biti zdrav, ONDA budite temperirani, U protivnom ćete cijeli dan ležati na kauču;
AKO lastavice lete nisko, ONDA će padati kiša, OSTALO neće padati kiša;
AKO su lekcije naučene, ONDA idite u šetnju, OSTALO naučite lekcije.

U nekim slučajevima<действия 2>može biti odsutan;

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

Primjer:

AKO se nazvao teretom, onda se popnite straga.

Oblik organizacije radnji u kojem se, ovisno o ispunjenosti određenog uvjeta, vrši jedno ili drugo potpored koraci naziva se grananje.

Prikažimo u obliku dijagrama toka slijed radnji učenika 6. razreda Vasye Mukhina, koji on zamišlja na sljedeći način: "Ako je Pavlik kod kuće, riješit ćemo zadatke iz matematike. U protivnom bismo trebali nazvati Marinu i pripremiti biološki izvještaj zajedno. Ako Marina nije kod kuće, morate sjesti na esej. "

I tako, uz pomoć blok dijagrama, možete vrlo jasno prikazati obrazloženje pri rješavanju sljedećeg problema.

Od tri kovanice istog apoena, jedan je krivotvoren (upaljač). Kako ga pronaći pomoću vage na vagi bez utega?

Algoritmi ponavljanja

U praksi često postoje zadaci u kojima se jedna ili više radnji mora ponoviti nekoliko puta, dok je ispunjen određeni unaprijed određeni uvjet.

Algoritam koji sadrži ciklusa naziva se ponavljajući algoritam ili algoritam koji se ponavlja.

Situacija u kojoj se izvršavanje petlje nikada ne završava naziva se beskonačna petlja. Kako bi se izbjegle takve situacije, treba razviti algoritme.

Pogledajmo primjer iz matematike.

Prirodan broj naziva se prostim ako ima samo dva djelitelja: jedan i sam broj1.

2, 3, 5, 7 - prosti brojevi; 4, 6, 8 - ne. U 3. stoljeću prije Krista grčki matematičar Eratosten predložio je sljedeći algoritam za pronalaženje svih prostih brojeva manjih od danog broja n:

1) ispišite sve prirodne brojeve od 1 do n;
2) izbrisati 1;
3) podcrtaj najmanji od neoznačenih brojeva;
4) precrtajte sve brojeve koji su višekratnici 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. Kad se izvrši, koraci 3-5 se ponavljaju sve dok na izvornom popisu nema neoznačenih brojeva.

Ovako izgleda dijagram postupaka školarca, što bi trebalo učiniti prije večernje šetnje domaća zadaća matematika:

Podsjetimo se da broj 1 nije niti složeni broj (koji ima više od dva djelitelja) niti prost broj.

Najvažnija stvar

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

> linearni algoritmi;
> algoritmi grananja;
> algoritmi ponavljanja.

Algoritam u kojem se naredbe izvršavaju redoslijedom kojim su napisane, odnosno uzastopno jedna za drugom, naziva se linearnim.

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

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

Pitanja i zadaci

1. Koji se algoritmi nazivaju linearnim?
2. Navedite primjer linearnog algoritma,
3. Izvođač "Kalkulator" može izvršiti samo dvije naredbe: pomnožiti s 2 i zbrajati. Dođite do najkraćeg plana za izvlačenje broja 50 iz O.
4. Koji se oblik organizacije radnji naziva grananjem?
5. Koje je uvjete morala ispuniti junakinja priče "Guske-labudovi"?
6. Navedite primjer algoritma koji sadrži grananje "
7. Pročitaj ulomak iz pjesme J. Rodarija "Kako zanati mirišu?":

Svaki slučaj ima poseban miris:
Pekara miriše na tijesto i peciva.
Prolazite pored stolarske radionice -
Miriše na strugotine i svježu dasku.
Slikar miriše na terpentin i boju.
Staklar miriše na kit za prozore.
Vozačeva jakna miriše na benzin
Radnička bluza - strojno ulje.

Preformulirajteo zanimanjima koristeći riječi "AKO ... ONDA" /

8. Sjetite se junaka čije ruske narodne priče donose odluke koje određuju njihovu sudbinu.
9. Od 9 kovanica istog apoena, jedan je lažni (upaljač). Koliko vaganja na vagi bez utega možete odrediti?
10. Koji se oblik organizacije radnji naziva ponavljanjem?
11. Navedite primjer algoritma koji sadrži ponavljanje.
12. U kojim vam se poznatim književnim djelima događa ciklički oblik organizacije radnji?
13. Gdje će izvođač koji je završio sljedeću skupinu timova 16 puta zaredom?

hodati 10 metara naprijed

okrenite 90 ° u smjeru kazaljke na satu

14. Koju skupinu radnji i koliko puta treba ponoviti pri rješavanju sljedećeg problema?

Četrdeset vojnika prišlo je rijeci, uz koju dva dječaka jašu u čamcu. Kako vojnici mogu prijeći na drugu stranu, ako čamac može držati samo jednog vojnika ili dva dječaka, ali vojnik i dječak više ne mogu?

15. Prisjetite se problema kalkulatora koji može samo pomnožiti s 2 i zbrajati 1. Bit će mnogo lakše razviti racionalne algoritme za njega ako koristite sljedeći blok dijagram:

Pomoću ovog dijagrama toka razvijte racionalne algoritme za dobivanje brojeva 1024 i 500 iz broja 0.

Bosova L. L. Informatika: Udžbenik za 6. razred / L. L. Bosova. - 3. izd., Rev. i dodati. - M.: BINOM. Laboratorij znanja, 2005. - 208 str: ilustr.

Za pisanje algoritama, zajedno s prirodnim ili matematičkim jezikom, prikladno je koristiti jezik blok dijagrama. Blok dijagram je grafički prikaz algoritma u kojem je svaka faza procesa obrade podataka prikazana u obliku geometrijskog lika fiksnog tipa, koji se naziva simbol. Simboli su povezani linijama koje označavaju smjer protoka informacija. Svaki simbol sadrži opis odgovarajuće faze obrade podataka. Ako je opis glomazan, bilježi se zasebno kao komentar. Glavni simboli prikazani su u tablici.

Simboli su povezani komunikacijskim linijama. Točka se stavlja na mjesto spajanja simbola. Simboli se mogu numerirati kako bi se olakšalo prikazivanje veza tamo gdje se krug prekida. Ti brojevi ne određuju redoslijed izvođenja algoritma, ovisno samo o linijama koje povezuju tokove.

Svi algoritmi podijeljeni su po svojoj strukturi na tri grupe:

Linearno;

Grananje;

Ciklički.

Algoritam koji ne sadrži uvjete naziva se linearnim. Ovaj algoritam bezuvjetno određuje proces transformacije podataka. Primjer takvog algoritma je korak-po-korak izračun matematičke formule. Svaka elementarna operacija izvodi se redoslijedom utvrđenim pravilima izračuna bez analize prethodno dobivenog rezultata. Blok dijagram linearnog algoritma je uzastopni niz znakova "postupak", koji ima oblik pravokutnika, dopunjen simbolima "ulaz izlaz" i "Start-end".

Riža. 8. Blok dijagram linearnog algoritma

Račvanje algoritam sadrži barem jedan uvjet. Za implementaciju algoritma grananja koristi se tipična struktura BRANCHING. Algoritam grananja temelji se na logičkom elementu uvjeta, predstavljenom na dijagramu simbolom ROMB. U logičkom elementu provjerava se uvjet koji daje rezultat DA ili NE. Ovisno o tome, tok informacija usmjeren je duž jednog od dva izlazna kanala logičkog elementa.

Ovaj algoritam može imati dvije mogućnosti:

1. Ako je uvjet ispunjen, tada se tok informacija šalje u blok računskog procesa za koji je uvjet provjeren; ako uvjet nije ispunjen, tok informacija se usmjerava na sljedeće elemente dijagrama toka. Tako, logički dijagram može se napisati kao IF (uvjet) - THEN (formula).

2. Postoje DVA FORMULA izračuna, a algoritam radi prema sljedećem logičkom principu: IF (uvjet) - ONDA (formula 1), ELSE (formula 2).

Ako trebate provjeriti nekoliko uvjeta, tada algoritam ima oblik "stabla" s granama u obliku "grana". Broj logičkih elemenata uvijek je jedan manji od broja uvjeta, budući da svaki element ima jedan ulaz i dva izlaza. Dio algoritma prije grananja se naziva barel, stanje - grananje, alternativni pravci procesa računanja nakon točke grananja - grane.

Slika 9. Dijagrami toka algoritama račvanja

Takav se algoritam naziva cikličkim, neke od radnji u kojima se ponavljaju nekoliko puta. Takve se radnje koje se ponavljaju nazivaju "ciklusom". Ciklički algoritmi sadrže radne uvjete ciklusa, pa se mogu smatrati svojevrsnim algoritmima grananja, u kojima je jedna od grana dio debla, što se ponavlja nekoliko puta. Ove radnje koje se ponavljaju čine ciklus.

Ciklički algoritmi se dijele na dvije vrste:

S poznatim brojem ponavljanja (ciklusa)

Iteracijski algoritmi u kojima broj ciklusa nije unaprijed poznat, a kraj ciklusa određen je nekim uvjetom (uglavnom zadanom računskom točnošću).

Razmotrimo obje vrste algoritama.