Domov › Telefon › Nakreslete, co se stane, když to robot udělá. Management dodavatelů Robot - Knowledge Hypermarket. Jednoduché a složené podmínky

Nakreslete, co se stane, když to robot udělá. Management dodavatelů Robot - Knowledge Hypermarket. Jednoduché a složené podmínky

| §2.3 Návrh algoritmů

Lekce 15
§2.3 Návrh algoritmů

2.3.1. Sekvenční konstrukce algoritmu

Existují různé metody návrh (vývoj, konstrukce) algoritmů. Seznámíme se s jedním z nich - metodou sekvenční konstrukce (zpřesňování) algoritmu. Jinak známá jako metoda shora dolů, shora dolů nebo postupného vývoje.

Proces sekvenční konstrukce algoritmu je následující.

V prvním kroku věříme, že před sebou máme dokonalého interpreta, který „všechno umí a všechno umí“. Stačí tedy určit počáteční data a výsledky algoritmu a prezentovat samotný algoritmus ve formě jediného předpisu - zadání problému (obr. 2.4).

Rýže. 2.4. Lineární algoritmus, který je výsledkem první fáze detailování úkolu

Pokud není účinkující proškolen k provedení daného pokynu, pak je nutné tento pokyn předložit ve formě souboru jednodušších pokynů (příkazů). Postup:

Úkol je rozdělen do několika částí, z nichž každá je jednodušší než celý úkol;
řešení každé části problému je formulováno v samostatném příkazu, který může také přesahovat rámec systému příkazů interpreta;
pokud algoritmus obsahuje instrukce, které přesahují možnosti interpreta, jsou takové instrukce opět prezentovány jako sada ještě jednodušších instrukcí.

Proces pokračuje, dokud nejsou interpretovi jasné všechny pokyny.

Sloučení přijatých pokynů do jediná sada provedených v určité posloupnosti příkazů, získáme požadovaný algoritmus pro řešení původního problému.

2.3.2. Vývoj algoritmu pomocí metody sekvenčního zpřesňování pro robota

Účinkujícího Robota již znáte. Funguje na kostkovaném poli, mezi jehož buňkami mohou být stěny.

Řídicí systém robotického umělce:

Můžete použít více příkazů v jedné podmínce pomocí logické operace A NEBO NE.

Je známo, že Robot je někde ve vodorovné chodbě. Žádná z cel na chodbě není přemalována.

Vytvořme algoritmus, pod jehož kontrolou Robot vybarví všechny buňky této chodby a vrátí se do výchozí pozici.

Představme si akční plán robota v následujících rozšířených krocích (modulech):

Podrobně popisujeme každý z pěti modulů.

1. Abychom vybarvili všechny buňky chodby umístěné nalevo od robota, nařídíme robotovi, aby ustoupil doleva a provedl cyklus - BYE:

vlevo
nts zatím stěna nahoře A malovat spodní část stěny; vlevo
kts

Pod kontrolou tohoto algoritmu Robot vybarví všechny buňky koridoru umístěné nalevo od něj a skončí v buňce nalevo od chodby.

2. Použijte příkaz vpravo pro návrat robota do chodby. Naším úkolem je vrátit Robota do jeho původní buňky. Tato buňka je první nevyplněná buňka umístěná napravo od robota. Pokud je tedy buňka obsazená Robotem zastíněna, posuneme ji doprava.

právo
nts zatím buňka je stínovaná doprava
kts

Pod kontrolou tohoto algoritmu robot skončí v původní buňce.

3. Po provedení příkazu napravo robot projde původní buňkou a obsadí buňku napravo od původní. Nyní můžete malovat přes buňky chodby umístěné napravo od původní.

právo
nts zatím stěna nahoře A malovat spodní část stěny; právo
kts

4. Od, po dokončení předchozí algoritmus, Robot se ukázal být napravo od chodby, povelem doleva ho vrátíme do chodby. Návrat do původní buňky je zajištěn následujícím algoritmem:

vlevo
nts zatím buňka je stínovaná doleva
kts

5. Na příkaz malovat robot vybarví původní buňku. Kompletní program pro ovládání robota vypadá takto:

2.3.3. Pomocné algoritmy

Při konstrukci nových algoritmů často nastávají situace, kdy různá místa Algoritmus vyžaduje stejnou sekvenci kroků zpracování dat. Pro takovou sekvenci kroků je vytvořen samostatný algoritmus, který se nazývá pomocný algoritmus. Algoritmy dříve vyvinuté pro řešení jiných problémů mohou být použity jako pomocné.

Pomocný algoritmus je algoritmus, který se používá zcela jako součást jiného algoritmu.

Příklad 1. V prostředí KuMir vytvoříme algoritmus pro performera Robota, pod jehož kontrolou nakreslí vzor:

Počáteční pozice robota je označena hvězdičkou. Algoritmus používá pomocný algoritmus obrázku.

Při reprezentaci algoritmů pomocí vývojových diagramů se pro označení příkazu pro volání pomocného algoritmu používá blok „předdefinovaný proces“ (obr. 2.5), do kterého je zapsán název (název) pomocného algoritmu, za nímž jsou parametry - vstup údaje a výsledky – jsou uvedeny v závorce.

Rýže. 2.5. Blokovat „předdefinovaný proces“

Pomocný algoritmus činí strukturu algoritmu srozumitelnější.

Příklad 2. Připomeňme si algoritmus pro výpočet stupně s přirozeným exponentem y = a n. Příslušné blokové schéma:

Mocnina s celočíselným exponentem y = a x, kde x je celé číslo, a ≠ 0 se vypočítá takto:

Ve výše uvedeném záznamu se výpočet stupně s přirozeným exponentem objevuje dvakrát. Proto algoritmus pro výpočet stupně s celočíselným exponentem může zahrnovat volání pomocného algoritmu pro výpočet stupně s přirozeným exponentem. Příslušné blokové schéma:

Algoritmus uvedený v blokovém diagramu je hlavní ve vztahu k pomocnému algoritmu v něm volanému.

Parametry použitého pomocného algoritmu jsou hodnoty a, n, y. Jedná se o formální parametry, které se používají k popisu algoritmu. Při specifickém přístupu k pomocnému algoritmu jsou formální parametry nahrazeny skutečnými parametry, tedy přesně těmi hodnotami, pro které bude pomocný algoritmus proveden. Druhy, počet a pořadí formálních a skutečné parametry musí odpovídat.

Příkaz pro vyvolání pomocného algoritmu se provede následovně (obr. 2.6):

1) formální vstupní data pomocného algoritmu jsou nahrazena hodnotami skutečných vstupních dat specifikovaných v příkazu pro volání pomocného algoritmu;
2) pro daná vstupní data se provádějí příkazy pomocného algoritmu;
3) získané výsledky jsou přiřazeny k proměnným s názvy skutečných výsledků;
4) přechod na další tým hlavní algoritmus.

Rýže. 2.6. Schéma pro provedení příkazu pro volání pomocného algoritmu

Algoritmus, který přímo nebo nepřímo obsahuje odkaz na sebe jako pomocný algoritmus, se nazývá rekurzivní.

Podívejme se na několik příkladů rekurzivních algoritmů.

Příklad 3. Algoritmus pro výpočet stupně s přirozeným exponentem n pro libovolný skutečné číslo a může být reprezentován v rekurzivní formě:

Číslo a na mocninu n ( n-tý stupeňčísla a) nejsou nic jiného než součin a n-1 a; zase a n-1 = a n-2 a atd.

Příklad 4. Rekurzivní algoritmus je základ efektivní řešení Hádanky Hanojská věž.

