Vrste algoritama. Linearni tip algoritama

Programiranje je pisanje nečega koristeći tuđi nepoznat jezik. Sa razvojem ove oblasti znanja, programeri su otišli još dalje i naučili da zapišu "nešto", a da nisu ni razumeli kako to zvuči na ruskom. Početnici uče pisati kod direktno u C ++ ili php, koristeći mnoge biblioteke, a zapravo ni ne razumiju kako ono što stvaraju zvuči na njihovom maternjem jeziku. Algoritamizacija se bavi razjašnjavanjem i dovođenjem ovog "nečega" do razumljivog.

Algoritamizacija

Većina primjera algoritama u informatici, čak i na univerzitetima, proučava se na osrednjem nivou. Uobičajena je praksa da se beskonačno piše sve složeniji kod. Pokušaji neiskusnih programera da odmah počnu pisati programe na programskom jeziku mogu se uporediti s radom novinara koji, jedva savladavši osnove stranog jezika, piše članak za časopis. Takav problem možete izbjeći ako prvo počnete snimati svoj rad na svom maternjem jeziku, uredite ga, provjerite ima li grešaka i na kraju ga prevedete na traženi jezik.

Prednost ovakvog pristupa leži uglavnom u činjenici da će programer biti angažovan na prevođenju samo 25% vremena, dok će pri pisanju programa na novom jeziku 100% provesti radeći sa nepoznatim jezikom. Istovremeno će se naći u skučenim uslovima i neće moći dobro provjeriti greške i revidirati projekat.

Algoritamizacija pomaže da se prilikom implementacije projekta na računaru proces rješenja opiše na materinjem i razumljivom jeziku u obliku dijagrama međusobno povezanih algoritama, da se analiziraju ideje i dobije najkvalitetniji i promišljeniji kod koji će biti otporniji na greške i raditi efikasnije.

Koncept algoritma

Kompjuter ne može rješavati probleme, može samo obavljati jednostavne radnje određenim redoslijedom. "Šta je s kalkulatorom?" - pitate. I to je plod rada programera koji su kreirali program koji koristi određene algoritme za postizanje željenih rezultata. Hajde da razmotrimo jednu apstraktnu situaciju. Šta biste trebali učiniti ako se od vas traži da pronađete korijene kvadratnog trinoma osobe koja nije upoznata s metodama rješavanja jednačina?

Očigledno, on mora biti obučen za rješavanje kvadratnih jednačina. To se događa prema sljedećoj shemi:

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

Tada će biti moguće dati izvođaču zadatke da riješi kvadratnu jednačinu. 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 ideje korištene u rješavanju problema biti percipirane od strane izvođača na isti način na koji vi to razumijete? Ovdje se približavamo konceptu algoritma. Praksa pokazuje da da bi se nekome nešto korektno objasnilo, potrebno je izvršiti sljedeće korake:

• odrediti početne podatke (varijable i koeficijente kvadratne jednačine);
• podijeliti proces rješenja na jedinstveno poznate komponente za izvođača (diskriminantne formule i pronalaženje korijena);
• navedite redoslijed koraka (prvo izračunajte diskriminanta, a zatim korijene);
• uspostaviti uslov pod kojim se rješenje smatra potpunim (provjeriti pronađene korijene zamjenom ih u jednačinu umjesto varijabli);
• naznačiti tačno kakav bi trebao biti rezultat rješenja (korijeni pripadaju skupu realnih brojeva).

Opisani skup koraka u opštem smislu je algoritam. Dakle, algoritam se može shvatiti kao metoda za rješavanje zadatka, napisana korištenjem određenih pravila koja omogućavaju nedvosmisleno razumijevanje izvršenih radnji i njihovog redoslijeda. Algoritmi i primjeri zadataka bit će detaljnije razmotreni u nastavku.

Osnovna svojstva algoritma

Diskretnost. Proces rješavanja problema uvijek se sastoji od radnji koje su strogo odvojene jedna od druge, koje se nazivaju koracima, koji imaju određeni redoslijed izvršavanja.

Sigurnost. Svaki korak mora biti jasan i nedvosmislen kako po značenju tako iu ključu radnje koju treba izvršiti.

Efikasnost. Algoritam bi trebao dati rezultat. U ovom slučaju, broj koraka može biti u hiljadama ili milionima, ali oni uvijek moraju dovesti do rezultata.

Masovni karakter. Svaki algoritam razvijen za rješavanje problema mora biti primjenjiv na sve probleme ovog tipa za sve važeće ulazne podatke.

Mogućnosti računara

Za pravilno kreiranje algoritama za računare, važno je razumjeti njihove mogućnosti. Hajde da prvo razmotrimo količine sa kojima računar radi. Općenito se mogu podijeliti na numeričke i tekstualne, konstante i varijable.

Konstantni brojevi označavaju sve brojeve: 3,15, 100, 10 5, njihova karakteristika je nepromjenjivost tokom cijelog rada programa. Varijable mijenjaju svoju vrijednost tokom 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 ista simbolička oznaka kao i za numeričke varijable: ime, grad itd. Razlika između njih je uglavnom u dodijeljenu kompjutersku memoriju za pohranjivanje takve varijable.

