Vrste algoritama - Hipermarket znanja. B6

Ključne riječi:

algoritam
svojstva algoritma
- diskretnost
- jasnoća
- sigurnost
- efektivnost
- masovni karakter
izvršilac

karakteristike izvođača
- niz zadataka koje treba riješiti
- srijeda
- režim rada
- komandni sistem
formalno izvršenje algoritma

3.1.1. Koncept algoritma

Svaka osoba u svakodnevnom životu, na studiju ili na poslu rješava ogroman broj problema različite složenosti. Složeni problemi zahtijevaju puno razmišljanja da bi se pronašlo rješenje; Čovjek bez razmišljanja rješava jednostavne i poznate zadatke automatski. U većini slučajeva, rješenje svakog problema može se podijeliti u jednostavne faze (korake). Za mnoge od ovih zadataka (instaliranje softvera, sastavljanje ormara, kreiranje web stranice, rukovanje tehničkim uređajem, kupovina avio karte putem interneta, itd.) već su razvijena i ponuđena uputstva korak po korak, sekvencijalna čija implementacija može dovesti do željenog rezultata.

Primjer 1. Zadatak „Pronađi aritmetičku sredinu dva broja“ rješava se u tri koraka:

razmislite o dva broja;
dodati dva broja na umu;
dobijeni iznos podijelite sa 2.

Primjer 2. Zadatak "Uplatite novac na svoj telefonski račun" podijeljen je u sljedeće korake:

idite na terminal za plaćanje;
odaberite telekom operatera;
unesite broj telefona;
provjerite da li je uneseni broj tačan;
ubacite novčanicu u akceptor novčanica;
pričekajte poruku o prilivu novca na vaš račun;
primiti ček.

Primjer 3. Faze rješavanja problema "Nacrtaj smiješnog ježa" prikazane su grafički:

Pronalaženje aritmetičke sredine, uplata novca na telefonski račun i izvlačenje ježa su na prvi pogled potpuno različiti procesi. Ali oni imaju zajedničku osobinu: svaki od ovih procesa opisan je nizom kratkih uputa, striktno pridržavanje kojih vam omogućava da dobijete traženi rezultat. Sekvence instrukcija date u primjerima 1-3 su algoritmi za rješavanje odgovarajućih problema. Izvršilac ovih algoritama je osoba.

Algoritam može biti opis određenog niza proračuna (primjer 1) ili koraka nematematičke prirode (primjeri 2-3). Ali u svakom slučaju, prije njegovog razvoja moraju biti jasno definirani početni uslovi (početni podaci) i ono što se želi dobiti (rezultat). Možemo reći da je algoritam opis slijeda koraka u rješavanju problema, koji vodi od početnih podataka do traženog rezultata.

Općenito, dijagram rada algoritma može se predstaviti na sljedeći način (slika 3.1):

Rice. 3.1.
Opća šema algoritma

Algoritmi su pravila sabiranja, oduzimanja, množenja i dijeljenja brojeva, gramatička pravila, pravila geometrijskih konstrukcija itd. koja se izučavaju u školi.