Interaktivní hra „Věže Hanoje“ (195747) vám pomůže zapamatovat si podmínky a algoritmus pro řešení hádanky (http://sc.edu.ru/).

Příklad 5. Podívejme se na konstrukční algoritmus geometrický obrazec, které se říká Kochova sněhová vločka. Krokem stavebního postupu je nahrazení střední třetiny každého ze stávajících segmentů dvěma novými o stejné délce, jak je znázorněno na obrázku:

S každým krokem je postava stále bizarnější. Hranice sněhové vločky Koch - poloha křivky po provedení nekonečné číslo kroky.

NEJDŮLEŽITĚJŠÍ

Jednou z hlavních metod pro konstrukci algoritmů je metoda konstrukce sekvenčního algoritmu. Jeho podstatou je, že: původní problém je rozdělena do několika částí, z nichž každá je jednodušší než celý problém a řešení každé části je formulováno v samostatném týmu; Pokud jsou získány příkazy, které přesahují možnosti interpreta, jsou prezentovány ve formě sady ještě jednodušších pokynů. Proces pokračuje, dokud nejsou interpretovi jasné všechny pokyny.

Pomocný algoritmus- algoritmus použitý zcela jako součást jiného algoritmu.

Algoritmus, který přímo nebo nepřímo obsahuje odkaz na sebe jako pomocný algoritmus, se nazývá rekurzivní.

Otázky a úkoly

1. Přečtěte si prezentační materiály k odstavci obsaženému v elektronická přihláška do učebnice. Doplňuje prezentace informace obsažené v textu odstavce?

2. Proč je při řešení složitého problému obtížné specifikovat vše najednou? nezbytné akce? Diskutujte o této otázce ve skupině.

3. Jaká je metoda sekvenčního zpřesňování při konstrukci algoritmu?

4. Jaká je souvislost mezi metodou konstrukce sekvenčního algoritmu a procesy, jako je psaní eseje nebo příprava na vícedenní pěší výlet?

5. Výška každého z nich je známa n studenti třídy 9A a m studenti 9. třídy. Popište ve velkých blocích algoritmus pro porovnávání průměrné výšky studentů v těchto třídách.

6. V řadě deseti buněk napravo od robota jsou některé buňky stínované. Poslední natřená buňka může sousedit se stěnou. Napište algoritmus, který odstíní buňky nad a pod každou zastíněnou buňkou. Algoritmus zkontrolujte v následujících případech:

7. Proč jsou potřeba pomocné algoritmy?

8. Popište proces provádění příkazu pro volání pomocného algoritmu v hlavním algoritmu.

9. Setkali jste se při studiu matematiky a fyziky s myšlenkou formálních a faktických parametrů? Uveďte příklad.

10. Jaké algoritmy se nazývají rekurzivní? Uveďte příklad rekurze ze života.

11. Vytvořte algoritmy, pod jejichž kontrolou bude robot malovat označené buňky. V případě potřeby použijte pomocný algoritmus.

Performer Robot působí na obdélníkovém kostkovaném poli. Mezi některými buňkami pole mohou být stěny. Některé buňky mohou být přetřeny (obr. 3.11).

Rýže. 3.11

Robot zabírá přesně jednu buňku pole. Pomocí příkazů nahoru, dolů, doleva a doprava se robot přesune do sousední buňky v naznačeném směru. Pokud stojí v cestě zeď, dojde k poruše - zobrazí se zpráva, že není možné provést další příkaz.

Na příkaz malovat robot vybarví buňku, ve které stojí. Pokud již byla buňka přelakována, bude přelakována znovu, ačkoliv nedojde k žádným viditelným změnám.

Je důležité si uvědomit, že robot může provádět pouze správně zapsané příkazy. Pokud například místo příkazu dolů zapíšete, Robot tomuto zadání nerozumí a okamžitě oznámí chybu.

Pamatujte, jak se nazývají chyby v záznamu příkazů. Jakým dalším chybám byste se měli při vývoji algoritmů vyvarovat?

Příklad algoritmu řízení robota

Napišme si program, jehož provedením Robot nakreslí na kostkovaném poli meandr pěti závitů (obr. 3.12).

Rýže. 3.12

Program může vypadat takto:

Zde jsme použili konstrukci opakování, protože přesně identické fragmenty se na obrázku opakují 5krát. Při psaní těla smyčky jsme napsali několik příkazů na jeden řádek oddělené středníky.

Pokud proceduru formalizujete jako smyčku, pak se hlavní program ukáže jako velmi krátký.

Navrhněte svou verzi programu pro kreslení meandru.

Cyklus "na shledanou".

Nyní zkusme napsat program, který vyřeší velmi jednoduchý problém: vybarvi všechny buňky napravo od Robota (obr. 3.13).

Rýže. 3.13

Není však specifikováno, kolik přesně buněk má být natřeno. Je známo, že:

vpravo v neznámé vzdálenosti je zeď;
buňky musí být natřeny, dokud se robot nepřiblíží ke zdi.

Využijme toho, že Robot může analyzovat a hlásit situaci kolem sebe, přičemž zkontrolujte následující jednoduché podmínky:

Je jasné, že prozatím bude podmínka splněna zdarma vpravo, musíte spustit příkazy:

K navrhování takových sekvencí akcí se používá speciální konstrukce algoritmického jazyka - cyklus „zatímco“.

V celkový pohled Smyčka „while“ je napsána takto:

Blokové schéma cyklu „while“ má tvar znázorněný na obr. 3.14.

Rýže. 3.14

Při provádění tohoto cyklu umělec opakuje následující akce:

kontroluje podmínku zapsanou za funkčním slovem BYE;
není-li podmínka splněna (robot odpověděl „Ne“), pak se provádění cyklu ukončí a robot začne provádět příkazy zapsané za servisním slovem END. Pokud je podmínka splněna (robot odpověděl „Ano“), pak robot provede tělo smyčky a znovu zkontroluje podmínku.

Napišme si program, jehož provedením Robot nakreslí meandr na kostkovaném poli (obr. 3.12), jehož počet otáček závisí na poloze pravé stěny.

Zákruta meandru se hodí na kostkované pole, pokud je mezi buňkou obsazenou robotem a pravou stěnou 1 buňka.

V závislosti na výchozí poloze robota se tělo smyčky nemusí provést ani jednou. Tato situace není odmítnutím.

Přemýšlejte o tom, jaká by měla být výchozí pozice robota v programu pro kreslení meandrů, aby se tělo smyčky nikdy neprovedlo.

Kvůli logickým chybám při kompilaci algoritmu může nastat situace zacyklení. To znamená, že podmínka bude vždy splněna a cyklus while se nikdy nedokončí.

Zvažte následující příklad:

Co se stane, když napravo od robota nebude žádná zeď?

Podmínka v cyklu "while" se kontroluje pouze před provedením těla cyklu, ale ne během jeho provádění.

Jednoduché a složené podmínky

V cyklu „while“ lze použít nejen jednoduché, ale i složené podmínky.

Složená podmínka je vytvořena z jedné nebo více jednoduchých podmínek a funkční slova A NEBO NE.

Uvažujme složenou podmínku A a B, kde A, B jsou jednoduché podmínky. Podmínka A a B jsou splněny, když je splněna každá ze dvou jednoduchých podmínek v ní obsažených.

Nechť A je jednoduchá podmínka nahoře zdarma a B jednoduchá podmínka vpravo zdarma. Podívejme se podrobně na ověření složených podmínek A a B - volné nahoře a volné vpravo (obr. 3.15).

Rýže. 3.15

V případě a je splněna podmínka A (volná nahoře), podmínka B je splněna (volná vpravo). Složená podmínka AIV (volné nahoře a volné vpravo) je také splněna.

V případě b je splněna podmínka A, podmínka B splněna není. Složená podmínka A a B není splněna.

V případě c není splněna podmínka A, je splněna podmínka B. Složená podmínka A a B není splněna.

V případě d není splněna podmínka A, není splněna podmínka B Složená podmínka A a B není splněna.

Je nutné zkontrolovat podmínku B ve složené podmínce A AND B, pokud podmínka A není splněna?

Složená podmínka A NEBO B je splněna, když je splněna alespoň jedna ze dvou jednoduchých podmínek v ní obsažených.

Zvažme kontrolu složené podmínky A NEBO B - volné nahoře NEBO volné vpravo (viz obr. 3.15).

V případě a je splněna podmínka A (volná nahoře), podmínka B je splněna (volná vpravo). Složená podmínka A NEBO B (volné nahoře NEBO volné vpravo) je splněna.

V případě b je splněna podmínka A, splněna podmínka B není splněna složená podmínka A NEBO B.

V případě c není splněna podmínka A, je splněna podmínka B. Složená podmínka A NEBO B je splněna.

V případě d není splněna podmínka A, není splněna podmínka B. Složená podmínka A NEBO B není splněna.

Měla by se podmínka B kontrolovat ve složené podmínce A NEBO B, pokud je splněna podmínka A?

Složená podmínka NOT A je splněna, když podmínka A není splněna.

Nechte A - jednoduchou podmínku vystínovat. Zvažme kontrolu složené podmínky NOT A (obr. 3.16).

Rýže. 3.16

V případě, že a, je splněna podmínka A, není splněna podmínka NOT A (NOT šrafovaná).

V případě b, není splněna podmínka A, je splněna podmínka NOT A (NEŠtínováno).

Podívejme se na příklad použití složené podmínky.

Je známo, že Robot je někde ve vertikální chodbě. Žádná z cel na chodbě není přemalována.

Vytvořme algoritmus, pod jehož kontrolou Robot vybarví všechny buňky tohoto koridoru a vrátí se do původní polohy.

Vzhledem k tomu, že robot bude muset pouze malovat přes cely chodby, musíme ho „naučit“ je rozpoznávat. Jak se liší buňky chodby od všech ostatních buněk na hřišti? Z Obr. Obrázek 3.17 ukazuje, že každá buňka chodby vlevo a vpravo je ohraničena zdí.

Rýže. 3.17

Robot je v chodbě, nalevo je zeď a napravo. SKI našeho dodavatele takové podmínky nestanoví. Existují opačné podmínky: levice je volná, pravá je volná. Používáme funkční slovo NOT:

Nutná podmínka bude mít podobu:

Představme si akční plán Robota ve zvětšených krocích (obr. 3.18).

Rýže. 3.18

Pro jednoduchost předpokládejme, že nad a pod chodbou je alespoň jedna buňka bez stěn (jinak budete muset dodatečné kontroly nahoře volný, dole volný).

1. Abychom vybarvili všechny buňky chodby nad robotem, nařídíme robotovi, aby přistoupil a provedl cyklus „prozatím“:

Pod kontrolou tohoto algoritmu Robot vybarví všechny buňky koridoru umístěné nad ním a skončí na buňce vedle horního okraje koridoru.

V jaké výchozí poloze robota se tento cyklus neprovede ani jednou?

2. Podle týmu dolů Vraťme Robota do chodby. Naším úkolem je vrátit jej do výchozího bodu. Tento bod má pouze jeden punc- není přelakovaná. Proto, když je buňka obsazená robotem zastíněná, přesuneme ji dolů:

Pod kontrolou tohoto algoritmu robot skončí v původní buňce.

3. Spuštění příkazu dolů,Robot projde počáteční buňkou a obsadí první buňku umístěnou pod tou původní. Nyní můžete malovat přes buňky chodby umístěné pod původní:

Je možné, že se tato smyčka neprovede ani jednou?

4. Protože po dokončení předchozího algoritmu bude robot pod chodbou, povelem nahoru ho vrátíme do chodby. Návrat do výchozího bodu zajišťuje algoritmus:

5. Při příkazu malovat robot namaluje počáteční bod.

Kompletní program pro ovládání robota vypadá takto:

Příkaz větve

Připomeňme, že forma organizace úkonů, při které se v závislosti na splnění či nesplnění nějaké podmínky provádí buď ten či onen sled úkonů, se nazývá větvení.

Větvení lze znázornit graficky, jak je znázorněno na Obr. 3.19.

Rýže. 3.19

Pro organizaci poboček ve SKI Robot je k dispozici speciální tým LI. Jeho celkový vzhled:

Pomocná slova POKUD, PAK, JINAK mají obvyklý význam.

Mezi THEN a ELSE je zapsána jedna nebo více akcí, které tvoří sérii akcí 1. Mezi ELSE a END je umístěna série akcí 2. Funkční slovo JINAK spolu s řadou akcí 2 může chybět (zkrácená forma větvení).

Nyní nechejte Robota ve vodorovné chodbě, jejíž spodní hranice je pevná a nahoře jsou východy (obr. 3.20). Musíte vést robota celou chodbou a malovat přes buňky chodby, které nemají horní okraje.

Rýže. 3.20

Jediným znakem koridoru je přítomnost spodní hranice, tj. podmínka NE zespodu je volně splněna. Pokud je výše uvedená podmínka splněna volně, pak je třeba buňku přetřít, jinak není třeba ji natírat. Podobně jako v případě malování vertikální chodby předpokládáme, že vlevo a vpravo od horizontální chodby jsou buňky. Blokové schéma algoritmu má podobu znázorněnou na obr. 3.21.

Rýže. 3.21

Naprogramovat:

Krátce o tom hlavním

Performer Robot působí na obdélníkovém kostkovaném poli. Mezi některými buňkami pole mohou být stěny. Některé buňky mohou být přetřeny. Robot zabírá přesně jednu buňku pole.

Systém výkonných příkazů je uveden v následující tabulce:

Robot může provádět smyčku „opakování n-krát“.

Pokud není předem přesně známo, kolikrát se má tělo smyčky provést, použije se speciální konstrukce algoritmického jazyka - smyčka „while“.

V cyklu „while“ lze použít nejen jednoduché, ale i složené podmínky. Složená podmínka se tvoří z jedné nebo více jednoduchých podmínek a pomocných slov AND, OR, NOT.

K organizaci větví poskytuje SKI robota speciální příkaz IF.

Otázky a úkoly

Robot pracuje na pravoúhlém šachovnicovém poli. Mezi některými buňkami pole mohou být stěny. Některé buňky mohou být přetřeny (obr. 3.11).

Na příkaz malovat robot vybarví buňku, ve které stojí. Pokud byla buňka již přetřena, bude přetřena znovu, i když ne viditelné změny se nestane.

Pamatujte, jak se nazývají chyby v záznamu příkazů. Jakým dalším chybám byste se měli při vývoji algoritmů vyvarovat?

Příklad algoritmu řízení robota

Pojďme si napsat naprogramovat, při jehož provedení Robot nakreslí na kostkovaném poli meandr pěti otáček (obr. 3.12).

Program může vypadat takto:

OPAKOVAT 5KRÁT
právo
přemalovat; vlevo
přemalovat; vlevo
přemalovat; nahoru
přemalovat; nahoru
přemalovat; právo; přemalovat
právo; právo; právo
dolů; dolů
KONEC

Zde jsme použili konstrukci opakování, protože přesně identické fragmenty se na obrázku opakují 5krát. Při záznamu těla cyklus a napsali jsme několik příkazů na jeden řádek oddělený středníky.

Pokud proceduru formalizujete jako smyčku, pak se hlavní program ukáže jako velmi krátký.

Pomocný algoritmus:
Otáčení PERC
START
právo
přemalovat; vlevo
přemalovat; vlevo
přemalovat; nahoru
přemalovat; nahoru
přemalovat; právo; přemalovat
právo; právo; právo
dolů; dolů
KONEC

Základní algoritmus:
OPAKOVAT 5KRÁT
zatočit
KONEC

Navrhněte svou verzi programu pro kreslení meandru.

Cyklus "na shledanou".

Nyní zkusme napsat program, který vyřeší velmi jednoduchý problém: vybarvi všechny buňky napravo od Robota (obr. 3.13).

Není však specifikováno, kolik přesně buněk má být natřeno. Je známo, že:

1) vpravo je v neznámé vzdálenosti zeď;
2) buňky je třeba natírat, dokud se robot nepřiblíží ke zdi.