Operacije koje je računar u stanju da izvrši:

1. Čitanje podataka sa ulaznih uređaja (tastatura, miš, fajlovi).
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 ekran, na papir, na mrežni interfejs).
4. Prijelaz između faza programa.
5. Poređenje dvije vrijednosti (veće, manje, jednako).

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

Metode za opisivanje algoritama

Verbalno. Ovo je najlakši način. Kulinarski recept je primjer za to. Dozvoljena je upotreba jednostavnih matematičkih formula.

Graphic. Opis pomoću dijagrama. Ovo je poseban način pisanja algoritama koristeći neku vrstu općeprihvaćenog algoritamskog jezika - oblika i blokova koji imaju specifično značenje: pravougaonik je jednostavna radnja, kosi paralelogram je ulaz/izlaz, romb je uvjet itd.

Korištenje algoritamskog jezika. Slično kao i grafički, to je i 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 obračun plata u zavisnosti od dužine radnog staža, napisan algoritamskim jezikom.

alg plate (int ST, realni ZP) arg ST res ZP start ako ST< 5 то zp = 150 иначе если ST <= 15 то ZP = 180 иначе ZP = 180 + (ST - 15)*10 конец

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

Tipovi algoritama

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

• linearni (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).

Ovo su osnovne vrste. Također je vrijedno napomenuti da u brojnoj literaturi postoji i četvrti tip - rekurzivni. Ali nema posebnu oznaku u shematskoj notaciji i implementira se kroz osnovne.

Više detalja o svakom algoritmu proračuna sa primjerima će biti opisano u nastavku.

Principi algoritamizacije

1. Odredite izvorne podatke.
2. Odaberite rješenje.
3. Odabranu metodu podijelite na korake na osnovu mogućnosti računara (programski jezik).
4. Izvršiti algoritam u obliku dijagrama, definirajući jasan redoslijed koraka.
5. Izlaz rezultata proračuna.
6. Označite prijelaz na izlaz kruga.

Otklanjanje grešaka u algoritmu

Čovjek griješi i to je činjenica. Glavni parametar svakog algoritma trebao bi biti ispravnost njegovog rada. Otklanjanje grešaka je proces identifikacije i ispravljanja grešaka u algoritmu. Za to se uzima određeni skup početnih podataka, koji se nazivaju testni podaci. To su, po pravilu, sve vrste izvornih tipova podataka. Na primjer, ako se na ulaz unese broj, tada treba provjeriti da li algoritam radi ispravno, uzimajući u obzir: pozitivne, negativne, cijele i realne brojeve, nulte vrijednosti itd.

Ljudski mozak ostaje glavni alat za provjeru tačnosti algoritma. Naravno, dozvoljeno je koristiti i druge kompjuterske alate za automatizaciju provjere, ali na ovaj ili onaj način, to je osoba koja priprema testove i analizira rezultate. U ovom slučaju postavlja se pitanje zašto nam treba algoritam ako čovjek sve radi sam? Zatim, glavni zadatak algoritma je ponovljeno rješenje 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. Razmotrite 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 treba koristiti za zamjenu životinja.

Forking algoritmi

Kao što ime govori, algoritam ima nekoliko grana. Suština rada je u odabiru jedne od mogućih opcija za računski proces, ovisno o bilo kojim uvjetima. Šematsko grananje je predstavljeno okvirom u obliku romba, unutar kojeg je naznačen uslov, a na njegovim stranama su grane za odabir u zavisnosti od toga da li je uslov tačan ili netačan. Algoritam grananja i primjeri njegove primjene mogu se naći posvuda. U programiranju, ovo je tipična if-else konstrukcija koja se nalazi u gotovo svakom jeziku.

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

Ciklični algoritam

Ciklični 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 proračuni. Tipovi algoritma za petlju i primjer će biti razmotreni u nastavku, ali za sada ćemo navesti glavne korake za izgradnju petlje.

1. Dodjela početne vrijednosti varijablama. Bez ovog uslova, petlja će najvjerovatnije propasti ili napraviti greške.
2. Blok za izračunavanje rezultata. Ovo je glavno tijelo petlje.
3. Provjera uvjeta za kraj cikličkog procesa. Ako zaboravite navesti uvjet pod kojim bi petlja trebala završiti, algoritam će raditi neograničeno.
4. Promjena varijabli. Ovaj blok stupa na snagu nakon provjere uvjeta prekida ako je bio lažan. Ako zaboravite na ovaj blok, ciklus će zauvijek izvršiti jednu radnju i nikada se neće završiti. Stoga je važno da se varijable podvrgavaju nekim promjenama pri svakoj iteraciji petlje.

Postoji nekoliko tipova algoritama petlje: sa postuslovom, preduslovom i parametrom.

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

Druge vrste algoritama

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