Animacije “Rad s algoritmom”, “Najveći zajednički djelitelj”, “Najmanji zajednički višekratnik” (http://school-collection.edu.ru/) pomoći će vam da zapamtite neke algoritme koji se izučavaju na časovima ruskog jezika i matematike.

Primjer 4. Neki algoritam dovodi do činjenice da se iz jednog lanca znakova dobiva novi lanac na sljedeći način:

Izračunava se dužina (u znakovima) izvornog niza znakova.
Ako je dužina originalnog lanca neparna, tada se originalnom lancu s desne strane dodaje broj 1, inače se lanac ne mijenja.
Simboli se zamjenjuju u parovima (prvi sa drugim, treći sa četvrtim, peti sa šestim, itd.).
Broj 2 se dodaje desno od rezultirajućeg lanca.

Rezultirajući lanac je rezultat algoritma.

Dakle, ako je početni lanac bio A#B, onda će rezultat algoritma biti lanac #A1B2, a ako je početni lanac bio ABC@, onda će rezultat algoritma biti lanac BA@B2.

3.1.2. Algoritam executor

Svaki algoritam je dizajniran za određenog izvođača.

Postoje formalni i neformalni izvođači. Formalni izvođač uvijek izvodi istu komandu na isti način. Neformalni izvršilac može izvršiti naredbu na različite načine.

Razmotrimo detaljnije skup formalnih izvođača. Formalni izvođači su izuzetno raznoliki, ali se za svakog od njih mogu navesti sljedeće karakteristike: opseg zadataka koji se rješavaju (svrha), okruženje, sistem komandovanja i način rada.

Raspon zadataka koje treba riješiti. Svaki izvođač je stvoren za rješavanje određenog niza problema - konstruiranje lanaca simbola, izvođenje proračuna, konstruiranje crteža na ravni, itd.

Artist Environment. Područje, okruženje, uslovi u kojima izvođač djeluje obično se nazivaju okruženjem datog izvođača. Izvorni podaci i rezultati bilo kojeg algoritma uvijek pripadaju okruženju izvođača kojem je algoritam namijenjen.

Sistem komandi izvršioca. Instrukcija izvođaču da izvrši zasebnu završenu radnju naziva se komanda. Skup svih naredbi koje može izvršiti neki izvršilac čini sistem komandi za ovaj izvršilac (SKI). Algoritam se sastavlja uzimajući u obzir mogućnosti određenog izvođača, drugim riječima, u sistemu komandi izvođača koji će ga izvršiti.

Performerski režimi rada. Za većinu izvođača omogućeni su načini direktne kontrole i programske kontrole. U prvom slučaju, izvođač čeka naredbe od osobe i odmah izvršava svaku primljenu komandu. U drugom slučaju, izvođaču se prvo daje kompletan niz naredbi (program), a zatim sve te komande izvršava automatski. Jedan broj izvođača radi samo u jednom od navedenih načina.

Pogledajmo primjere izvođača.

Primjer 5. Izvođač Kornjača se kreće po ekranu računara, ostavljajući trag u obliku linije. Komandni sistem Kornjače sastoji se od dvije komande:

Desno m (gdje je m cijeli broj) - uzrokuje promjenu smjera kretanja Kornjače za m stupnjeva u smjeru kazaljke na satu.

Ponavljanje snimanja k [<Команда1> <Команда2> ... <Командаn>] znači da će se niz naredbi u zagradama ponoviti k puta.

Razmislite koja će se figura pojaviti na ekranu nakon što Kornjača završi sljedeći algoritam.

Ponovite 12 [Desno 4 5 Naprijed 20 Desno 45]

Primjer 6. Sistem izvršnih komandi Računar se sastoji od dve komande, kojima se dodeljuju brojevi:

Prvi od njih smanjuje broj za 1, drugi povećava broj za 3 puta. Prilikom pisanja algoritama, radi sažetosti, naznačeni su samo brojevi komandi. Na primjer, algoritam 21212 znači sljedeći niz naredbi:

Koristeći ovaj algoritam, broj 1 će se pretvoriti u 15: ((1-3-1)-3-1)-3 = 15.

Primjer 7. Performer Robot radi na kariranom polju, između susjednih ćelija mogu biti zidovi. Robot se kreće duž ćelija polja i može izvoditi sljedeće komande, kojima se dodjeljuju brojevi:

Prilikom izvođenja svake takve komande, robot se pomiče u susjednu ćeliju u naznačenom smjeru. Ako postoji zid u ovom smjeru između ćelija, tada je robot uništen. Šta će se dogoditi s robotom ako izvrši niz naredbi 32323 (ovdje brojevi označavaju brojeve komandi), počevši da se kreće iz ćelije A? Koju sekvencu komandi robot treba da izvrši da bi prešao iz ćelije A u ćeliju B bez kolapsa kada udari o zidove?

Prilikom razvoja algoritma:

identifikuju se objekti koji se pojavljuju u problemu, utvrđuju se svojstva objekata, odnosi između objekata i moguće radnje sa objektima;
utvrđuju se početni podaci i traženi rezultat;
određuje se redoslijed radnji izvođača, osiguravajući prijelaz sa početnih podataka na rezultat;
redoslijed radnji se bilježi pomoću komandi uključenih u sistem komandi izvršioca.

Možemo reći da je algoritam model aktivnosti izvršioca algoritma.

3.1.3. Svojstva algoritma

Ne može se svaka instrukcija, sekvenca instrukcija ili akcioni plan smatrati algoritmom. Svaki algoritam nužno ima sljedeća svojstva: diskretnost, razumljivost, sigurnost, efektivnost i masovnost.

Svojstvo diskretnosti znači da je put do rješavanja problema podijeljen u zasebne korake (akcije). Svaka akcija ima odgovarajuću instrukciju (naredbu). Tek nakon izvršenja jedne naredbe, izvršilac može započeti izvršavanje sljedeće naredbe.

Svojstvo razumljivosti znači da se algoritam sastoji samo od naredbi koje su uključene u sistem naredbi izvođača, odnosno od onih naredbi koje izvođač može uočiti i prema kojima može izvršiti tražene radnje.

Svojstvo sigurnosti znači da algoritam ne sadrži komande čije značenje izvođač može dvosmisleno protumačiti; Neprihvatljive su situacije kada nakon izvršenja sljedeće komande izvođaču nije jasno koju naredbu da izvrši u sljedećem koraku.

Svojstvo efikasnosti znači da algoritam mora biti u stanju da dobije rezultat nakon konačnog, moguće veoma velikog broja koraka. U ovom slučaju, rezultatom se smatra ne samo odgovor određen formulacijom problema, već i zaključak o nemogućnosti daljeg rješavanja ovog problema iz bilo kojeg razloga.

Svojstvo masovne proizvodnje znači da algoritam mora pružiti mogućnost njegove primjene za rješavanje bilo kojeg problema iz određene klase problema. Na primjer, algoritam za pronalaženje korijena kvadratne jednačine trebao bi biti primjenjiv na bilo koju kvadratnu jednačinu, algoritam za prelazak ulice trebao bi biti primjenjiv bilo gdje na ulici, algoritam za pripremu lijeka trebao bi biti primjenjiv na pripremu bilo koje njegove količine, itd.

Primjer 8. Razmotrimo jednu od metoda za pronalaženje svih prostih brojeva koji ne prelaze n. Ova metoda se naziva "Eratostenovo sito", nazvana po starogrčkom naučniku Eratostenu koji ju je predložio.

Da biste pronašli sve proste brojeve koji nisu veći od datog broja n, slijedeći Eratostenovu metodu, morate izvršiti sljedeće korake:

zapišite sve cijele brojeve od 2 do n u redu (2, 3, 4, ..., n);
okvir 2 - prvi prost broj;
precrtati sa liste sve brojeve djeljive posljednjim pronađenim prostim brojem;
pronađite prvi neoznačeni broj (označeni brojevi su precrtani brojevi ili brojevi u okviru) i stavite ga u okvir - to će biti još jedan prost broj;
ponovite korake 3 i 4 sve dok ne ostane nijedan neobeležen broj.

Vizuelniju ideju o metodi pronalaženja prostih brojeva možete dobiti pomoću animacije "Eratostenovo sito" (http://school-collection.edu.ru/).

Razmatrani slijed radnji je algoritam, budući da zadovoljava sljedeća svojstva:

diskretnost - proces pronalaženja prostih brojeva podijeljen je na korake;
razumljivost - svaka naredba je razumljiva učeniku 9. razreda koji izvodi ovaj algoritam;
sigurnost - svaku komandu izvođač tumači i izvršava nedvosmisleno; postoje uputstva o redosledu izvršavanja komandi;
efektivnost - nakon određenog broja koraka postiže se rezultat;
masovni karakter - slijed radnji je primjenjiv za bilo koji prirodni n.

Razmatrana svojstva algoritma nam omogućavaju da damo precizniju definiciju algoritma.

3.1.4. Mogućnost automatizacije ljudskih aktivnosti

Izrada algoritma je obično radno intenzivan zadatak koji od osobe zahtijeva duboko znanje, domišljatost i puno vremena.

Rješavanje problema pomoću gotovog algoritma zahtijeva samo od izvođača da striktno slijedi date upute.

Primjer 9. Iz gomile koja sadrži bilo koji broj predmeta veći od tri, dva igrača naizmjenično uzimaju po jedan ili dva predmeta. Pobjednik je onaj koji može pokupiti sve preostale predmete u svom sljedećem potezu.

Razmotrimo algoritam po kojem će prvi igrač sigurno osigurati pobjedu.

Ako je broj predmeta u hrpi višestruki od 3, onda ustupite mjesto protivniku, inače započnite igru.
Sa svojim sljedećim potezom, svaki put dodajte broj objekata koje je vaš protivnik uzeo na 3 (broj preostalih objekata mora biti višestruki od 3).

Izvođač možda ne ulazi u smisao onoga što radi i ne obrazlaže zašto se ponaša ovako, a ne drugačije, odnosno može djelovati formalno. Sposobnost izvođača da djeluje formalno pruža mogućnost automatizacije ljudske aktivnosti. Za ovo:

proces rješavanja problema predstavljen je kao niz jednostavnih operacija;
stvorena je mašina (automatski uređaj) sposobna za obavljanje ovih operacija u redoslijedu navedenom u algoritmu;
osoba je oslobođena rutinskih aktivnosti, izvršenje algoritma je povjereno automatskom uređaju.

Najvažniji

Izvršilac je objekat (osoba, životinja, tehničko sredstvo) sposoban da izvrši određeni skup naredbi. Formalni izvođač uvijek izvodi istu komandu na isti način. Za svakog formalnog izvođača možete odrediti: opseg zadataka koje treba riješiti, okruženje, sistem komandi i način rada.

Algoritam je opis niza radnji namijenjenih određenom izvođaču koji od početnih podataka vodi do traženog rezultata, koji ima svojstva diskretnosti, razumljivosti, sigurnosti, djelotvornosti i masovnosti.

Sposobnost izvođača da djeluje formalno pruža mogućnost automatizacije ljudske aktivnosti.

Pitanja i zadaci

Kako se zove algoritam?
Pronađite sinonime za riječ "recept".
Navedite primjere algoritama koje ste učili u školi.
Ko može biti izvršilac algoritma?
Navedite primjer formalnog izvođača. Navedite primjer kada osoba djeluje kao formalni izvođač.
Koje komande robot treba da obavlja funkcije: a) blagajnika u prodavnici; b) domar; c) zaštitar?
Šta određuje opseg zadataka koje obavlja "kompjuterski" izvođač?
Razmotrite program za obradu teksta na vašem računaru kao izvršioca. Opišite niz zadataka koje rješava ovaj izvođač i njegovo okruženje.
Šta je tim, sistem komandi izvođača?
Navedite glavna svojstva algoritma.
Do čega može dovesti odsustvo bilo kakvog svojstva u algoritmu? Navedite primjere.
Zašto je važno biti u mogućnosti formalno izvršiti algoritam?
Niz brojeva se konstruiše prema sledećem algoritmu: prva dva broja niza se uzimaju jednakima 1; Svaki sljedeći broj u nizu se smatra jednakim zbroju prethodna dva broja. Zapišite prvih 10 članova ovog niza.
Neki algoritam dobija novi lanac iz jednog niza znakova na sledeći način. Prvo se ispisuje originalni lanac znakova, nakon njega se ispisuje originalni lanac znakova obrnutim redoslijedom, zatim se upisuje slovo koje slijedi u ruskoj abecedi nakon slova koje je bilo na posljednjem mjestu u originalnom lancu. Ako je zadnje mjesto u originalnom lancu slovo Z, onda se kao sljedeće slovo piše slovo A. Rezultirajući lanac je rezultat algoritma. Na primjer, ako je originalni lanac znakova bio DOM, tada će rezultat algoritma biti lanac DOMMODN. Zadan niz znakova KOM. Koliko će slova O biti u lancu simbola koji će se dobiti ako primenite algoritam na ovaj lanac, a zatim ponovo primenite algoritam na rezultat njegovog rada?
Pronađite animaciju koraka Eratostenovog algoritma na internetu. Koristite Eratostenov algoritam da pronađete sve proste brojeve koji ne prelaze 50.
Šta će biti rezultat Kornjačinog izvršavanja algoritma (vidi primjer 5)?
Zapišite algoritam za izvršitelj kalkulatora (primjer 6), koji ne sadrži više od 5 naredbi:
Sistem izvršnih komandi Konstruktor se sastoji od dve komande, kojima se dodeljuju brojevi:
Prema prvom od njih, broju desno se dodaje 2, prema drugom broj se dijeli sa 2. Kako će se pretvoriti broj 8 ako izvođač izvrši algoritam 22212? Kreirajte algoritam u komandnom sistemu ovog izvršioca, prema kojem će se broj 1 pretvoriti u broj 16 (algoritam ne smije sadržavati više od 5 naredbi).
U kojoj ćeliji treba da se nalazi Robot performer (primjer 7) da bi se vratio u njega nakon izvršenja algoritma 3241?

