Všetky typy algoritmov. Softvérový spôsob zápisu algoritmov. Popis rôznych algoritmických štruktúr v jazyku blokových diagramov

Programovanie je písanie niečoho pomocou cudzieho cudzieho jazyka. S rozvojom tejto oblasti vedomostí zašli vývojári ešte ďalej a naučili sa zapísať „niečo“ bez toho, aby pochopili, ako to znie v ruštine. Začiatočníci sa učia písať kód priamo v C++ alebo php pomocou mnohých knižníc a vlastne ani nerozumejú tomu, ako to, čo vytvárajú, znie v ich rodnom jazyku. Algoritmizácia sa zaoberá objasnením a priblížením tohto „niečoho“.

Algoritmizácia

Väčšina príkladov algoritmov v informatike, dokonca aj na univerzitách, je študovaná na priemernej úrovni. Je bežnou praxou písať donekonečna viac a viac zložitý kód... Pokusy neskúsených programátorov začať hneď písať programy v programovacom jazyku možno prirovnať k práci novinára, ktorý sotva ovláda základy cudzí jazyk, píše článok do časopisu. Vyhnúť sa podobný problém môžete, ak začnete svoju prácu nahrávať najskôr vo svojom rodnom jazyku, upravíte ju, skontrolujete chyby a nakoniec ju preložíte do požadovaného jazyka.

Výhoda tohto prístupu spočíva najmä v tom, že vývojár sa bude prekladom venovať len 25% času, pričom pri písaní programu v novom jazyku strávi 100% prácou s neznámym jazykom. Zároveň sa ocitne v stiesnených podmienkach a nezvládne dirigovanie dobrá kontrola za chyby a revíziu projektu.

Algoritmizácia pomáha pri implementácii projektu na počítači opísať proces riešenia v natívnom a zrozumiteľný jazyk vo forme diagramu vzájomne prepojených algoritmov analyzujte nápady a získajte čo najkvalitnejší a premyslený kód, ktorý bude odolnejší voči chybám a bude fungovať efektívnejšie.

Koncepcia algoritmu

Počítač nemôže vyriešiť problémy, môže iba fungovať jednoduché akcie v zobrazenom poradí. "A čo kalkulačka?" - pýtaš sa. Je to tiež výsledok práce programátorov, ktorí vytvorili program, ktorý používa určité algoritmy na získanie požadovaných výsledkov. Uvažujme o abstraktnej situácii. Čo by ste mali robiť, ak vás požiadajú, aby ste našli korene kvadratického trinómu osoby, ktorá nie je oboznámená s metódami riešenia rovníc?

Je zrejmé, že musí byť vyškolený na riešenie kvadratických rovníc. To sa deje podľa nasledujúcej schémy:

1. Vyberte si riešenie.
2. Preštudujte si všetky detaily zvolenej metódy.
3. Prvé dva body vysvetlite budúcemu interpretovi v jazyku, ktorému rozumie.

Potom bude možné zadať interpretovi úlohy na vyriešenie kvadratickej rovnice. A ak sú prvé dva kroky jednoduché a priamočiare – všetky riešenia sú popísané v príslušnej literatúre, potom je tretí krok ťažký.

Ako môžete zabezpečiť, že myšlienky použité pri riešení problému budú interpretom vnímané tak, ako ich chápete vy? Tu sa dostávame bližšie ku konceptu algoritmu. Prax ukazuje, že na to, aby sa niekomu niečo správne vysvetlilo, je potrebné dodržať nasledujúce kroky:

• určiť počiatočné údaje (premenná a koeficienty kvadratickej rovnice);
• rozdeliť proces riešenia na jedinečne známe komponenty pre interpreta (diskriminačné vzorce a hľadanie koreňov);
• uveďte poradie krokov (najskôr vypočítajte diskriminant, potom korene);
• stanovte podmienku, za ktorej sa riešenie považuje za úplné (skontrolujte nájdené korene ich dosadením do rovnice namiesto premenných);
• uveďte presne, aký by mal byť výsledok riešenia (korene patria do množiny reálnych čísel).

Opísaný súbor krokov v všeobecný zmysel a je to algoritmus. Algoritmus teda možno chápať ako metódu riešenia úlohy, napísanú pomocou určitých pravidiel, ktoré umožňujú jednoznačné pochopenie vykonávaných akcií a ich poradia. Algoritmy a príklady úloh budú podrobnejšie popísané nižšie.

Základné vlastnosti algoritmu

Diskrétnosť. Proces riešenia problému vždy pozostáva z činností striktne oddelených od seba, nazývaných kroky, ktoré majú určité poradie vykonávania.

Istota. Každý krok musí byť jasný a jednoznačný z hľadiska významu a kľúča činnosti, ktorá sa má vykonať.

Účinnosť. Algoritmus by mal poskytnúť výsledok. V tomto prípade sa počet krokov môže pohybovať v tisícoch alebo miliónoch, no vždy musia viesť k výsledku.