• Mehanički algoritmi. Na primjer, rad motora s unutarnjim sagorijevanjem ili montažne linije.
• Probabilistički algoritmi. Njihov rad se zasniva na teoriji vjerovatnoće i matematičkoj statistici.
• Heuristički algoritmi. U svom radu koriste praktična razmatranja, bez rigoroznog matematičkog opravdanja.
• Genetski algoritmi. Primjenjuju biološke ideje u svom radu.

Algoritmi mogu biti jednostavni, složeni, ali svi imaju zajedničke karakteristike. Po ovim karakteristikama uobičajeno je razlikovati tri vrste algoritama s kojima ćemo se upoznati.

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

Generalno, izvršavanje komandi prema algoritmu donekle podsjeća na društvene igre u kojima se učesnici naizmjenično bacaju kockice i hodaju po poljima. Štaviše, na marginama se mogu nalaziti komentari u stilu: „Vrati se 2 ćelije unazad“ ili „Idi 5 ćelija napred“ (Sl. 1).

Rice. 1. Društvena igra ()

Poznata igra „Monopol” ili „Menadžer” je složeniji model izvođenja algoritma (slika 2).

Rice. 2. Igra "Monopol" ()

Suštinska razlika ove igre od jednostavnog izvođenja algoritma je u tome što konačni cilj učesnika nije prolazak puta, već skupljanje novca određenim radnjama.

U zavisnosti od redosleda izvršenja naredbe, mogu se razlikovati tri tipa algoritama:

Linearni algoritmi;

Algoritmi grananja;

Algoritmi ponavljanja.

"monopol"

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

Rice. 4. Igra "Monopol" ()

U trenutku početka, igrači imaju jednak iznos gotovine. Bacajući kockice i pomerajući svoje žetone po igralištu sa petljama, oni stiču nekretnine u puno različitih boja. Kada dođe na lokaciju koju je stekao neprijatelj, igrač je dužan platiti utvrđenu najamninu. Nakon što kupi sve parcele iste grupe boja, učesnik može na njima graditi kuće i hotele, što povećava veličinu zakupa. Cilj svega što se dešava je banalan - uništiti sve rivale.

Prema zvaničnim izvorima - Parker Brothers, koji proizvodi Monopoly od 1935. do danas - legendarna društvena igra nastala je na sljedeći način. Godine 1934., nezaposleni inženjer Charles Darrow (slika 5) pozvao je gore navedeni ured da objavi igru ​​koju je on izmislio o trgovini nekretninama.

Rice. 5. Charles Darrow ()

Otkrivši 52 greške u dizajnu u igri na ploči, braća Parker odbila su pronalazača. On je, s čisto američkim poduzetničkim duhom, otišao u štampariju, naručio 5 hiljada primjeraka igre i prilično ih brzo rasprodao. Shvativši da im profit izmiče iz nosa, braća Parker su na brzinu stekla prava na Monopoly, a sljedeće godine je postala najprodavanija društvena igra u Sjedinjenim Državama, a Darrow je bio živo oličenje američkog sna.

Međutim, u isto vrijeme, poznate su i ranije igre koje upadljivo podsjećaju na "Monopoly". Ispada da je Darrow tek prvi koji je požurio i dobio patent za "narodnu" zabavu? Da i ne. Istraživanja posljednjih godina bacila su svjetlo na misteriju koja stoji iza porijekla Monopolyja.

U drugoj polovini devetnaestog veka, politički ekonomista Henri Džordž živeo je i radio u Sjedinjenim Državama. Predložio je da se svi nameti zamijene jednim porezom - na zemlju. Prožeta njegovim idejama, u januaru 1904. Maggie je dobila patent za društvenu igru ​​The Landlord’s Game, koja i po pravilima i izgledu podsjeća na trenutni „Monopol“. Vjeruje se da je "Igra vlasnika zemlje" imala dvije varijante pravila: igrajući igru ​​prema važećim poreznim zakonima, igrači su prelazili na model koji je predložio George - i navodno su se uvjerili u njegove neophodne prednosti. . Dakle, igra nije bila zabava, već instrument ideološke borbe.

Nije došla do masovne proizvodnje, ali se The Landlord's Game postepeno širila Sjevernom Amerikom u zanatskim kopijama. Nalet interesovanja za društvene igre pao je u godinama Velike depresije: hiljade nezaposlenih ljudi rado su zamišljali sebe kao vreće novca, barem za kockarskim stolom. Pojava preduzimljivog čovjeka poput Charlesa Darrowa trajala je nekoliko mjeseci - i on je došao, decenijama poprimivši slavu jedinog pronalazača "Monopola".

Bilo je, naravno, i onih koji su smatrali da je potrebno da otmu komad od nosilaca autorskih prava. Nelicencirani monopoli preplavili su Kinu. A kod nas su se proizvodili i proizvode vitki redovi klonova - "Broker", "Zadruga", "Upravitelj" (Sl. 6)...

Rice. 6. Igra "Menadžer" ()