Algoritam i njegova svojstva.

Algoritam- jasna i precizna instrukcija izvođaču da izvrši konačnu sekvencu naredbi koja vodi od početnih podataka do željenog rezultata.

Algoritam executor- ovo je objekat ili subjekt za koji je algoritam dizajniran da kontroliše.

Izvođačev komandni sistem (SCS) je čitav skup naredbi koje izvođač može izvršiti.

Svojstva algoritma: razumljivost, tačnost, konačnost.

jasnoća: algoritam se sastoji samo od komandi uključenih u SKI izvršioca.

tačnost: Svaka komanda kontrolnog algoritma određuje nedvosmislenu akciju izvođača.

Završenost (ili performanse): izvršenje algoritma mora dovesti do rezultata u konačnom broju koraka.

Okruženje izvođača: okruženje u kojem izvođač djeluje.

Određeni slijed radnji izvođača uvijek se odnosi na neke izvorni podaci. Na primjer, da biste pripremili jelo prema kulinarskom receptu, potrebni su vam odgovarajući proizvodi (podaci). Za rješavanje matematičkog problema (rješavanje kvadratne jednadžbe) potrebni su vam početni numerički podaci (koeficijenti jednadžbe).

Kompletan skup podataka: neophodan i dovoljan skup podataka za rješavanje zadatka (dobivanje željenog rezultata).