Hromadný charakter. Akýkoľvek algoritmus vyvinutý na riešenie problému musí byť aplikovateľný na všetky problémy tohto typu pre všetky platné vstupné dáta.

Možnosti počítača

Pre správna tvorba algoritmy pre počítače, je dôležité pochopiť ich schopnosti. Uvažujme najskôr o veličinách, s ktorými počítač pracuje. V všeobecný prípad možno ich rozdeliť na číselné a textové, konštanty a premenné.

Pod konštantné čísla rozumie sa všetkým číslam: 3,15, 100, 105, ich vlastnosťou je nemennosť počas celej činnosti programu. Premenné menia svoju hodnotu počas vykonávania kódu a zvyčajne sa označujú písmenami: x, y, max, min atď.

Textové premenné, podobne ako číselné, môžu byť konštantné alebo premenné. V prvom prípade je to len text: "dobrý", "a a b" atď. V druhom je to rovnaké symbolické označenie ako pre číselné premenné: meno, mesto atď. Rozdiel medzi nimi je najmä v pridelená pamäť počítača na uloženie takejto premennej.

Operácie, ktoré je počítač schopný vykonávať:

1. Čítanie údajov zo vstupných zariadení (klávesnica, myš, súbory).
2. Výpočet hodnôt pomocou matematické funkcie: sčítanie, odčítanie, sin, cos, ln atď. – každý programovací jazyk má svoju vlastnú sadu vstavaných funkcií.
3. Výstup dát (na obrazovku, na papier, do sieťového rozhrania).
4. Prechod medzi fázami programu.
5. Porovnanie dvoch hodnôt (väčšia, menšia, rovnaká).

Toto sú základné operácie, ktoré môže vykonávať väčšina programovacích jazykov.

Metódy na popis algoritmov

Verbálne. Toto je najjednoduchší spôsob. Jeho príklad je recept... Používanie jednoduchých matematických vzorcov je povolené.

Grafický. Popis pomocou diagramov. to zvláštnym spôsobom písanie algoritmov pomocou akéhosi všeobecne akceptovaného algoritmického jazyka - obrazcov a blokov, ktoré majú definitívny význam: obdĺžnik - jednoduchý úkon, šikmý rovnobežník - vstup / výstup, kosoštvorec - podmienka atď.

Používanie algoritmického jazyka. Podobne ako pri grafickom je to aj špeciálny spôsob zápisu algoritmu. Existuje veľa algoritmických jazykov. Ich pravidlá nie sú prísne, inak by to bol programovací jazyk. Uvažujme o príklade algoritmu na výpočet miezd v závislosti od dĺžky služby, napísaného pomocou algoritmického jazyka.

Alg mzdy (int ST, real ZP) arg ST res ZP začiatok ak ST

Algoritmický jazyk možno nazvať prísnejšou formou notácie v porovnaní s verbálnou. Používa sa obmedzený súbor slov a ich konštrukcií, ako aj formátovanie so zarážkami. Nevýhodou verbálnej formy a algoritmického jazyka je zhoršujúca sa prehľadnosť algoritmu so zväčšovaním jeho veľkosti. Preto sa tieto metódy môžu použiť iba na vyjadrenie významu malých algoritmov.

Typy algoritmov

Existuje veľké množstvo algoritmov navrhnutých tak, aby vyriešili čo najviac rôzne úlohy... Napríklad každá učebnica vyššej matematiky obsahuje stovky algoritmov: riešenie systému lineárne rovnice, nájdenie extrémov funkcie, výpočet integrálu atď. Pri podrobnom skúmaní ich štruktúry sa však ukazuje, že všetky algoritmy možno rozdeliť do niekoľkých typov. Pozrime sa na tieto typy algoritmov s príkladmi.

• lineárne (výpočet výsledku sčítania alebo násobenia, výmena hodnôt niekoľkých premenných);
• vetvenie (určenie najväčšieho z niekoľkých čísel);
• cyklický (triedenie poľa, výpočet faktoriálu).

Toto sú základné typy. Za zmienku tiež stojí, že v rade literatúry existuje aj štvrtý typ – rekurzívny. Nemá však špeciálne označenie v schematickom zápise a realizuje sa prostredníctvom základných.

Ďalšie podrobnosti o každom algoritme výpočtu s príkladmi budú opísané nižšie.

Princípy algoritmizácie

1. Určite zdrojové údaje.
2. Vyberte si riešenie.
3. Rozdeľte vybranú metódu do krokov na základe možností počítača (programovacieho jazyka).
4. Vykonajte algoritmus vo forme diagramu s jasným poradím krokov.
5. Výstup výsledkov výpočtu.
6. Označte prechod na výstup obvodu.

Ladenie algoritmu

Človek robí chyby a to je fakt. Hlavným parametrom každého algoritmu by mala byť správnosť jeho práce. Ladenie je proces identifikácie a opravy chýb v algoritme. Na to sa berie konkrétna sada počiatočné údaje nazývané test. Sú to spravidla všetky druhy zdrojových dátových typov. Napríklad, ak je na vstup zadané číslo, potom by sa mal skontrolovať algoritmus správna práca berúc do úvahy: kladné, záporné, celé a reálne čísla, nulové hodnoty atď.