U svjetlu nedavnog preispitivanja uloge Darrowa u stvaranju Monopola i isteka autorskih prava, takve kompanije neće biti tužene. Čak i ako pretpostavimo da na svijetu nije postojala Elizabeth Maggie, pravila "Monopola" su odavno prešla u javno vlasništvo. Međutim, Hasbro i dalje drži dio patenta kod sebe: dizajn čipova, grafički dizajn, redoslijed ćelija na polju za igru.

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

Rice. 3. Sijalica ()

Na primjer, sljedeći algoritam za zamjenu pregorele sijalice je linearan (slika 3):

1. isključiti prekidač za svjetlo;

2. Odvrnite pregorelu sijalicu;

3. uvrnuti novu sijalicu;

4. Uključite prekidač da provjerite da li je svjetlo uključeno.

Koristeći blok dijagram, ovaj algoritam se može prikazati na sljedeći način:

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

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

Logika donošenja odluka može se opisati na sljedeći način:

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

U suprotnom<действия 2>

AKO imas novca, ONDA kupi hljeb, NEMOJ ga kupovati DRUGO.

AKO ćeš danas biti u centru, zovi me, INAČE ne.

AKO su lekcije naučene, ONDA idite u šetnju, INAČE naučite lekcije.

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

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

AKO je sebe nazvao teretom, onda se popni pozadi.

AKO želite da budete zdravi, budite raspoloženi.

Oblik organizacije radnji u kojem se, u zavisnosti od ispunjenja ili neispunjenja određenog uslova, izvršava jedan ili drugi niz radnji, naziva se grananje.

Oslikajmo u obliku dijagrama toka slijed radnji učenika 6. razreda koji je zaboravio ključeve od stana, što on zamišlja ovako: „Ako je moja majka kod kuće, onda ću doći i sjesti da obavim moj domaći. Ako mama nije kod kuće, idem da igram fudbal sa prijateljima dok mama ne dođe. Ako nema prijatelja na ulici, ja ću se voziti na ljuljašci dok moja majka ne dođe."

(blok dijagram (sl. 8.) vidi kraj sinopsisa)

Potrebni i dovoljni uslovi

Već smo razgovarali sa vama da postoje neophodni i dovoljni uslovi.

Primjer preduvjeta bi bio:

Da biste postali ljekar, morate završiti diplomu medicine.

Uslov medicinskog obrazovanja je neophodan za rad kao ljekar, ali nije dovoljan. Zaista, ne postaju svi diplomirani lekari.

Primjer dovoljnog uslova bi bio:

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

Ovaj uslov je dovoljan: ako uključite klima uređaj, zaista postaje hladnije. Međutim, ovaj uslov nije neophodan, jer da biste postigli ovaj cilj, možete uključiti ventilator, otvoriti prozor itd.

Naravno, istovremeno postoje neophodni i dovoljni uslovi (takvi uslovi se nazivaju jednako). Na primjer:

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

Zaista, ako je proljeće gotovo, dolazi ljeto, a ako proljeće nije gotovo, onda ljeto ne može doći. Odnosno, uslovi za kraj proljeća i početak ljeta su jednaki.

Koncepti neophodnih, dovoljnih i ekvivalentnih uslova su veoma važni u takvoj grani matematike kao što je matematička logika. Osim toga, vrlo su česti u dokazivanju različitih teorema.

U praksi se često dešavaju zadaci u kojima jednu ili više radnji treba ponoviti više puta, a pritom je ispunjen neki prethodno utvrđeni uslov.

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

1. Uzmite jabuku.

2. Pogledajte da li je pokvaren.

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

Potrebno je izvršiti ovaj skup radnji dok ne ponestane jabuka u kutiji.

Oblik organizacije radnji, u kojem se izvršavanje istog niza radnji ponavlja dok je ispunjen određeni unaprijed utvrđen uslov, naziva se ciklus (ponavljanje).

Poziva se situacija u kojoj se izvođenje petlje nikada ne završava petlja.

Treba razviti algoritme kako bi se izbjegle takve situacije.

Pogledajmo algoritam budilnika na telefonu, koji bi trebao 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 raspravljali smo o tri tipa algoritama - linearnim algoritmima, algoritmima grananja i algoritmima koji se ponavljaju.

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

Eratostenovo sito

Prisjetimo se definicije jednostavnog prirodnog broja.

Prirodni broj se naziva prost ako jeste ima samo dva djelitelja: jedan i sam broj. Ostali brojevi se pozivaju sastavni... Štaviš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. veku pre nove ere, grčki matematičar Eratos-fen predložio je sledeći algoritam za pronalaženje svih prostih brojeva manjih od datog broja P:

1.napiši sve prirodne brojeve od 1 do n;

2. brisati 1;

3. podvuci najmanji od neoznačenih brojeva;

4. Precrtajte sve brojeve koji su višekratnici broja podvučenog u prethodnom koraku;

5. ako lista sadrži neoznačene brojeve, idite na korak 3, inače su svi podvučeni brojevi prosti.