Metode za pisanje algoritama.

Najčešće metode su: grafički, verbalno i u formi kompjuterski programi.

Grafička metoda podrazumijeva korištenje određenih grafičkih simbola - blokova.

Naziv bloka	Oznaka bloka	Sadržaj
Proces		Obrada podataka
Odlučivanje		Logički blok za provjeru istinitosti ili neistinitosti određenog stanja
Prijenos podataka		Unos ili izlaz informacija
Počni, stani		Početak ili kraj programa
Modifikacija		Organizacija cikličkog procesa - zaglavlje ciklusa

Zbirka blokova čini tzv dijagram toka algoritma.

Verbalno snimanje algoritmi su prvenstveno fokusirani na čovjeka izvođača i omogućavaju različito snimanje instrukcija, ali snimanje mora biti prilično precizno.

Prilikom pisanja algoritama u formu programe računari koriste programske jezike - sisteme za kodiranje instrukcija i pravila za njihovu upotrebu. Pisanje algoritama u obliku programa karakteriše visok stepen formalizacije.

Algoritmi za rad sa količinama. Osnovne algoritamske strukture.

Količina je jedan informacijski objekt koji ima ime, vrijednost i tip.

Izvođač algoritama za rad sa veličinama može biti osoba ili poseban tehnički uređaj, kao što je računar. Takav izvođač mora imati memorija za skladištenje količina.

Količine mogu biti konstantne ili varijabilne.

Konstantna vrijednost (konstanta) ne mijenja svoju vrijednost tokom izvršavanja algoritma. Konstanta se može označiti svojom vrijednošću (brojevi 10, 3.5) ili simboličkim imenom (broj).

Varijabilna vrijednost može promijeniti vrijednost tokom izvršavanja algoritma. Varijabla je uvijek označena simboličkim imenom (X, A, R5, itd.).

Vrsta količine definira skup vrijednosti koje vrijednost može poduzeti i skup radnji koje se mogu izvršiti s tom vrijednošću. Osnovne vrste veličina: cjelobrojne, realne, simboličke, logičke.

Izraz- zapis koji definira redoslijed radnji na količinama. Izraz može sadržavati konstante, varijable, znakove operacije i funkcije. primjer:

A + B; 2*X-Y; K + L - sin(X)

Komanda dodjeljivanja je naredba izvršitelja koja rezultira da varijabla prima novu vrijednost. Format naredbe:

ime varijable>:=izraz>

Naredba dodjele se izvršava sljedećim redoslijedom: prvo se izračunava, a zatim se rezultirajuća vrijednost dodjeljuje varijabli.

Primjer. Neka varijabla A ima vrijednost 6. Koju će vrijednost dobiti varijabla A nakon izvršenja naredbe: A:= 2 * A - 1?
Rješenje. Izračunavanje izraza 2*A - 1 sa A=6 će dati broj 11. To znači da će nova vrijednost varijable A biti jednaka 11.

U nastavku će se pretpostaviti da Izvođač algoritama za rad sa veličinama je računar. Bilo koji algoritam se može izgraditi iz naredbi zadaci, unos, izlaz, grananje I ciklus.

Naredba za unos- naredba kojom se vrijednosti varijabli postavljaju putem ulaznih uređaja (na primjer, tastature).

primjer: unos A - unos vrijednosti varijable A sa tastature računara.

Izlazna komanda: Naredba koja prikazuje vrijednost količine na izlaznom uređaju računara (kao što je monitor).

primjer: zaključak X - vrijednost varijable X se prikazuje na ekranu.

Komanda podružnice- dijeli algoritam na dva puta u zavisnosti od nekog uslova; tada se izvođenje algoritma nastavlja na opći nastavak. Grananje može biti potpuno ili nepotpuno. Opis grananja u blok dijagramima i na algoritamskom jeziku:

Ovdje serija znači jednu ili više uzastopnih naredbi; kv - kraj grananja.

Naredba petlje osigurava ponovljeno izvršavanje niza naredbi (tijelo petlje) na osnovu nekog uslova.

Petlja s preduvjetom- petlja čije se izvršavanje ponavlja sve dok uvjet petlje nije istinit:

Petlja s parametrom- ponavljano izvršavanje tijela petlje dok cijeli broj parametar prolazi kroz skup svih vrijednosti od početne (In) do konačne (Ik):