Využijme toho, že Robot může analyzovat a hlásit situaci kolem sebe, přičemž kontrolujeme následující jednoduché podmínky:

zdarma vpravo
ponechán volný
zdarma nahoře
zdarma zespodu
přemalováno

Je jasné, že pokud je podmínka vpravo splněna volně, musíte provést příkazy:

právo
přemalovat

K navrhování takových sekvencí akcí se používá speciální konstrukce algoritmického jazyka - cyklus „zatímco“.

WHILE right je zdarma dělat
právo
přemalovat
KONEC

Obecně je smyčka „while“ zapsána takto:

BYE<условие>DĚLAT
<тело цикла (последовательность команд)>
KONEC

Blokové schéma cyklu „while“ má tvar znázorněný na obr. 3.14.

Při provádění tohoto cyklu umělec opakuje následující akce:

1) kontroluje stav zapsaný za funkčním slovem BYE;

2) není-li podmínka splněna (robot odpověděl „Ne“), provádění cyklu se ukončí a robot začne provádět příkazy zapsané za servisním slovem END. Pokud je podmínka splněna (robot odpověděl „Ano“), pak robot provede tělo smyčky a znovu zkontroluje podmínku.

Napišme si program, jehož provedením Robot nakreslí meandr na kostkovaném poli (obr. 3.12), jehož počet otáček závisí na poloze pravé stěny.