Ovo je ciklični algoritam. Kada se izvrši, koraci 3-5 se ponavljaju sve dok na originalnoj listi ne bude neoznačenih brojeva.

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

Napišimo brojeve od 1 do 25.

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

Pošto nisu svi brojevi označeni, podvuci 3. Sada precrtaj sve brojeve koji su djeljivi sa 3.

Pošto nisu svi brojevi označeni, podvuci 5. Sada precrtaj broj 25.

Pošto nisu svi brojevi označeni, ističemo 7.

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

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

Svi brojevi su sada označeni.

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

Rice. 7.Blok dijagram za zamenu sijalice

Rice. 8. Dijagram toka radnji učenika šestog razreda

Rice. 9. Blok dijagram budilnika

Bibliografija

1. Bossova L.L. Informatika i IKT: Udžbenik za 6. razred. - M.: BINOM. Laboratorija znanja, 2012.

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

3. Bosova L.L., Bosova A.Yu. Nastava informatike u 5-6 razredima: Metodički vodič. - M.: BINOM. Laboratorij znanja, 2010.

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

2. Internet portal "Hipermarket znanja" ()

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

Zadaća

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

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

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

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

Glavni svojstva algoritam su:

1.

2.

3.

4.

·linearni;

· Grananje;

· ciklično.

Linearno

Grananje

ciklično

Struktura programa u Pascalu.

Pascal Je jezik koji uči tačnosti i jasnosti (odjeljci programa se ne mogu mijenjati, potrebno je jasno predstaviti rad programa itd.). Zato je neophodno jasno poznavati i razumeti strukturu Pascal programa.

PROGRAM naziv programa;
(Engleskim slovima, jedna riječ. Želite dublje? Onda trebate koristiti pravila za pisanje identifikatora)

KORISTI biblioteke dodataka (moduli);
(dodatne funkcije, mogu se povezati s programom u ovoj liniji)

LABEL lista etiketa;
(sa jednog mesta programa "skoči" na drugo)

CONST dio koji opisuje konstante;
(konstantne vrijednosti, ne mogu se mijenjati)

TYPE opis tipova varijabli; (vrsta)

VAR definicija globalnih varijabli;
(opis svih varijabli koje se mogu mijenjati u programu)

DEFINICIJA PROCEDURA;

DEFINICIJA FUNKCIJA;

glavni blok programa

Gotovo svaki red prati " ; ". Ovaj znak označava da je linija završena. Znak" ; "ne stavlja se iza službene riječi POČNI i poslednji KRAJ.(što znači kraj programa) nakon čega slijedi tačka.

3.Uslovni operator, operator po izboru. Logičke operacije u Pascalu, tablice istinitosti, osnovni zakoni logičke algebre.
Uslovni operatori

IF [boolean izraz] Tada [naredba 1]; Drugo [operater 2];

Naredba IF radi na sljedeći način: prvo se provjerava rezultat Booleovog izraza. Ako je rezultat TRUE, tada se izvršava [naredba_1] koja slijedi nakon ključne riječi, a [naredba_2] se preskače. Ako je rezultat FALSE, tada se [naredba_1] preskače i [naredba_2] se izvršava.

FOR [cycle_parameter]: = [n_z_p_ts] Za [k_z_p_ts] Uraditi [operator];

ZA, Za, Uradi - službene riječi. [cycle_parameter] je parametar ciklusa. [n_z_p_ts] - početna vrijednost parametra ciklusa. [k_z_p_ts] - konačna vrijednost parametra ciklusa. [operator] je proizvoljan operator.

Parametar petlje mora biti varijabla ordinalnog tipa. Početne i krajnje vrijednosti parametra petlje moraju biti istog tipa kao i parametar petlje.

WHILE [uvjet] Uradite [operater];

DOK, Uradi - službene riječi. [uslov] je izraz logičkog tipa. [operator] je običan operator.

Naredba While radi na sljedeći način: prvo se provjerava rezultat logičkog uslova. Ako je rezultat istinit, tada se izvršava naredba, nakon čega se uvjet vraća u test s novom vrijednošću parametara u logičkom izrazu uvjeta. Ako je rezultat lažan, onda se petlja prekida.

REPEAT [telo petlje]; DO [uvjet];

Naredba REPEAT radi na sljedeći način: prvo se izvršavaju naredbe tijela petlje, nakon čega se provjerava logički uvjet rezultata. Ako je rezultat lažan, tada se vrši povratak na izvršenje operatora sljedećeg tijela petlje. Ako je rezultat tačan, tada izjava izlazi.

Logička I operacija

Logička I operacija se izvodi sa dva bita, nazovimo ih a i b. Rezultat izvršavanja logičke AND operacije će biti jednak 1 ako su a i b jednaki 1, au svim ostalim (drugim) slučajevima rezultat će biti jednak 0. Pogledajmo tabelu istinitosti logičke operacije i .

a	b	a & b

Tipovi podataka.

redni broj:

Wholes; Brain teaser; Symbolic; Enumerable; Interval;

Pravi:

Strukturirano:

nizovi; Strings; Setovi; Unose; Files;

Pointers

6. Nizovi. Definicija, opis, alokacija i upotreba memorije.
Niz je strukturirani tip podataka sa fiksnim brojem elemenata i ima isti tip.

Nekretnina:

svi elementi niza su istog tipa;

niz ima jedno ime za sve elemente;

pristup određenom elementu niza se vrši preko indeksa (s).

7.Procedure i funkcije. Zaglavlje i tijelo procedura i funkcija, klasifikacija parametara. Pozivne procedure i funkcije, posebnosti njihove upotrebe.

Podprogram to je dio programa, dizajniran kao posebna sintaktička struktura i opremljen imenom. "Pozivanje" potprograma, tj. izvršenje akcija navedenih u potprogramu u obliku naredbi može se izvesti u nekom trenutku u programu specificiranjem imena ovog potprograma. Pored specificiranja niza akcija, svaki potprogram može sadržavati opis određenog skupa lokalni objekti - konstante, tipovi, varijable itd. Ovi objekti služe za organiziranje radnji unutar potprograma i imaju smisla (tj. dostupni su ili vidljivi) samo unutra ovaj podprogram

Mehanizam potprograma u Turbo Pascal jeziku je implementiran u obliku procedura i funkcija. Imaju skoro istu strukturu, isto značenje, ali se razlikuju po svrsi i načinu prizivanja.

Procedure služe za postavljanje niza radnji koje imaju za cilj promjenu eksternog u odnosu na programsko okruženje. Procedura se poziva navođenjem njenog imena na mjestu programa gdje se očekuje izvršenje operatora navedenih u proceduri.

Funkcije služe, prije svega, za određivanje algoritma za izračunavanje određene vrijednosti (jednostavnog tipa). Prema tome, poziv funkcije je jedan od valjanih operanda izraza, koji u njemu označava vrijednost koju funkcija izračunava („vraća“).

POSTUPAK ProcedureName (FormalParametersList);
LABEL
Nabrajanje oznaka unutar tijela procedure
CONST
Opis lokalnih konstanti
TYPE
Opis lokalnih tipova
VAR
Opis lokalnih varijabli
POČNI
Procedura na tijelu
KRAJ.

Koncept algoritma. Svojstva, metode opisa. Vrste algoritama.

Algoritam je tačna i razumljiva instrukcija izvođaču da izvrši niz radnji koje imaju za cilj rješavanje problema.

Glavni svojstva algoritam su:

1. determinizam (izvjesnost). Pretpostavlja dobijanje nedvosmislenog rezultata računskog procesa sa datim početnim podacima. Zbog ovog svojstva, proces izvršavanja algoritma je mehaničke prirode;

2. efektivnost. Označava postojanje takvih početnih podataka za koje se računski proces implementiran prema datom algoritmu mora zaustaviti nakon konačnog broja koraka i vratiti željeni rezultat;

3. masovni karakter. Ovo svojstvo pretpostavlja da bi algoritam trebao biti prikladan za rješavanje svih problema ovog tipa;

4. diskretnost. To znači rasparčavanje računskog procesa određenog algoritmom na odvojene faze, čiju mogućnost izvršilac (računar) može izvesti je nesumnjiva.

Uz svu raznolikost algoritama za rješavanje problema, u njima se mogu razlikovati tri glavna tipa računskih procesa:

·linearni;

· Grananje;

· ciklično.

Linearno naziva se računski proces u kojem se sve faze rješavanja problema izvode prirodnim redoslijedom snimanja ovih faza.

Grananje naziva se takav računski proces u kojem izbor pravca obrade informacija zavisi od početnih ili međupodataka (od rezultata provere ispunjenosti nekog logičkog uslova).

Ciklus je dio proračuna koji se više puta ponavlja. Zove se računski proces koji sadrži jedan ili više ciklusa ciklično... Prema broju izvršenja, ciklusi se dijele na cikluse sa određenim (unaprijed određenim) brojem ponavljanja i cikluse sa neograničenim brojem ponavljanja.

Target : Upoznati studente sa osnovama algoritamizacije.

Pitanja za učenje:

1. Algoritam i njegova svojstva. Metode za pisanje algoritama.

2. Glavne vrste algoritama. Blok dijagrami tipičnih algoritama.

Nakon što je proučio ovu temu, student treba da:

znati:

· Svojstva algoritma;

· Blokovi za izgradnju strujnih kola;

· Osnovne vrste algoritama;

Biti u mogućnosti :

· Izgraditi algoritme prema stanju problema;

Koncept algoritma

Koncept algoritma je jedan od temeljnih koncepata informatike, koji se povijesno uobličio u samostalnu disciplinu "teorija algoritama", blisku drugoj disciplini "matematička logika". S druge strane, disciplina "teorija algoritama" se može smatrati srednjom između dvije discipline: matematike i računarstva, vezanih za programski dio.