Hlavným nástrojom na kontrolu presnosti algoritmu zostáva ľudský mozog... Na automatizáciu kontroly je samozrejme možné použiť aj iné počítačové nástroje, ale tak či onak je to osoba, ktorá pripravuje testy a analyzuje výsledky. V tomto prípade vyvstáva otázka, prečo potrebujeme algoritmus, ak človek robí všetko sám? Potom je hlavnou úlohou algoritmu opakované riešenie určitého typu problému.

Lineárne algoritmy

Lineárny je algoritmus, v ktorom sú kroky sekvenčné jeden po druhom. Každý algoritmus, ktorý neobsahuje vetvy a slučky, je lineárny. Uvažujme o príklade algoritmu, ktorý rieši nasledujúci problém: vlk a zajac sedia v dvoch bunkách, musíte ich vymeniť.

Kľúčom k vyriešeniu tohto problému je dodatočná klietka, ktorá by sa mala použiť na výmenu zvierat.

Forkovacie algoritmy

Ako už názov napovedá, algoritmus má niekoľko vetiev. Podstatou práce je vybrať si jednu z nich možné možnosti výpočtový proces za akýchkoľvek podmienok. Schematické vetvenie je znázornené kosoštvorcovým rámčekom, vo vnútri ktorého je označená podmienka a po jeho stranách sú výberové vetvy podľa toho, či je podmienka pravdivá alebo nepravdivá. Algoritmus vetvenia a príklady jeho použitia nájdete všade. V programovaní je to typické if-others konštruovať, ktorý sa nachádza takmer v každom jazyku.

Uveďme príklad algoritmu na riešenie problému nájdenia najväčšieho z troch čísel.

Cyklický algoritmus

Cyklický algoritmus je algoritmus, v ktorom sa mnohokrát opakujú rovnaké kroky, pri ktorých sa môže meniť iba hodnota konkrétnej premennej, nad ktorou sa vykonávajú výpočty. Typy cyklického algoritmu a príklad budú diskutované nižšie, ale zatiaľ uvedieme hlavné kroky na vytvorenie slučky.

1. Priradenie počiatočnej hodnoty premenným. Bez tejto podmienky slučka s najväčšou pravdepodobnosťou zlyhá alebo urobí chyby.
2. Blok na výpočet výsledkov. Toto je hlavná časť slučky.
3. Kontrola koncového stavu cyklický proces... Ak zabudnete zadať podmienku, za ktorej sa má cyklus skončiť, algoritmus pobeží donekonečna.
4. Zmena premenných. Tento blok nadobudne účinnosť po kontrole podmienky ukončenia, ak bola nepravdivá. Ak na tento blok zabudnete, cyklus vykoná jednu akciu navždy a nikdy sa nedokončí. Preto je dôležité, aby premenné prešli určitými zmenami pri každej iterácii cyklu.

Existuje niekoľko typov cyklických algoritmov: s dodatočnou podmienkou, predbežnou podmienkou a parametrom.

Zostavme cyklický algoritmus na príklade hľadania faktoriálu čísla N.

Iné typy algoritmov

Existuje množstvo ďalších algoritmov, ktoré sa líšia klasifikáciou alebo pôvodom.

• Mechanické algoritmy. Napríklad prevádzka spaľovacieho motora alebo montážnej linky.
• Pravdepodobnostné algoritmy. Ich práca je založená na teórii pravdepodobnosti a matematickej štatistike.
• Heuristické algoritmy. Vo svojej práci používajte praktické úvahy bez prísneho matematického zdôvodnenia.
• Genetické algoritmy. Aplikovať biologické myšlienky vo svojej práci.

V praxi sú najbežnejšie tieto formy prezentácie algoritmov:

· Verbálne (nahrávky v prirodzenom jazyku);

Grafika (obrázky z grafické symboly);

· Pseudokódy (poloformalizované popisy algoritmov v podmienenom algoritmickom jazyku, vrátane prvkov programovacieho jazyka a fráz v prirodzenom jazyku, všeobecne akceptovaná matematická notácia atď.);

· Softvér (texty v programovacích jazykoch).

Verbálnym spôsobom Záznamy algoritmov sú popisom sekvenčných fáz spracovania údajov. Algoritmus je nastavený vo voľnej forme v prirodzenom jazyku. Napríklad. Napíšte algoritmus na nájdenie najväčšieho spoločného deliteľa (GCD) dvoch prirodzených čísel.

Algoritmus môže byť nasledovný:

· Nastavte dve čísla;

Ak sú čísla rovnaké, vezmite ktorékoľvek z nich ako odpoveď a zastavte sa

v opačnom prípade pokračujte vo vykonávaní algoritmu;

· Určte väčšie z čísel;

· Nahraďte väčšie z čísel rozdielom medzi väčším a menším z čísel;

· Zopakujte algoritmus od kroku 2.