Primjer. Date su dvije jednostavne razlomke. Napravite algoritam za dobijanje razlomka koji je rezultat njihovog dijeljenja.
Rješenje. U algebarskom obliku, rješenje problema izgleda ovako:
a/b: c/d = a*d/b*c = m/n
Početni podaci su četiri cjelobrojne veličine: a, b, c, d. Rezultat su dva cijela broja m i n.

alg dijeljenje razlomaka
netaknut a, b, c, d, m, n
start input a b c d
m:=a*d
n:=b*c
izlaz "Numerator=", m
izlaz "Denominator=", n
koi

Imajte na umu da za izlaz teksta (bilo koji niz znakova), on mora biti napisan u navodnicima u naredbi zaključak.

Efimova O., Morozov V., Ugrinovič N. Kurs računarske tehnologije sa osnovama računarske nauke. Udžbenik za srednju školu. - M.: DOO "AST Izdavačka kuća"; ABF, 2000
Problematika-radionica iz informatike. U 2 toma/Ed. I. Semakina, E. Henner. - M.: Laboratorija za osnovna znanja, 2001.
Ugrinovich N. Računarstvo i informacione tehnologije. 10-11 razredi - M.: Laboratorija za osnovna znanja, JSC "Moskovski udžbenici", 2001.

Zadaci i testovi na temu "Algoritmi i izvršioci"

Artist Management Draftsman - Algoritmi 6. razred
Lekcije: 4 Zadaci: 9 Testovi: 1
2 zadatka: 9 testova: 1

Dragi studente!

Poznavanje teme "Algoritmi i izvršioci" neophodno je prvenstveno za dalje proučavanje programiranja. Programski jezik QBasic izabran je kao osnova za izučavanje programiranja. Odustali smo od ideje da u naš kurs uključimo Visual Basic ili bilo koji drugi objektno orijentirani programski jezik, budući da ovaj pristup još nije široko korišten u većini srednjih škola u Ruskoj Federaciji. Osim toga, objektno orijentirano programiranje je bazirano na principima klasičnog Dos programiranja.

Naš kurs je osmišljen za program opšteg obrazovanja. Kada se pripremate za prijemni ispit iz informacionih tehnologija na fakultetima, potrebno je da se upoznate sa specifičnostima studiranja programiranja na datom univerzitetu. U nekim slučajevima, potrebno je dubinsko proučavanje brojnih tema, na primjer, "Nizovi". Na to treba obratiti pažnju kada proučavate literaturu o programiranju, možda biste trebali koristiti metodološke preporuke za pripremu ispita koje se trenutno objavljuju u većini visokoškolskih ustanova.

U zaključku napominjemo da je postizanje „akrobatike“ u programiranju moguće samo uz stalnu praksu i rješavanje konkretnih primijenjenih problema.

Teorijske informacije

Algoritam je opis niza radnji (plan), čije striktno izvršenje dovodi do rješenja datog problema u konačnom broju koraka.

Svojstva algoritama:

1. Diskretnost (algoritam se mora sastojati od specifičnih radnji koje slijede određenim redoslijedom);

2. Determinizam (svaka radnja mora biti striktno i nedvosmisleno definisana u svakom slučaju);

3. Konačnost (svaka radnja i algoritam u cjelini moraju biti u mogućnosti da se dovrše);

4. Masivnost (isti algoritam se može koristiti sa različitim izvornim podacima);

5. Efikasnost (bez grešaka, algoritam bi trebao dovesti do ispravnog rezultata za sve važeće ulazne vrijednosti).

Vrste algoritama:

1. Linearni algoritam (opis radnji koje se izvode jednom u datom redosledu);

2. Ciklični algoritam (opis radnji koje se moraju ponoviti određeni broj puta ili dok se zadatak ne završi);

3. Algoritam grananja (algoritam u kojem se, u zavisnosti od uslova, izvodi jedan ili drugi niz radnji)

Primjeri rješavanja problema

Izvođač Crtač se kreće po koordinatnoj ravni, ostavljajući trag u obliku linije. Nacrt može izvršiti naredbu Pređi na (a, b)(gdje su a,b cijeli brojevi), pomjerajući crtača iz tačke sa koordinatama (x, y) u tačku sa koordinatama (x + a, y + b). Ako su brojevi a, b pozitivni, vrijednost odgovarajuće koordinate se povećava; ako je negativan, smanjuje se.

Na primjer, ako se crtač nalazi u tački sa koordinatama (9, 5), onda komanda Prebaci na

(1, -2) će pomjeriti crtača na tačku (10, 3).

Ponoviti k puta

Tim1 Tim2 Tim3

Kraj

znači da redoslijed naredbi Tim1 Tim2 Tim3će se ponoviti k puta. Autoru nacrta je dat sljedeći algoritam za izvršenje:

Ponovite 3 puta

Pomak za (-2, -3) Pomak za (3, 2) Pomak za (-4, 0)

Kraj

S kojom naredbom se ovaj algoritam može zamijeniti tako da crtač završi na istoj tački kao i nakon izvršenja algoritma?

1) Pređi na (-9, -3)

2) Pređite na (-3, 9)

3) Pređi na (-3, -1)

4) Pređi na (9, 3)

Rješenje:

Ovaj zadatak je najbolje rješavati uzastopno.

U petlji, crtač izvršava niz naredbi

– Pomicanje (-2, -3)

– Pređi na (3, 2)

– Pređite na (-4, 0),

koja se može zamijeniti jednom komandom: Pomakni za (-2+3-4, -3+2+0), tj. Pređite na (-3, -1).