Zákruta meandru se hodí na kostkované pole, pokud je mezi buňkou obsazenou robotem a pravou stěnou 1 buňka.

WHILE right je zdarma dělat
právo
přemalovat; vlevo
přemalovat; vlevo
přemalovat; nahoru
přemalovat; nahoru
stín vpravo; přemalovat
právo; právo; právo
dolů; dolů
KONEC

V závislosti na výchozí poloze robota se tělo smyčky nemusí provést ani jednou. Tato situace není odmítnutím.

Přemýšlejte o tom, jaká by měla být výchozí pozice robota v programu pro kreslení meandrů, aby se tělo smyčky nikdy neprovedlo.

Kvůli logickým chybám při kompilaci algoritmu může nastat situace zacyklení. To znamená, že podmínka bude vždy splněna a cyklus while se nikdy nedokončí.

Zvažte následující příklad:

WHILE right je zdarma dělat
právo; vlevo
KONEC

Co se stane, když napravo od robota nebude žádná zeď?

Podmínka v cyklu while se kontroluje pouze před provedením těla cyklu, ale ne během jeho provádění.

Zvažte, co by se stalo, kdyby robot začal provádět náš program pro kreslení meandrů se smyčkou „zatímco“ v následující výchozí pozici:

Co mají společné smyčky „opakování n-krát“ a „sbohem“? Jaké jsou mezi nimi rozdíly? Jsou k popisu opakujících se akcí potřeba dva konstrukty?

Jednoduché a složené podmínky

V cyklu „while“ lze použít nejen jednoduché, ale i složené podmínky.

Složená podmínka se tvoří z jedné nebo více jednoduchých podmínek a pomocných slov AND, OR, NOT.

Uvažujme složenou podmínku A a B, kde A, B jsou jednoduché podmínky. Podmínka A a B jsou splněny, když je splněna každá ze dvou jednoduchých podmínek v ní obsažených.

Nechť A je jednoduchá podmínka vpravo volně, B jednoduchá podmínka vpravo volně. Podívejme se podrobně na ověření složené podmínky A a B - bez shora. (obr. 3.15).

V případě a je splněna podmínka A (volná nahoře), podmínka B je splněna (volná vpravo). Složená podmínka A a B (volné nahoře a volné vpravo) je také splněna.

V případě b je splněna podmínka A, podmínka B splněna není. Složená podmínka A a B není splněna.

V případě c není splněna podmínka A, je splněna podmínka B. Složená podmínka A a B není splněna.

V případě d není splněna podmínka A, není splněna podmínka B Složená podmínka A a B není splněna.

Je nutné zkontrolovat podmínku B ve složeném stavu AIV, pokud podmínka A není splněna?