Opísaný algoritmus je použiteľný pre akékoľvek prirodzené čísla a mal by viesť k riešeniu problému.

Verbálnym spôsobom nie je široko používaný nasledujúce dôvody:

· Takéto popisy nie sú prísne formalizované;

· Trpieť výrečnosťou záznamov;

· Umožniť nejednoznačnosť výkladu jednotlivých predpisov.

Grafický spôsob prezentácia algoritmov je kompaktnejšia a názornejšia v porovnaní s verbálnou.

Toto grafické znázornenie je tzv schéma algoritmu alebo Bloková schéma.

o grafické znázornenie algoritmus je znázornený ako postupnosť vzájomne prepojených funkčných blokov, z ktorých každý zodpovedá vykonaniu jednej alebo viacerých akcií.

Vo vývojovom diagrame každý typ akcie (zadávanie počiatočných údajov, výpočet hodnôt výrazov, kontrola podmienok, riadenie opakovania akcií, dokončovacie spracovanie atď.) zodpovedá geometrický obrazec, reprezentovaný ako symbol bloku. Symboly blokov sú spojené prechodovými čiarami, ktoré určujú poradie vykonávania akcií.

1) Blok začiatku a konca

Prvok zobrazuje výstup do vonkajšieho prostredia a vstup z vonkajšie prostredie(najbežnejšie použitie je začiatok a koniec programu). Príslušná akcia je zaznamenaná vo vnútri tvaru.

2) Akčný blok

Vykonanie jednej alebo viacerých operácií, spracovanie údajov akéhokoľvek druhu (zmena hodnoty údajov, forma prezentácie, umiestnenie). Vo vnútri obrázku sú samotné operácie napísané priamo, napríklad operácia priradenia: a = 10 * b + c

3) Logický blok

Zobrazuje riešenie alebo funkciu typu spínača s jedným vstupom a dvoma alebo viacerými alternatívnymi výstupmi, z ktorých je možné vybrať len jeden po vyhodnotení podmienok definovaných v rámci tohto prvku. Vstup do prvku je označený čiarou, ktorá zvyčajne vstupuje do horného vrcholu prvku. Ak existujú dva alebo tri výstupy, potom je zvyčajne každý výstup označený čiarou vychádzajúcou zo zostávajúcich vrcholov (bočné a spodné). Ak existujú viac ako tri výstupy, mali by byť zobrazené ako jedna čiara vychádzajúca z hornej časti (zvyčajne zospodu) prvku, ktorý sa potom rozvetvuje. Príslušné výsledky výpočtu možno zapísať vedľa riadkov reprezentujúcich tieto cesty. Príklady riešenia: všeobecne - porovnanie (tri výstupy:>,<, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).

Prevod dát do formy vhodnej na spracovanie (vstup) alebo zobrazenie výsledkov spracovania (výstup). Tento symbol nedefinuje dátový nosič (špecifické symboly sa používajú na označenie typu dátového nosiča).

Typy algoritmov

Forkovací algoritmus - algoritmus obsahujúci aspoň jednu podmienku, v dôsledku ktorého overenia je možné vykonať rozdelenie algoritmu na niekoľko paralelných vetiev.

Lineárny algoritmus je súbor príkazov (inštrukcií) vykonávaných postupne v čase jeden po druhom.

Cyklický algoritmus - algoritmus, ktorý poskytuje viacnásobné opakovanie rovnakej akcie (rovnaké operácie) na nových zdrojových údajoch. Väčšina metód výpočtu a počítania možností je zredukovaná na cyklické algoritmy. Programový cyklus - postupnosť príkazov (séria, telo slučky), ktoré možno vykonať viackrát (pre nové počiatočné dáta), kým nie je splnená určitá podmienka.

Účel lekcie:	zvýšenie záujmu o štúdium predmetu; rozvíjať schopnosť rýchleho myslenia; rozvoj tvorivej činnosti žiakov; rozvoj kognitívnych záujmov.
Ciele lekcie:	1. Vzdelávacie: - Upevniť so študentmi pojmy algoritmus, interpret, systém príkazov interpreta, spôsoby prezentácie algoritmov. - Oboznámiť študentov s typmi algoritmov: lineárny, vetviaci, cyklický. - Naučiť prezentáciu algoritmov vo forme blokových schém. 2. Rozvíjanie: - Aktivizovať kognitívnu činnosť žiakov prostredníctvom multimediálnych učebných pomôcok. - Rozvíjať imaginatívne, kritické, divergentné myslenie. 3. Vzdelávacie: - Zvyšovanie motivácie žiakov na vyučovacej hodine. - Dosiahnutie vedomej úrovne asimilácie materiálu študentmi. - Formovanie zmyslu pre kolektivizmus a zdravú súťaživosť. - Formovanie algoritmického myslenia.
Požiadavky na znalosti a zručnosti:	- Poznať typy algoritmov. - Poznať pojmy: lineárny, vetviaci, cyklický algoritmus. - Vedieť aplikovať získané poznatky pri plnení praktických úloh.
Typ lekcie:	kombinované.
Technológia:	formovanie komunikatívnej kompetencie.
metódy:	- čiastočne prieskumný, praktický; - informačný (verbálny); - popisný a ilustračný.
Vybavenie:	Flipchart na tému (Príloha 1), počítače, zdroj Študentská technologická mapa (Príloha 2), viacúrovňové karty (Príloha 3), lokálna sieť NetOp.