Pošto se petlja ponavlja 3 puta, rezultirajuća komanda Shift by (-3, -1) će biti izvršena 3 puta. To znači da se ciklus može zamijeniti naredbom Shift sa (-3*3, -1*3), tj. Pređite na (-9, -3). Tako dobijamo naredbu Move to (-9, -3) kojom se može zamijeniti cijeli algoritam.

Zadaci za obuku

1. Izvođač Crtač se kreće po koordinatnoj ravni, ostavljajući trag u obliku linije. Nacrt može izvršiti naredbu Pređi na (a, b)(gdje su a, b cijeli brojevi), pomjerajući crtača iz tačke sa koordinatama (x, y) u tačku sa koordinatama (x + a, y + b). Ako su brojevi a, b pozitivni, vrijednost odgovarajuće koordinate se povećava; ako je negativan, smanjuje se.

Na primjer, ako je crtač na koordinatama (4, 2), tada će komanda Premjesti na (2, −3) pomjeriti crtača u tačku (6, −1).

Ponoviti k puta

Tim1 Tim2 Tim3

Kraj

znači da redoslijed naredbi Tim1 Tim2 Tim3 ponoviće se k jednom.

Autoru nacrta je dat sljedeći algoritam za izvršenje:

Ponovite 2 puta

Pomicanje za (−6, −4)

Nakon što je završio ovaj algoritam, crtač se vratio na početnu tačku. Koju naredbu treba staviti umjesto komande Tim1?

1) Pomaknite za (−2, −1)

2) Pređite na (1, 1)

3) Pomak za (−4, −2)

4) Pređi na (2, 1)

2. Pređi na (a, b)

Na primjer, ako je crtač na koordinatama (4, 2), tada će komanda Premjesti na (2, −3) pomjeriti crtača u tačku (6, −1).

Ponoviti k puta

Tim1 Tim2 Tim3

Kraj

Tim1 Tim2 Tim3 ponoviće se k jednom.

Ponovite 4 puta

Naredba1 Premjesti na (3, 3) Pomakni na (1,−2) Kraj

Pomaknite za (−8, 12)

Tim1?

1) Pomak za (−2, −4)

2) Pomak za (4,−13)

3) Pređi na (2, 4)

4) Pomak za (−8, −16)

3. Izvođač Crtač se kreće po koordinatnoj ravni, ostavljajući trag u obliku linije. Nacrt može izvršiti naredbu Pređi na (a, b)(gdje su a, b cijeli brojevi), pomjerajući crtača iz tačke sa koordinatama (x, y) u tačku sa koordinatama (x + a, y + b). Ako su brojevi a, b pozitivni, vrijednost odgovarajuće koordinate se povećava; ako je negativan, smanjuje se.

Ponoviti k puta

Tim1 Tim2 Tim3

Kraj

znači da redoslijed naredbi Tim1 Tim2 Tim3 ponoviće se k jednom.

Autoru nacrta je dat sljedeći algoritam za izvršenje:

Ponovite 3 puta

Pređi na (3, 9)

Nakon što je završio ovaj algoritam, crtač se vratio na početnu tačku. Koju naredbu treba staviti umjesto komande Tim1?

1) Prebacite na (3, 4)

2) Pomak za (−5, −10)

3) Pomak za (−9, −12)

4) Pomak za (−3, −4)

4. Izvođač Crtač se kreće po koordinatnoj ravni, ostavljajući trag u obliku linije. Nacrt može izvršiti naredbu Pređi na (a, b)(gdje su a, b cijeli brojevi), pomjerajući crtača iz tačke sa koordinatama (x, y) u tačku sa koordinatama (x + a, y + b). Ako su brojevi a, b pozitivni, vrijednost odgovarajuće koordinate se povećava; ako je negativan, smanjuje se.

Na primjer, ako se crtač nalazi u tački s koordinatama (4, 2), tada će komanda Premjesti na (2, −3) pomjeriti crtača u tačku (6, −1).

Ponoviti k puta

Tim1 Tim2 Tim3

Kraj

znači da redoslijed naredbi Tim1 Tim2 Tim3 ponoviće se k jednom.

Autoru nacrta je dat sljedeći algoritam za izvršenje:

Ponovite 3 puta

Naredba1 Premjesti na (3, 2) Pomakni na (2, 1) Kraj

Pređi na (−9, −6)

Nakon što je završio ovaj algoritam, crtač se vratio na početnu tačku. Koju naredbu treba staviti umjesto komande Tim1?

1) Pomak za (−6, −3)

2) Pređi na (4, 3)

3) Pomak za (−2, −1)

4) Pređi na (2, 1)

5. Izvođač Crtač se kreće po koordinatnoj ravni, ostavljajući trag u obliku linije. Nacrt može izvršiti naredbu Pređi na (a, b)(gdje su a, b cijeli brojevi), pomjerajući crtača iz tačke sa koordinatama (x, y) u tačku sa koordinatama (x + a, y + b). Ako su brojevi a, b pozitivni, vrijednost odgovarajuće koordinate se povećava; ako je negativan, smanjuje se.

Ponoviti k puta

Tim1 Tim2 Tim3

Kraj

znači da redoslijed naredbi Tim1 Tim2 Tim3 ponoviće se k jednom.

Autoru nacrta je dat sljedeći algoritam za izvršenje:

Ponovite 2 puta

Naredba1 Premjesti na (3, 3) Pomakni na (1, −2) Kraj

Pomak za (4, −6)

Nakon što je završio ovaj algoritam, crtač se vratio na početnu tačku. Koju naredbu treba staviti umjesto komande Tim1?

1) Pomak za (6, −2)

2) Pomaknite za (−8, 5)

3) Pomaknite za (−12, 4)

4) Pomaknite za (−6, 2)