Algoritamizacija se odnosi na opšte metode informatike, od velikog je značaja u rešavanju složenih problema. Prije pisanja programa za rješavanje problema na računaru, potrebno je pregledati redoslijed radnji koje se moraju izvršiti da bi se problem koji se razmatra ispravno riješio.

Algoritam je niz aritmetičkih, logičkih i drugih operacija potrebnih za izvršenje na računaru.

Da bi se dobio tačan rezultat, algoritam mora biti dizajniran tako da kada se izvrši, sve naredbe se tumače nedvosmisleno. Stoga postoje obavezni zahtjevi koji se moraju uzeti u obzir prilikom kompajliranja algoritama. Zahtjevi su formulirani kao svojstva.

Algoritam mora uvijek biti efikasan, imati svojstvo ponovljivosti i mora biti dizajniran za određenog izvođača. U tehnologiji, takav izvođač je kompjuter. Da bi se osigurala mogućnost implementacije na računaru, algoritam mora biti opisan na jeziku računara koji je razumljiv, odnosno na mašinskom jeziku. Međutim, prije nego što se algoritam predstavi na kompjuterski razumljivom jeziku (mašinskom jeziku), potrebno je napisati program koristeći algoritamski programski jezik.

Algoritam se može predstaviti na različite načine, a posebno:

1) verbalno (verbalni opis);

2) tabelarno;

3) u obliku blok dijagrama;

4) algoritamskim jezikom.

Prilično uobičajen način da se algoritam predstavi je da se napiše na algoritamskom jeziku, koji je, u opštem slučaju, sistem notacije i pravila za jednoobrazno i ​​tačno pisanje algoritama i njihovo izvršavanje. Ovaj način predstavljanja algoritma uključuje njegovo pisanje u obliku programa.

Program Je zapis algoritma u programskom jeziku koji dovodi do konačnog rezultata u konačnom broju koraka.

Poželjno je algoritam predstaviti u obliku blok dijagrama prije pisanja na algoritamskom jeziku. Da biste izgradili algoritam u obliku blok dijagrama, morate znati svrhu svakog od blokova. Tabela 13. navodi tipove blokova i njihovu namjenu.

Tabela 13

		Svrha bloka	Komentar (blok odgovara operatoru)
		Početak ili kraj blok dijagrami
		Ulaz ili izlaz podataka	ulaz / izlaz
		Proces (posebno računarstvo)	zadaci
		Modifikator ciklusa

5.2. Osnovne vrste algoritama

Algoritamizacija djeluje kao skup određenih praktičnih tehnika, posebnih specifičnih vještina racionalnog mišljenja u okviru zadatih jezičkih sredstava. Algoritamizacija proračuna uključuje rješavanje problema u obliku niza radnji, odnosno rješenja predstavljenog u obliku dijagrama toka. Mogu se razlikovati tipični algoritmi. To uključuje: linearne algoritme, algoritme grananja, ciklične algoritme.

Linearni algoritmi

Linearni algoritam je najjednostavniji. Pretpostavlja sekvencijalno izvršavanje operacija. U ovom algoritmu nema provjera uvjeta ili ponavljanja.

Primjer : Izračunaj funkciju z = (x-y) / x + y2.

Nacrtajte dijagram toka za izračunavanje funkcije pomoću linearnog algoritma. Varijabilne vrijednosti X, at može postojati bilo koji, osim nule, za unos sa tastature.

Rješenje: Linearni algoritam za izračunavanje funkcije dat je u obliku blok dijagrama na slici 8. Prilikom izvršavanja linearnog algoritma, vrijednosti varijabli se unose s tipkovnice, zamjenjuju u datu funkciju, rezultat se izračunava, a zatim se prikazuje rezultat.

Slika 8. Linearni algoritam

Svrha blokova na dijagramu na slici 8:

· Blok 1 u dijagramu služi kao logičan početak.

· Blok 3 predstavlja aritmetičku operaciju.

· Blok 4 daje rezultat.

· Blok 5 u kolu služi kao logički završetak kola.

Algoritmi grananja

Algoritam grananja uključuje provjeru uslova za izbor rješenja. U skladu s tim, algoritam će imati dvije grane za svaki uslov.

U primjeru se razmatra algoritam grananja, gdje se, ovisno o uvjetu, bira jedno od mogućih rješenja. Algoritam je predstavljen u obliku blok dijagrama.

Primjer : Kada je uslov ispunjen x>0 funkcija se izračunava: z= ln x+ y, inače, naime, kada x = 0 ili x<0 , funkcija se izračunava: z= x+ y2 .

Nacrtajte dijagram toka za izračunavanje funkcije koristeći algoritam grananja. Varijabilne vrijednosti X, at mogu biti bilo koje, unesite ih sa tastature.

Rješenje : Na slici 9 prikazan je algoritam grananja, gdje se, u zavisnosti od uslova, izvršava jedno od grananja. U dijagramu toka pojavio se novi blok 3 koji provjerava stanje problema. Ostali blokovi su poznati iz linearnog algoritma.

https://pandia.ru/text/78/136/images/image008_57.gif "width =" 300 "height =" 360 src = ">