Počas vyučovania

I. Organizačný moment.
1. Pozdrav od chalanov. Ahojte chalani! Sadnúť si! akú máš náladu? Ak je to dobré, usmievajte sa na všetkých! Ak nie, pozrite sa na seba a usmejte sa! Začnime lekciu! Algoritmus som prezentoval slovne. Pozrite sa na tabuľu. Rovnaký algoritmus je znázornený graficky. Dnes sa v lekcii s vami naučíme reprezentovať typy algoritmov pomocou vývojových diagramov (flipchart strana 1).
Epigrafom našej hodiny budú slová slávneho francúzskeho vedca Gustava Guillauma „Cestu zvládne ten, kto kráča, aj ten, kto myslí“.
2. Oznámenie cieľov vyučovacej hodiny.
II. Aktualizácia vedomostí žiakov

Ale skôr, než sa začneme učiť nový materiál. Musíme si pamätať, čo sme sa naučili v poslednej lekcii.

1. Kontrola domácich úloh.
Skontrolujte krížovky, ktoré žiaci vylúštili doma.

odpovede:
1.grafický
2.končatina
3.informácie
4.interpret
5.algoritmus
6.program
7.plánovať
8.počítač
9.nástroj
10.kresba
11.krok

Možnosť 1. "Výsadba sadenice."

Možnosť 2. Epizóda z rozprávky „Husi-labute“.

6. Domáce úlohy.
1. Naučte sa súhrn.
2. Nakreslite na formát A4 príklad cyklického algoritmu a vývojový diagram rozprávky „Kolobok“.

7. Otázky. 1. Aké typy algoritmov rozlišujeme?
2. Aké typy algoritmov sú znázornené na obrázkoch.

Príloha č.3

Viacúrovňové karty
1. Dokončite úlohu číslo 1,2,3 pre zdroj
Vyplňte tabuľku dvoma príkladmi pre každý typ algoritmu.
Vytvorte algoritmus v programe Skicár pomocou príkazov na presun a kopírovanie.
Možnosť 1. (flipchart strana 25).
"Výsadba sadenice".
Možnosť 2. (flipchart strana 26).
Epizóda z rozprávky „Husi-labute“.

Cieľ : Oboznámiť študentov so základmi algoritmizácie.

Študijné otázky:

1. Algoritmus a jeho vlastnosti. Metódy zápisu algoritmov.

2. Hlavné typy algoritmov. Blokové diagramy typických algoritmov.

Po preštudovaní tejto témy by mal študent:

vedieť:

· Vlastnosti algoritmu;

· Bloky pre stavebné obvody;

· Základné typy algoritmov;

Byť schopný :

· Zostavte algoritmy podľa stavu problému;

Koncepcia algoritmu

Pojem algoritmus je jedným zo základných pojmov informatiky, ktorý sa historicky sformoval v samostatnej disciplíne „teória algoritmov“, blízkej inej disciplíne „matematická logika“. Na druhej strane disciplínu "teória algoritmov" možno považovať za strednú medzi dvoma disciplínami: matematikou a informatikou, súvisiacimi s programovaním.

Algoritmizácia sa vzťahuje na všeobecné metódy informatiky, má veľký význam pri riešení zložitých problémov. Pred napísaním programu na riešenie problému na počítači je potrebné preskúmať postupnosť akcií, ktoré je potrebné vykonať na správne vyriešenie uvažovaného problému.

Algoritmus je postupnosť aritmetických, logických a iných operácií, ktoré je potrebné vykonať na počítači.

Na získanie správneho výsledku musí byť algoritmus navrhnutý tak, aby pri jeho vykonávaní boli všetky príkazy jednoznačne interpretované. Preto existujú povinné požiadavky, ktoré sa musia brať do úvahy pri zostavovaní algoritmov. Požiadavky sú formulované ako vlastnosti.

Algoritmus musí byť vždy efektívny, musí mať vlastnosť opakovateľnosti a musí byť navrhnutý pre konkrétneho interpreta. V technológii je takýmto interpretom počítač. Aby sa zabezpečila možnosť implementácie na počítači, algoritmus musí byť popísaný v jazyku počítača, ktorý je zrozumiteľný, teda v strojovom jazyku. Pred prezentovaním algoritmu v počítačovo zrozumiteľnom jazyku (strojovom jazyku) je však potrebné napísať program pomocou algoritmického programovacieho jazyka.

Algoritmus môže byť reprezentovaný rôznymi spôsobmi, najmä:

1) verbálne (slovný opis);

2) tabuľkovo;

3) vo forme blokovej schémy;

4) v algoritmickom jazyku.