6. Izvođač Crtač se kreće po koordinatnoj ravni, ostavljajući trag u obliku linije. Nacrt može izvršiti naredbu Pređi na (a, b)(gdje su a, b cijeli brojevi), pomjerajući crtača iz tačke sa koordinatama (x, y) u tačku sa koordinatama (x + a, y + b). Ako su brojevi a, b pozitivni, vrijednost odgovarajuće koordinate se povećava; ako je negativan, smanjuje se.

Na primjer, ako se crtač nalazi u tački s koordinatama (4, 2), tada će komanda Premjesti na (2, −3) pomjeriti crtača u tačku (6, −1).

Ponoviti k puta

Tim1 Tim2 Tim3

Kraj

znači da redoslijed naredbi Tim1 Tim2 Tim3 ponoviće se k jednom.

Autoru nacrta je dat sljedeći algoritam za izvršenje:

Ponovite 4 puta

Naredba1 Premjesti na (1, 3) Pomakni na (1, −2) Kraj

Pomaknite za (−4, −12)

Nakon što je završio ovaj algoritam, crtač se vratio na početnu tačku. Koju naredbu treba staviti umjesto komande Tim1?

1) Pomak za (1,−2)

2) Prebacite na (12, 4)

3) Pređi na (2, 11)

4) Pomaknite za (−1, 2)

7. Izvođač Crtač se kreće po koordinatnoj ravni, ostavljajući trag u obliku linije. Nacrt može izvršiti naredbu Pređi na (a, b)(gdje su a, b cijeli brojevi), pomjerajući crtača iz tačke sa koordinatama (x, y) u tačku sa koordinatama (x + a, y + b). Ako su brojevi a, b pozitivni, vrijednost odgovarajuće koordinate se povećava; ako je negativan, smanjuje se.

Na primjer, ako se crtač nalazi u tački s koordinatama (4, 2), tada će komanda Premjesti na (2, −3) pomjeriti crtača u tačku (6, −1).

Ponoviti k puta

Tim1 Tim2 Tim3

Kraj

znači da redoslijed naredbi Tim1 Tim2 Tim3 ponoviće se k jednom.

Autoru nacrta je dat sljedeći algoritam za izvršenje:

Ponovite 4 puta

Naredba1 Premjesti na (3, 2) Pomakni na (2, 1) Kraj

Pređi na (−12, −8)

Nakon što je završio ovaj algoritam, crtač se vratio na početnu tačku. Koju naredbu treba staviti umjesto komande Tim1?

1) Pomak za (−8, −4)

2) Pomak za (−2, −1)

3) Pređi na (7, 5)

4) Pređi na (2, 1)

8. Naprijed n Desno m

Ponovite 9 [Naprijed 50 Desno 60]

1) pravilni šestougao

2) pravilan trougao

3) otvorena izlomljena linija

4) pravilni šestougao

9. Izvođač Kornjača se kreće po ekranu računara, ostavljajući trag u obliku linije. U svakom konkretnom trenutku poznata je pozicija izvođača i smjer njegovog kretanja. Izvođač ima dvije komande: Naprijed n(gdje je n cijeli broj), što uzrokuje da se kornjača kreće za n koraka u smjeru kretanja; Desno m(gdje je m cijeli broj), uzrokujući promjenu smjera kretanja za m stepeni u smjeru kazaljke na satu. Zapis Ponovite k [Command1 Command2 Command3] znači da će se niz naredbi u zagradama ponoviti k puta.

Kornjači je dat sljedeći algoritam za izvršenje: Ponovite 7 [Naprijed 70 Desno 120]. Koji će se oblik pojaviti na ekranu?

1) pravilni šestougao

2) otvorena izlomljena linija

3) pravilan heptagon

4) pravilan trougao

10. Izvođač Kornjača se kreće po ekranu računara, ostavljajući trag u obliku linije. U svakom konkretnom trenutku poznata je pozicija izvođača i smjer njegovog kretanja. Izvođač ima dvije komande: Naprijed n(gdje je n cijeli broj), što uzrokuje da se kornjača kreće za n koraka u smjeru kretanja; Desno m(gdje je m cijeli broj), uzrokujući promjenu smjera kretanja za m stepeni u smjeru kazaljke na satu. Zapis Ponovite k [Command1 Command2 Command3] znači da će se niz naredbi u zagradama ponoviti k puta.

Kornjači je dat sljedeći algoritam za izvršenje: Ponovite 9 [Naprijed 70 Desno 90]. Koji će se oblik pojaviti na ekranu?

2) pravilni šestougao

3) pravilan osmougao

4) pravilan četvorougao

11. Izvođač Kornjača se kreće po ekranu računara, ostavljajući trag u obliku linije. U svakom konkretnom trenutku poznata je pozicija izvođača i smjer njegovog kretanja. Izvođač ima dvije komande: Naprijed n(gdje je n cijeli broj), što uzrokuje da se kornjača kreće za n koraka u smjeru kretanja; Desno m(gdje je m cijeli broj), uzrokujući promjenu smjera kretanja za m stepeni u smjeru kazaljke na satu. Zapis Ponovite k [Command1 Command2 Command3] znači da će se niz naredbi u zagradama ponoviti k puta.

Kornjači je dat sljedeći algoritam za izvršenje: Ponovite 5 [Naprijed 80 Desno 60]. Koji će se oblik pojaviti na ekranu?

1) pravilan petougao

2) pravilan trougao

3) pravilni šestougao

4) otvorena izlomljena linija

12. Izvođač Kornjača se kreće po ekranu računara, ostavljajući trag u obliku linije. U svakom konkretnom trenutku poznata je pozicija izvođača i smjer njegovog kretanja. Izvođač ima dvije komande: Naprijed n(gdje je n cijeli broj), što uzrokuje da se kornjača kreće za n koraka u smjeru kretanja; Desno m(gdje je m cijeli broj), uzrokujući promjenu smjera kretanja za m stepeni u smjeru kazaljke na satu. Zapis Ponovite k [Command1 Command2 Command3] znači da će se niz naredbi u zagradama ponoviti k puta.