Složená podmínka A NEBO B je splněna, když je splněna alespoň jedna ze dvou jednoduchých podmínek v ní obsažených.

Zvažme kontrolu složené podmínky A NEBO B - volné nahoře NEBO volné vpravo (viz obr. 3.15).

V případě a je splněna podmínka A (volná nahoře), podmínka B je splněna (volná vpravo). Složená podmínka A NEBO B (volné nahoře NEBO volné vpravo) je splněna.

V případě b je splněna podmínka A, splněna podmínka B není splněna složená podmínka A NEBO B.

V případě c není splněna podmínka A, je splněna podmínka B. Složená podmínka A NEBO B je splněna.

V případě d není splněna podmínka A, není splněna podmínka B. Složená podmínka A NEBO B není splněna.

Měla by se podmínka B kontrolovat ve složené podmínce A NEBO B, pokud je splněna podmínka A?

Složená podmínka NOT A je splněna, když podmínka A není splněna.

Nechte A - jednoduchou podmínku vystínovat. Zvažme kontrolu složené podmínky NOT A (obr. 3.16).

V případě, že a, je splněna podmínka A, není splněna podmínka NOT A (NOT šrafovaná).

V případě b, není splněna podmínka A, je splněna podmínka NOT A (NEŠtínováno).

Podívejme se na příklad použití složené podmínky.

Je známo, že Robot je někde ve vertikální chodbě. Žádná z cel na chodbě není přemalována.

Pojďme skládat, pod jehož kontrolou Robot přetře všechny buňky této chodby a vrátí se do původní polohy.

Robot je v chodbě, nalevo je zeď a napravo. SKI našeho dodavatele takové podmínky nestanoví. Existují opačné podmínky: levice je volná, pravá je volná. Používáme funkční slovo NOT:

stěna vlevo -> vlevo NE volná
stěna vpravo -> NE volná vpravo

Požadovaná podmínka bude mít podobu:
NOT na levé straně je zdarma A NOT na pravé straně je zdarma.

Představme si akční plán Robota ve zvětšených krocích (obr. 3.18).

Pro jednoduchost předpokládejme, že nad a pod chodbou je alespoň jedna buňka bez stěn (jinak budete muset provést dodatečné kontroly nahoře zdarma, dole zdarma).

1. Abychom vybarvili všechny buňky chodby nad robotem, nařídíme robotovi, aby přistoupil a provedl cyklus „prozatím“:

nahoru
DĚLAT
přemalovat
nahoru
KONEC

Pod kontrolou tohoto algoritmu Robot vybarví všechny buňky koridoru umístěné nad ním a skončí na buňce vedle horního okraje koridoru.

V jaké výchozí poloze robota se tento cyklus neprovede ani jednou?

2. S týmem dolů vrátíme robota do chodby. Naším úkolem je vrátit jej do výchozího bodu. Tento bod má jediný rozlišovací znak - není přelakovaný. Proto, když je buňka obsazená robotem zastíněná, přesuneme ji dolů:

dolů
PŘI malování DO
dolů
KONEC

Pod kontrolou tohoto algoritmu robot skončí v původní buňce.

3. Po provedení příkazu dolů robot projde původní buňkou a obsadí první buňku umístěnou pod původní buňkou. Nyní můžete malovat přes buňky chodby umístěné pod původní:

dolů
DOKUD není levá volná A NE pravá není volná
DĚLAT
přemalovat
dolů
KONEC

Je možné, že se tato smyčka neprovede ani jednou?

4. Protože po dokončení předchozího algoritmu bude robot pod chodbou, povelem nahoru ho vrátíme do chodby. Návrat do výchozího bodu zajišťuje algoritmus:

nahoru
PŘI malování DO
nahoru
KONEC

5. Při příkazu malovat robot namaluje počáteční bod.

Kompletní program pro ovládání robota vypadá takto:

nahoru
DOKUD není levá volná A NE pravá není volná
DĚLAT
přemalovat
nahoru
KONEC
dolů
PŘI malování DO
dolů
KONEC
dolů
DOKUD není levá volná A NE pravá není volná
DĚLAT
přemalovat
dolů
KONEC
nahoru
PŘI malování DO
nahoru
KONEC
přemalovat

Příkaz větve

Připomeňme, že forma organizace úkonů, při které se v závislosti na splnění či nesplnění nějaké podmínky provádí buď ten či onen sled úkonů, se nazývá větvení.

Větvení lze znázornit graficky, jak je znázorněno na Obr. 3.19.

K organizaci větví poskytuje SKI robota speciální příkaz IF. Jeho celkový vzhled:

LI<условие>ŽE<серия действий 1>
JINAK<серия действий 2>
KONEC

Pomocná slova POKUD, PAK, JINAK mají obvyklý význam.

Naprogramovat:

DOKUD zespodu je to zdarma dělat
POKUD je vršek volný PAK
přemalovat
KONEC
právo
KONEC

Krátce o tom hlavním

Performer Robot působí na obdélníkovém kostkovaném poli. Mezi některými buňkami pole mohou být stěny. Některé buňky mohou být přetřeny. Robot zabírá přesně jednu buňku pole.

Systém výkonných příkazů je uveden v následující tabulce:

Robot může provádět smyčku „opakování n-krát“.

Pokud není předem přesně známo, kolikrát se má tělo smyčky provést, použije se speciální konstrukce algoritmického jazyka - smyčka „while“.

V cyklu „while“ lze použít nejen jednoduché, ale i složené podmínky. Složená podmínka se tvoří z jedné nebo více jednoduchých podmínek a pomocných slov AND, OR, NOT.

K organizaci větví poskytuje SKI robota speciální příkaz IF.

Otázky a úkoly