Pomerne bežným spôsobom reprezentácie algoritmu je napísať ho v algoritmickom jazyku, čo je vo všeobecnosti systém zápisu a pravidiel pre jednotné a presné zapisovanie algoritmov a ich vykonávanie. Tento spôsob reprezentácie algoritmu zahŕňa jeho písanie vo forme programu.

Program Je záznamom algoritmu v programovacom jazyku, ktorý vedie ku konečnému výsledku v konečnom počte krokov.

Je lepšie prezentovať algoritmus vo forme blokového diagramu pred písaním v algoritmickom jazyku. Ak chcete vytvoriť algoritmus vo forme blokového diagramu, musíte poznať účel každého z blokov. V tabuľke 13. sú uvedené typy blokov a ich účel.

Tabuľka 13

		Účel bloku	Komentár (blok zodpovedá operátorovi)
		Začiatok alebo koniec blokové schémy
		Vstup alebo výstup dát	vstup výstup
		Proces (najmä výpočtová technika)	úlohy
		Modifikátor cyklu

5.2. Základné typy algoritmov

Algoritmizácia pôsobí ako súbor určitých praktických techník, špeciálnych špecifických zručností racionálneho myslenia v rámci daných jazykových prostriedkov. Algoritmizácia výpočtov zahŕňa riešenie problému vo forme postupnosti akcií, to znamená riešenie prezentované vo forme vývojového diagramu. Je možné rozlíšiť typické algoritmy. Patria sem: lineárne algoritmy, vetviace algoritmy, cyklické algoritmy.

Lineárne algoritmy

Lineárny algoritmus je najjednoduchší. Predpokladá postupné vykonávanie operácií. V tomto algoritme nie sú žiadne podmienené ani opakované kontroly.

Príklad : Vypočítajte funkciu z = (x-y) / x + y2.

Zostavte vývojový diagram na výpočet funkcie pomocou lineárneho algoritmu. Variabilné hodnoty NS, pri môžu byť ľubovoľné, okrem nuly, na ich zadávanie z klávesnice.

Riešenie: Lineárny algoritmus na výpočet funkcie je uvedený vo forme blokovej schémy na obr. 8. Pri vykonávaní lineárneho algoritmu sa hodnoty premenných zadávajú z klávesnice, dosadzujú sa do danej funkcie, vypočíta sa výsledok a potom sa zobrazí výsledok.

Obr. 8. Lineárny algoritmus

Účel blokov v diagrame na obr. 8:

· Blok 1 v diagrame slúži ako logický začiatok.

· Blok 3 predstavuje aritmetickú operáciu.

· Blok 4 vypíše výsledok.

· Blok 5 v obvode slúži ako logické ukončenie obvodu.

Algoritmy vetvenia

Algoritmus vetvenia zahŕňa kontrolu podmienok pre výber riešenia. V súlade s tým bude mať algoritmus dve vetvy pre každú podmienku.

V príklade je uvažovaný algoritmus vetvenia, kde sa v závislosti od podmienky vyberie jedno z možných riešení. Algoritmus je prezentovaný vo forme blokového diagramu.

Príklad : Keď je splnená podmienka X>0 funkcia sa vypočíta: z= ln X+ r, inak, totiž keď x = 0 alebo X<0 , funkcia sa vypočíta: z= X+ r2 .

Zostavte vývojový diagram na výpočet funkcie pomocou vetviaceho algoritmu. Variabilné hodnoty NS, pri môžu byť ľubovoľné, zadajte ich z klávesnice.

Riešenie : Obrázok 9 ukazuje algoritmus vetvenia, kde sa v závislosti od podmienky vykoná jedna z vetiev. V blokovej schéme sa objavilo nový blok 3, ktorá kontroluje stav problému. Zvyšné bloky sú známe z lineárneho algoritmu.

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

Obr. 9. Algoritmus vetvenia

Príklad : Nájdite maximálnu hodnotu troch rôznych celých čísel zadaných z klávesnice. Zostavte vývojový diagram riešenia problému.

Riešenie : Tento algoritmus predpokladá kontrolu stavu. Na tento účel sa vyberie ktorákoľvek z troch premenných a porovná sa s ostatnými dvoma. Ak je väčší, hľadanie maximálneho čísla je ukončené. Ak podmienka nie je splnená, potom sa porovnajú dve zostávajúce premenné. Jeden z nich bude maximálny. Bloková schéma tejto úlohy je znázornená na obr.

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

Ryža. 10. Bloková schéma hľadania maxima

Cyklické algoritmy

Cyklický algoritmus umožňuje opakovanie jednej operácie alebo niekoľkých operácií v závislosti od stavu problému.

Cyklické algoritmy sú dvoch typov:

1) s dané množstvo cyklov alebo s počítadlom cyklov;

2) počet cyklov nie je známy.

Príklad : V slučke vypočítajte hodnotu funkcie z = x * y za predpokladu, že jedna z premenných X zmeny v každom cykle o jednu a druhú premennú pri nemení a môže byť ľubovoľné celé číslo. V dôsledku vykonania cyklu na počiatočnej hodnote premennej x = 1 môžete získať tabuľku násobenia. Počet cyklov môže byť ľubovoľný. Zostavte vývojový diagram riešenia problému.