Kornjači je dat sljedeći algoritam za izvršenje: Ponovite 5 [Naprijed 80 Desno 90]. Koji će se oblik pojaviti na ekranu?

1) otvorena izlomljena linija

2) pravilni šestougao

3) pravilan petougao

4) pravilan četvorougao

Teorijske informacije

Primjeri rješavanja problema

Zadaci za obuku

Teorijske informacije

Primjeri rješavanja problema

Zadaci za obuku

Teorijske informacije

Primjeri rješavanja problema

Zadaci za obuku

Teorijske informacije

Primjeri rješavanja problema

Zadaci za obuku

Teorijske informacije

Primjeri rješavanja problema

Zadaci za obuku

Teorijske informacije

Primjeri rješavanja problema

Zadaci za obuku

Teorijske informacije

Primjeri rješavanja problema

Zadaci za obuku

Teorijske informacije

Primjeri rješavanja problema

Zadaci za obuku

Teorijske informacije

Primjeri rješavanja problema

Zadaci za obuku

Riječ "algoritam" dolazi od imena arapskog matematičara al-Khwarizmija iz 9. stoljeća, koji je formulirao pravila za izvođenje aritmetičkih operacija.

Algoritam– tačna i razumljiva instrukcija izvođaču da izvrši konačnu sekvencu naredbi koja vodi od početnih podataka do početnog rezultata.

Primjeri: dnevna rutina, redoslijed kuhanja, upute itd.)

Algoritam executor– to je onaj koji izvršava algoritam (osoba, životinja, mašina, kompjuter).

Sistem komandi izvršioca- ovo je čitav skup naredbi koje izvođač zna izvršiti (razumije). Algoritam se može izgraditi samo od komandi uključenih u sistem izvršnih komandi.

Na primjer, izvođač Robot može izvoditi komande naprijed, nazad, lijevo, desno, slikati. Kreće se po ćelijskom polju koje je ograničeno zidom i koje sadrži zidove. Robot ne može proći kroz zid.

Svojstva algoritma:

1.Performanse (ud)– mogućnost dobijanja rezultata iz početnih podataka u konačnom broju koraka. (Na primjer, kada se izvršava algoritam za sabiranje 2 broja, treba dobiti zbir).

2.Masovni karakter– mogućnost primjene algoritma na veliki broj različitih izvornih podataka. (Na primjer, možete dodati bilo koja 2 broja, poznavajući algoritam sabiranja.)

3.Determinizam(sigurnost, tačnost) – svaka komanda mora jedinstveno odrediti radnju izvođača.

4.Razumljivost– komanda mora biti napisana na jeziku razumljivom računaru.

5.Diskretnost– razdvajanje algoritma u zasebne komande.

Načini za pisanje algoritma:

1) Na prirodnom jeziku – snimanje u obliku posebnih naredbi na jeziku razumljivom ljudima.

2) Grafički – na jeziku dijagrama toka, koristeći geometrijske oblike (oval, pravougaonik, paralelogram, romb).

3) Na algoritamskom jeziku - jezik za pisanje algoritama za nastavu programiranja. Komande su napisane na ruskom jeziku.

4) U programskom jeziku - program. Programski jezici: Basic, Pascal, C, Visual Basic.

B7.Osnovne algoritamske strukture: praćenje, grananje, petlja; slika na blok dijagramima. Rastavljanje zadataka na podzadatke. Pomoćni algoritmi.

Algoritamski dizajni. Unutar algoritama mogu se razlikovati grupe koraka koji se razlikuju po unutrašnjoj strukturi – algoritamske konstrukcije.

Osnovne algoritamske konstrukcije su linearni niz koraka (ili slijedećih), grananja i petlje.

Poziva se algoritam u kojem se naredbe izvršavaju uzastopno jedna za drugom linearni algoritam.

Ovako izgleda linearni algoritam u jeziku blok dijagrama:

Primjer: algoritam za uključivanje računara:

Uključite napajanje računara (pritisnite dugme na štitniku od prenapona).
Uključite monitor i štampač.
Pritisnite dugme za napajanje na sistemskoj jedinici.
Sačekajte da se operativni sistem učita i da se pojavi radna površina.
Na posao.

U ovom algoritmu, sve radnje moraju se izvoditi uzastopno jedna za drugom: ne možete početi raditi ako napajanje ili monitor nisu uključeni.

U algoritamsku strukturu" grananje» uključeno stanje, u zavisnosti od istinitosti uslova, izvršava se jedan ili drugi niz naredbi (serija).

Uslov je izjava koja može biti istinita ili lažna. U uslovu se dva broja, dva niza, dvije varijable ili izrazi niza međusobno uspoređuju pomoću operatora poređenja (>,<, =, >=, <=).

Snimanje na algoritamskom jeziku: IfCondition Then Series 1 (If Stanje istina, pa istina Epizoda 1, Ako Stanje false, onda se ništa ne izvršava). Primjer: Ako je danas nedjelja, onda nema potrebe ići u školu. Puni oblik grananja

U algoritamskim strukturama ciklus uključuje niz naredbi koje se ponavljaju. Ovaj niz naredbi se zove tijelo petlje.

Postoje dvije vrste cikličkih algoritamskih struktura:

suprotstavljene petlje, u kojem se tijelo petlje izvršava određeni broj puta;
uslovne petlje, u kojem se tijelo petlje izvršava sve dok je uvjet zadovoljen.

Petlja sa brojačem– koristi se kada se unaprijed zna koliko ponavljanja tijela petlje treba izvesti.