1. Zadejte všechny algoritmy ze tří příkazů, které přesunou robota z jeho původní pozice do buňky B.

Existuje algoritmus pro tento úkol, během kterého robot provede: a) dva kroky; b) čtyři kroky; c) pět kroků; d) sedm kroků; e) 2001 kroků; e) kroky roku 2006?

2. Péťa vytvořil algoritmus, který přenese Robota z buňky A do buňky B natřením některých buněk. Co by měl Kolja s tímto algoritmem udělat, aby získal algoritmus, který přenese robota z B do A a vybarví stejné buňky?

3. Péťa sestavil algoritmus, během kterého se Robot vrátil do své původní polohy. Kolja vymazal jeden z týmů. Při provádění Koljova algoritmu se robot také vrátil do své původní pozice. Který tým vymazal Kolja?

4. Máša vymyslela vzor pro Robota. Kolja vymazal přesně polovinu barevných buněk. Obnovte výkres s vědomím, že je symetrický podle svislé osy. Napište program pro robota.

5. Napište program, pomocí kterého se Robot dostane do buňky B ve všech třech bludištích.

6. Napište program, který robotovi pomůže dostat se do buňky B.

7. Jsou známy dva pomocné algoritmy Robota:

Nakreslete, co se stane, když robot provede následující základní algoritmy:

8. Vytvořte algoritmy, pod jejichž kontrolou bude robot malovat označené buňky:

9. Je známo, že někde napravo od Robota je zeď.

Vytvořte algoritmus, pod jehož kontrolou robot namaluje řadu buněk až ke zdi a vrátí se do původní polohy.

10. Je známo, že někde napravo od Robota je plná buňka.

Vytvořte algoritmus, pod jehož kontrolou robot vybarví řadu buněk až k vybarvené buňce a vrátí se do původní polohy.

11. Je známo, že Robot se nachází vedle levého vchodu do horizontální chodby.

12. Je známo, že Robot je někde ve vodorovné chodbě. Žádná z cel na chodbě není přemalována.

Vytvořte algoritmus, pod jehož kontrolou Robot vybarví všechny buňky této chodby a vrátí se do původní polohy.

13. V řadě deseti buněk napravo od robota jsou některé buňky stínované.

Napište algoritmus, který maluje buňky:

a) pod každou zastíněnou buňkou;
b) nad a pod každou zastíněnou buňkou.

14. Co lze říci o správnosti následujícího fragmentu algoritmu?

KDYŽ je vymalováno UDĚLEJTE TO
POKUD je právo volné PAK
právo
přemalovat
KONEC
KONEC

15 Napište program, pomocí kterého se Robot dostane do buňky B ve všech třech bludištích.

zobecnění a systematizace znalostí na téma Algoritmy,
formování dovedností praktická aplikace znalost;

vzdělávací:

vštěpování odpovědnosti, samostatnosti, sebeúcty, přesnosti při práci;
podpora informační kultura studenti;

vývoj:

formování a rozvoj kognitivních zájmů studentů;
rozvoj schopnosti pracovat s dříve nabytými znalostmi, porovnávat, analyzovat a vyvozovat závěry.

Typ lekce: kombinovaný.

Zařízení:

projektor,
počítačová třída

Plán lekce

Organizační moment - 2 min.
Aktualizace znalostí - 8 min.
Vysvětlení látky a provedení cvičení - 20 min.
Fixace materiálu - 10 min.
Otázky studentů, domácí úkol, shrnutí hodiny – 5 min.

Postup lekce
Organizační moment
Zdravím vás, kontrolujem přítomné.
V předchozích lekcích jsme hovořili o algoritmech, podívali jsme se na jejich typy, typy, vlastnosti a vytvořili jsme algoritmy pro řešení různé úkoly. Dnes budeme používat algoritmy ke správě interpretů. A nejprve si připomeňme, co je to „umělec“.
Aktualizace znalostí
Studenti odpovídají na následující otázky:

Definujte pojem Performer. Uveďte příklady.
Jak se formální performer liší od neformálního? Uveďte příklady.
Co je SKI? Název SKI kalkulačka.
Jaké požadavky jsou kladeny na algoritmy, které mají být provedeny umělcem?

Vysvětlování nového materiálu pomocí projektoru
Prostředí robotického umělce je kostkované pole ohraničené zdí. Uvnitř pole může být také stěna mezi některými buňkami. Robot Executor se může posunout o jedno pole pomocí příkazů pohybu vpravo, vlevo, nahoru, dolů. Pomocí příkazu může také malovat přes čtverce, na kterých stojí přemalovat. Pokud je mezi buňkami zeď, robot ji nemůže projít. Příkazy pro kontrolu nepřítomnosti stěny a toho, zda je buňka přemalována: nahoře volné, dole volné, vpravo volné, vlevo volné, vymalováno (obr. 1).
Cvičení:

Petya sestavil algoritmus, který přenese robota z buňky A do buňky B natřením některých buněk. Co by měl Kolja s tímto algoritmem udělat, aby přenesl robota z B do A natřením stejných buněk?
Petya sestavil algoritmus, během kterého se Robot vrátil do své původní polohy. Kolja vymazal jeden z týmů. Při provádění Koljova algoritmu se robot také vrátil do své původní pozice. Který tým vymazal Kolja?
Viz obr.2

V konečné verzi bude algoritmus pro provádění tohoto úkolu vypadat takto:
Opakujte 5x
nahoru; nahoru; právo; dolů; dolů; právo
konec
Cvičení(obr. 5).
Nyní zvažte následující úkol: vymalujte všechny buňky až ke stěně napravo od robota, za předpokladu, že počet buněk až ke stěně není znám (obr. 6). V tomto případě použijeme algoritmickou konstrukci Smyčka-po(tj. smyčka se provede po kontrole podmínky).