Riešenie : V príklade je nastavený počet cyklov. Podľa toho sa vyberie prvý typ algoritmu slučky. Algoritmus pre tento problém je znázornený na obr. jedenásť.

V druhom bloku sa zadáva počet cyklov n a ľubovoľné celé čísla NS, r .

V blokovej schéme sa objavil nový blok 3, v ktorom je premenná i počíta počet cyklov, pričom sa po každom cykle zvyšuje o jeden, kým sa počítadlo nebude rovnať i = n ... o i = n vykoná sa posledný cyklus.

Tretí blok označuje rozsah zmeny počítadla cyklov (od i = 1 predtým i = n).

Vo štvrtom bloku sa zmenia hodnoty premenných: z, X.

Piaty blok zobrazuje výsledok. Štvrtý a piaty blok sa opakuje v každom cykle.

Obr. Cyklický algoritmus s počítadlom cyklov

Tento typ slučkových algoritmov je preferovaný, ak je daný počtom slučiek.

Ak je počet cyklov neznámy, potom môžu byť blokové schémy cyklických algoritmov prezentované vo forme obrázkov 12, 13.

Príklad : Vypočítajte y = y-X zatiaľ čo r> X, ak r=30 , X=4. Spočítajte počet vykonaných cyklov, konečnú hodnotu premennej pri ... V slučke vypíšte hodnotu premennej pri, počet vykonaných cyklov. Zostavte vývojový diagram riešenia problému.

Riešenie : V príklade je počet cyklov neznámy. Podľa toho sa vyberie druhý typ algoritmu slučky. Algoritmus pre tento problém je znázornený na obr. 12.

Stav sa kontroluje na vstupe do slučky. V tele cyklu sa vykonajú dva bloky:

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

2) výstup hodnôt premenných i, r.

Cyklus sa vykonáva, pokiaľ je splnená podmienka y> x... Za predpokladu, že sú tieto premenné rovnaké y = x alebo r cyklus končí.

Algoritmus zobrazený na obrázku 12 sa volá cyklický predpodmienkový algoritmus, keďže podmienka sa kontroluje na začiatku cyklu alebo na vstupe do cyklu. > X pri vstupe do slučky. Ak je podmienka splnená, prejdite na blok 4, v opačnom prípade na blok 6.

Štvrtý blok vypočíta hodnotu premennej pri i= i+1 .

Piaty blok zobrazuje výsledok:

Variabilná hodnota pri,

i.

Príklad : Zostavte si príklad vývojového diagramu (obrázok 12) a skontrolujte stav výstupu zo slučky. V tomto príklade sa podmienka úlohy nemení a výstup je rovnaký, ale vývojový diagram bude odlišný.

Riešenie : V tomto prípade sa skontroluje podmienka pre opustenie slučky: r<=x ... Za tejto podmienky sa slučka nevykoná. Stav v blokovom diagrame by sa mal po vytlačení preniesť na koniec cyklu. Cyklus sa vykonáva, pokiaľ je splnená podmienka y> x.

Zavolá sa algoritmus, ak sa podmienka prenesie na koniec cyklu slučkový algoritmus s dodatočnou podmienkou... Algoritmus pre tento problém je znázornený na obr. 13.

Druhý blok uvádza r=30 , X=4 .

Tretí blok vypočíta hodnotu premennej pri , počíta sa počet dokončených cyklov i= i+1 .

Štvrtý blok zobrazuje výsledok:

Variabilná hodnota pri,

Počet dokončených cyklov i.

Piaty blok kontroluje stav r <= X opustiť slučku. Ak je podmienka splnená, prejdite na blok 6, v opačnom prípade na blok 3 a cyklus sa zopakuje.

Obr. 13. Slučkový algoritmus s dodatočnou podmienkou

Kontrolné otázky

1. Pojem algoritmu.

2. Typy algoritmov.

3. Základné algoritmické štruktúry.

4. Hlavné bloky grafického algoritmu.

5. Lineárna algoritmická štruktúra. Príklad.

6. Vetvenie. Príklad.

7. Cyklické algoritmické štruktúry. Príklad.

Pri štúdiu informatiky sa veľká pozornosť venuje štúdiu algoritmov a ich typov. Bez znalosti základných informácií o nich nemôžete napísať program ani analyzovať jeho prácu. Štúdium algoritmov začína v školskom kurze informatiky. Dnes zvážime koncept algoritmu, vlastnosti algoritmu, typy.

koncepcia

Algoritmus je určitá postupnosť akcií, ktoré vedú k dosiahnutiu konkrétneho výsledku. Pri zostavovaní algoritmu je podrobne predpísaná každá činnosť interpreta, ktorá ho v budúcnosti privedie k riešeniu úlohy.

Algoritmy sa v matematike často používajú na riešenie určitých problémov. Takže veľa ľudí pozná algoritmus na riešenie kvadratických rovníc s hľadaním diskriminantu.