Slika 9. Algoritam grananja

Primjer : Pronađite maksimalnu vrijednost tri različita cijela broja unesena s tastature. Nacrtajte dijagram toka za rješavanje problema.

Rješenje : Ovaj algoritam pretpostavlja provjeru uvjeta. Za ovo se bira bilo koja od tri varijable i upoređuje s druge dvije. Ako je veći, onda je potraga za maksimalnim brojem završena. Ako uvjet nije ispunjen, tada se uspoređuju dvije preostale varijable. Jedan od njih će biti maksimalan. Blok dijagram za ovaj zadatak je prikazan na slici 10.

https://pandia.ru/text/78/136/images/image010_48.gif "width =" 492 "height =" 456 src = ">

Rice. 10. Blok dijagram traženja maksimuma

Ciklični algoritmi

Ciklični algoritam omogućava ponavljanje jedne ili više operacija, ovisno o stanju problema.

Ciklični algoritmi su dvije vrste:

1) sa datim brojem ciklusa ili sa brojačem ciklusa;

2) broj ciklusa je nepoznat.

Primjer : U petlji izračunajte vrijednost funkcije z = x * y pod uslovom da je jedna od varijabli x promjene u svakom ciklusu za jednu, a drugu varijablu at se ne mijenja i može biti bilo koji cijeli broj. Kao rezultat izvršenja petlje na početnoj vrijednosti varijable x = 1 možete dobiti tablicu množenja. Broj ciklusa može biti bilo koji. Nacrtajte dijagram toka za rješavanje problema.

Rješenje : U primjeru je postavljen broj ciklusa. U skladu s tim, odabire se prvi tip algoritma petlje. Algoritam za ovaj problem prikazan je na Sl. jedanaest.

U drugom bloku se upisuje broj ciklusa n i bilo koji cijeli brojevi X, y .

U blok dijagramu se pojavio novi blok 3 u kojem je varijabla i broji broj ciklusa, povećavajući se za jedan nakon svakog ciklusa dok brojač ne bude jednak i = n ... At i = n posljednji ciklus će biti izvršen.

Treći blok označava opseg promjene brojača ciklusa (od i = 1 prije i = n).

U četvrtom bloku se mijenjaju vrijednosti varijabli: z, x.

Peti blok prikazuje rezultat. Četvrti i peti blok se ponavljaju u svakom ciklusu.

Slika 11. Ciklični algoritam sa brojačem ciklusa

Ova vrsta algoritama petlje je poželjna kada je data brojem petlji.

Ako je broj ciklusa nepoznat, onda se blok dijagrami cikličkih algoritama mogu prikazati u obliku slika 12, 13.

Primjer : Izračunati y = y-xćao y> x, ako y=30 , x=4. Izbrojite broj izvedenih ciklusa, konačnu vrijednost varijable at ... U petlji ispišite vrijednost varijable at, broj izvedenih ciklusa. Nacrtajte dijagram toka za rješavanje problema.

Rješenje : U primjeru, broj ciklusa je nepoznat. U skladu s tim, odabire se drugi tip algoritma petlje. Algoritam za ovaj problem prikazan je na Sl. 12.

Stanje se provjerava na ulazu u petlju. Dva bloka se izvode u tijelu petlje:

1) y = y-x;i= i+1 ;

2) izlaz vrijednosti varijabli i, y.

Ciklus se izvršava sve dok je uslov ispunjen y> x... Pod uslovom da su ove varijable jednake y = x ili y ciklus se završava.

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

Četvrti blok izračunava vrijednost varijable at i= i+1 .

Peti blok prikazuje rezultat:

Varijabilna vrijednost at,

i.

Primjer : Nacrtajte primjer dijagrama toka (slika 12), provjeravajući uvjet izlaza iz petlje. U ovom primjeru, uvjet zadatka se ne mijenja, a izlaz je isti, ali će dijagram toka biti drugačiji.

Rješenje : U ovom slučaju se provjerava uvjet za izlazak iz petlje: y<=x ... Pod ovim uslovom, petlja se ne izvršava. Stanje u blok dijagramu treba prenijeti na kraj ciklusa, nakon što se ispiše. Ciklus se izvršava sve dok je uslov ispunjen y> x.

Algoritam, ako se uslov prenese na kraj ciklusa, se poziva algoritam petlje sa postuslovom... Algoritam za ovaj problem prikazan je na Sl. trinaest.

Drugi blok uvodi y=30 , x=4 .

Treći blok izračunava vrijednost varijable at , broj završenih ciklusa se računa i= i+1 .

Četvrti blok prikazuje rezultat:

Varijabilna vrijednost at,

Broj završenih ciklusa i.

Peti blok provjerava stanje y <= x za izlazak iz petlje. Ako je uslov ispunjen, idite na blok 6, u suprotnom na blok 3 i ciklus se ponavlja.

Slika 13. Algoritam petlje sa postuslovom

Kontrolna pitanja

1. Koncept 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.