Rýže. 5

Rýže. 6

Cvičení: v předchozím úkolu musíte přebarvit všechny buňky napravo od robota a vrátit se do výchozí pozice.
Odpověď: nts právo je prozatím zdarma
právo
přemalovat
kts
nts zatím vymalováno
vlevo
kts
Složené podmínky se tvoří z jedné nebo více jednoduchých podmínek a pomocných slov AND, OR, NOT. Aby složená podmínka, která kombinuje jednoduché podmínky s logickým spojovacím OR, byla pravdivá, je pravda jeden z jednoduché podmínky v něm obsažené. Aby složená podmínka, která spojuje jednoduché podmínky s logickým spojovacím AND, byla pravdivá, je nutné, aby tato Vše jednoduché podmínky v něm obsažené (obr. 7).

Rýže. 7

Rýže. 8

Fixace materiálu
Úkoly se vyplňují v pracovních sešitech a následuje diskuse o řešeních navržených studenty.
Úkol 1. Pomocí příkazů opakovat A Ahoj přesuňte robota z výchozí pozice do bodu B, pokud není znám počet svislých buněk a délka stěn v bludišti (obr. 8).
Odpověď: opakujte 5krát
nts není volný na pravé straně ještě
nahoru
kts
právo
nts není volný na pravé straně ještě
dolů
kts
právo
konec
Úkol 2. Je známo, že Robot se nachází poblíž vchodu do chodby (délka chodby není známa). Vytvořte pro robota algoritmus, který natře všechny buňky v chodbě a vrátí jej do původní polohy (obr. 9).
Odpověď: právo
nts ještě nejsou osvobozeny shora a nejsou osvobozeny zdola
přemalovat
právo
kts
vlevo
nts zatím vymalováno
vlevo
kts

Rýže. 9

Rýže. 10

DZ, shrnutí lekce
Odpovědi na dotazy žáků, domácí úkoly (obr. 10), známkování za práci v hodině.
Dnes jsme se naučili ovládat Robota, používat cyklické algoritmy k optimalizaci úkolu skládání algoritmu a uvědomili jsme si, že při skládání algoritmů musíme být extrémně opatrní a přesní. V další lekci se budeme dále seznamovat různé možnosti algoritmy pro robota. Děkuji vám všem za pozornost.

Literatura:
1. L Bosová. Informatika a ICT. Učebnice pro 7. třídu. M., Binom, Laboratoř znalostí, 2010.
2. A.G. Kushnirenko, G.V. Lebeděv, Ya.N. Seidelman. Informatika 7-9 tříd. M., Drop, 2003.

navíc:

Ukázkový materiál k hodině informatiky v 9. ročníku „Skládání cyklické algoritmy pro účinkujícího robota“ (14 snímků)

Snímek 1

Snímek 3

Performer Robot. Pomocné algoritmy(2h)

Cíl: představit koncept hlavního a pomocného algoritmu; vysvětlit pravidla pro použití pomocného algoritmu; analyzovat příklady algoritmů pomocí pomocných. Rozvinout praktické dovednosti při konstrukci algoritmů metodou sekvenčního zpřesňování.

Plán lekce

1.Zavedení nových pojmů (hlavní a pomocné algoritmy, volání) a vysvětlení nových pojmů.

2. Analýza příkladů řešení úloh pomocí pomocného algoritmu.

3. Praktická práce

Při řešení některých problémů je vhodné je rozdělit na menší dílčí úkoly, z nichž každý může být formulován jako samostatný algoritmus. V tomto případě se nejprve zkompiluje tzv. hlavní algoritmus, ve kterém se k řešení dílčích úloh používají volání pomocných algoritmů, které se přidávají později. Toto řešení se nazývá metoda sekvenčního zpřesňování. Umožňuje skupině programátorů pracovat na projektu, přičemž každý řeší svůj vlastní dílčí úkol.

V procesu řešení problému lze každý pomocný algoritmus v případě potřeby rozdělit na menší pomocné algoritmy.

Zavolá se příkaz k provedení pomocného algoritmu výzva a je zapsán v těle hlavního algoritmu.

Stejný algoritmus lze považovat za hlavní a pomocný ve vztahu k ostatním algoritmům. V algoritmickém jazyce se nejprve zapíše hlavní algoritmus, poté následují pomocné.

Úkol 1:

Robot je v levém horním rohu pole. Nejsou zde žádné stěny ani malované cely. Vytvořte algoritmus pomocí pomocného algoritmu, který nakreslí čtyři křížky na jednu vodorovnou čáru. Konečná pozice robota může být libovolná.

Řešení

Analýza na desce:

Úkol 2. Robot je v levém horním rohu pole. Nejsou zde žádné stěny ani malované cely. Vytvořte algoritmus, který nakreslí čtverec 8 x 8 do šachovnicového vzoru. Konečná pozice robota může být libovolná.

Praktická práce na PC „Řešení problému pomocí pomocných algoritmů“

Problém 1 . Robot je v levém dolním rohu pole. Nejsou zde žádné stěny ani malované cely. Napište algoritmus, který vykreslí 6 svislé pruhy stejně dlouhých 6 buněk. Konečná pozice robota může být libovolná.

Problém 2 . Pomocí pomocných vytvořte algoritmus pro malování buněk, které tvoří číslo 1212.

Domácí úkol : Vymyslete algoritmus, který nakreslí následující obrázek: K vyřešení problému použijte dva pomocné algoritmy.