Vlastnosti

Pred uvažovaním v informatike je potrebné zistiť ich základné vlastnosti.

Medzi hlavné vlastnosti algoritmov je potrebné zdôrazniť nasledovné:

• Determinizmus, teda istota. Spočíva v tom, že každý algoritmus predpokladá získanie určitého výsledku vzhľadom na počiatočné.
• Účinnosť. Znamená to, že za prítomnosti množstva počiatočných údajov sa po dokončení série krokov dosiahne určitý očakávaný výsledok.
• Hromadný charakter. Algoritmus napísaný raz môže byť použitý na riešenie všetkých problémov daného typu.
• Diskrétnosť. To znamená, že každý algoritmus môže byť rozdelený do niekoľkých etáp, z ktorých každá má svoj vlastný účel.

Metódy nahrávania

Bez ohľadu na to, aké typy algoritmov v informatike uvažujete, existuje niekoľko spôsobov, ako ich napísať.

1. Verbálne.
2. Vzorec-slovný.
3. Grafický.
4. Jazyk algoritmu.

Algoritmus je najčastejšie znázornený vo forme blokového diagramu s použitím špeciálnych označení stanovených GOST.

Hlavné typy

Existujú tri hlavné schémy:

1. Lineárny algoritmus.
2. Algoritmus vetvenia alebo vetvenia.
3. Cyklický.

Lineárne

Za najjednoduchšie v informatike sa považuje Zahŕňa postupnosť akcií. Uveďme najjednoduchší príklad algoritmu tohto druhu. Nazvime to „Gathering for School“.

1. Vstaňte, keď zazvoní budík.

2. Umyjeme.

3. Umývame si zuby.

4. Cvičenie.

5. Obliekanie.

6. Jeme.

7. Obujeme sa a ideme do školy.

8. Koniec algoritmu.

Forkovací algoritmus

Vzhľadom na typy algoritmov v informatike si nemožno spomenúť na štruktúru vetvenia. Tento typ predpokladá prítomnosť podmienky, pri ktorej sa v prípade jej vykonania úkony vykonajú v jednom poradí av prípade nesplnenia v inom.

Zoberme si napríklad nasledujúcu situáciu – chodec prechádzajúci cez cestu.

1. Blížime sa k semaforu.

2. Pozeráme sa na semafor.

3. Musí byť zelená (to je podmienka).

4. Ak je podmienka splnená, prechádzame cez cestu.

4.1 Ak nie, počkajte, kým sa nerozsvieti zelená.

4.2 Prechádzame cez cestu.

5. Koniec algoritmu.

Cyklický algoritmus

Pri štúdiu typov algoritmov v informatike by sme sa mali podrobne zaoberať týmto algoritmom, pričom predpokladáme časť výpočtov alebo akcií, ktoré sa vykonávajú, kým nie je splnená určitá podmienka.

Uveďme si jednoduchý príklad. Ak je rozsah čísel od 1 do 100. Musíme nájsť všetko, čo je, tie, ktoré sú deliteľné jedným a samy sebou. Nazvime tento algoritmus „Prvočísla“.

1. Vezmite si číslo 1.

2. Skontrolujte, či je menej ako 100.

3. Ak áno, skontrolujte, či je toto číslo prvočíslo.

4. Ak je podmienka splnená, zapíšte si ju.

5. Vezmite si číslo 2.

6. Skontrolujte, či je menej ako 100.

7. Skontrolujte, či je to jednoduché.

… Berieme číslo 8.

Skontrolujte, či je menej ako 100.

Skontrolujte, či je číslo prvočíslo.

Nie, preskočme to.

Berieme číslo 9.

Preto opakujeme všetky čísla až do 100.

Ako vidíte, kroky 1 – 4 sa budú niekoľkokrát opakovať.

Algoritmy s predbežnou podmienkou, kedy sa podmienka kontroluje na začiatku cyklu, alebo s dodatočnou podmienkou, keď je kontrola na konci cyklu, sa rozlišujú medzi cyklické.

Ďalšie možnosti

Algoritmus je možné kombinovať. Môže byť teda cyklický a rozvetvený zároveň. V tomto prípade sa na rôznych segmentoch algoritmu používajú rôzne podmienky. Takéto zložité štruktúry sú užitočné pri písaní zložitých programov a hier.

Legenda v blokovej schéme

Zvažovali sme, aké typy algoritmov sú v informatike. Nehovorili sme ale o tom, aké označenia sa používajú na ich grafický záznam.

1. Začiatok a koniec algoritmu je napísaný v oválnom rámčeku.
2. Každý tím je zachytený v obdĺžniku.
3. Podmienka je napísaná diamantom.
4. Všetky časti algoritmu sú spojené pomocou šípok.

závery

Uvažovali sme o téme "Algoritmy, typy, vlastnosti". Počítačová veda trávi veľa času štúdiom algoritmov. Používajú sa pri písaní rôznych programov ako na riešenie matematických problémov, tak aj na vytváranie hier a rôznych druhov aplikácií.