Lekce 01 Úvod do algoritmizace

Počítačové laboratoře bez tajemství aneb naučme se učit algoritmizaci a programování s využitím robotů

Lekce 01  Úvod do algoritmizace

„Tento projekt CZ.1.07/1.3.12/04.0006 je spolufinancován Evropským sociálním fondem a státním rozpočtem České republiky.“

  

Vysvětlení základních pojmů Zápis algoritmu pomocí vývojových diagramů Základní stavební prvky algoritmu ◦ Posloupnost ◦ Větvení ◦ Cyklus

CZ.1.07/1.3.12/04.0006

VPSS_L1 (verze 01.2/2012) - Úvod do algoritmizace

2







Algoritmus je postup (posloupnost operací) vedoucí k řešení dané úlohy Algoritmus je vyčerpávající předpis – všechny možnosti, které mohou při řešení úlohy nastat, musí být do algoritmu zařazeny Základní vlastnosti: ◦ Determinovanost – pro každý krok je jednoznačně určen krok, kterým se bude pokračovat ◦ Konečnost – každý výpočet při zadání přípustných vstupních údajů za konečnou dobu skončí a dá požadované výsledky ◦ Hromadnost – algoritmus řeší celou třída konkrétních úloh vzájemně se lišících vstupními údaji

CZ.1.07/1.3.12/04.0006


3



Existuje více způsobů



Slovní popis ◦ Pro exaktní popis je příliš komplikovaný ◦ Závislý na jazyce a způsobu vyjadřování autora



Grafický zápis pomocí vývojového diagramu ◦ Přehledný a jednoznačný zápis algoritmu ◦ Odstraňuje nevýhody slovního popisu algoritmu ◦ Základní značky pro zápis algoritmu (stará norma ČSN 36 9030)

CZ.1.07/1.3.12/04.0006


4





MS Word Project Draw (knihovna Flowchart)

CZ.1.07/1.3.12/04.0006


5



Smart Draw

CZ.1.07/1.3.12/04.0006


6

Operační blok

Rozhodovací blok

Vstupní a výstupní blok

Konkrétní specifikace V/V: tisk, vstup z klávesnice, zobrazení na obrazovce Mezní značka

CZ.1.07/1.3.12/04.0006


7

Start algoritmu

SLOVNÍ POPIS 1.

Přijíždí auto zleva?

ANO

2. NE

Přijíždí auto zprava?

ANO

NE

3.

4.

Přejdi do poloviny cesty

JINÝ SLOVNÍ POPIS

1. Přijíždí auto zprava?

Pokud je cesta volná zleva, pokračuj bodem 2, jinak se vrať k bodu 1. Pokud je cesta volná zprava, přejdi do poloviny cesty a pokračuj bodem 3, jinak se vrať k bodu 1. Zkontroluj, zda je stále volná cesta zprava. Pokud ano, pokračuj bodem 4, jinak opakuj bod 3. Přejdi na druhou stranu.

ANO

2.

NE

Dokonči přecházení cesty

3

Dokud přijíždějí auta zleva čekej, jinak pokračuj bodem 2. Pokud přijíždějí auta zprava, vrať se na bod 1, jinak přejdi do poloviny cesty. Dokud přijíždějí auta zprava, tak čekej, jinak dokonči přecházení.

Konec CZ.1.07/1.3.12/04.0006


8





Obecně lze zapisovat jakýkoliv pokyn bez vazby na nějaký programovací jazyk Příklad: ◦ Uvař čaj, vezmi pero, otoč se doprava o 90° ◦ Sečti čísla x a y ◦ Vypiš druhou mocninu čísla R



Problém může nastat ve fázi přepisu do programovacího jazyka

CZ.1.07/1.3.12/04.0006


9

  



 

Vyjadřují posloupnost vykonávání příkazů Značí se orientovanými úsečkami Pokud není naznačen směr, je implicitní směr shora dolů nebo zleva doprava. Obecně vstupů do bloku může být více, výstup jen jeden (mimo blok větvení). Doporučení je – jen jeden vstup Rozvětvení je povoleno jen v bloku větvení.

CZ.1.07/1.3.12/04.0006


10





Jeden začátek, jeden konec algoritmu Strukturované programování – používání standardních konstrukcí, které odpovídají řídícím strukturám v běžných programovacích jazycích (viz dále)

CZ.1.07/1.3.12/04.0006


11

CZ.1.07/1.3.12/04.0006


12

CZ.1.07/1.3.12/04.0006


13

 





Proměnná je místo pro uložení hodnoty Identifikátor proměnné – představuje pojmenování (pravidla pro identifikátory jsou závislá na jazyce) Typ proměnné – specifikuje, jakou hodnotu lze uložit (typ, rozsah, přesnost) Běžně se rozlišují ◦ Jednoduché proměnné pro celé číslo, reálné číslo, znak, textový řetězec a logickou hodnotu ◦ Strukturované proměnné pro uložení více hodnot (např. pole čísel, záznam pro uschování souvisejících hodnot), přístup pomocí indexů, přístup k jednotlivým položkám

CZ.1.07/1.3.12/04.0006


14

 

Lze zapisovat obecně Příklad:

◦ Do proměnné A ulož součet hodnot X a Y ◦ Do proměnné A ulož hodnotu zadanou z klávesnice ◦ Vypiš obsah proměnné A na obrazovku





Nebo matematickým zápisem (operace přiřazení je různá v jednotlivých jazycích) či nějakým srozumitelným pseudojazykem Příklad: ◦ ◦ ◦ ◦

A=X+Y X=X+1 A←X+Y TISK A

CZ.1.07/1.3.12/04.0006


15

 

Výraz je posloupnost symbolů, konstant a proměnných, která má nějakou hodnotu. Příklad: ◦ ◦ ◦ ◦ ◦





10 X+3 A>B Počet stran Jméno knihy

Podmínka je výraz, na základě kterého můžeme rozhodovat, tj. výraz jehož výsledná hodnota je logického typu (ano-ne, pravda-nepravda) Příklad: ◦ Svítí slunce ◦ A>B

CZ.1.07/1.3.12/04.0006


16

Příkaz 1

CZ.1.07/1.3.12/04.0006

Příkaz 2

Příkaz n


17

Výpočet přepony Načti strany trojúhelníku a,b

c  a 2  b2 Vypiš c Konec

CZ.1.07/1.3.12/04.0006


18

    



Algoritmus na uvaření čaje Napsání dopisu Součet dvou čísel Výpočet obsahu a obvodu kruhu Nakreslení čtverce o zadané straně Většinu reálných úloh pouze s využitím posloupnosti nelze řešit ◦ Dělení dvou čísel, uvaření čaje s možností volby druhu čaje, množství cukru, výpočet směrnice úsečky…

CZ.1.07/1.3.12/04.0006


19

Podmínka

NE

CZ.1.07/1.3.12/04.0006

ANO

NE

Příkaz

Příkaz 2

Podmínka

ANO

Příkaz 1


20

Výpočet přepony Načti a, b

NE

a>b

max = b

ANO

max = a

Vypiš max Konec

CZ.1.07/1.3.12/04.0006


21

      

Uvaření kávy s možností s cukrem, s mlékem Porovnání dvou čísel (větší, menší, rovnost) Maximum tří čísel Porovnání tří čísel Dělení dvou čísel Směrnice přímky, zadané dvěma body Určení, zda čísla a, b, c mohou být stranami trojúhelníka. Pokud ano, zda je pravoúhlý.

CZ.1.07/1.3.12/04.0006


22

Modifikujte na kompletní variantu (komplexní kořeny, a=0, případně a i b = 0) …?

CZ.1.07/1.3.12/04.0006


23

Podmínka V1

Příkaz 2

CZ.1.07/1.3.12/04.0006

V2

Příkaz 2

V3

Příkaz 3

V4

Příkaz 4

V5

Příkaz 5


24



CZ.1.07/1.3.12/04.0006


25

CZ.1.07/1.3.12/04.0006


26

opakuj pro i=1..5 Podmínka

NE

Příkaz

Příkaz

Podmínka

i

ANO

Příkaz

NE

ANO

CZ.1.07/1.3.12/04.0006


27



Cyklus, kde je dopředu znám počet opakování

CZ.1.07/1.3.12/04.0006


28





Cyklus, kde neznám počet opakování Cyklus má ukončovací podmínku

CZ.1.07/1.3.12/04.0006


29

      



Největší společný dělitel dvou čísel Výpočet faktoriálu přirozeného čísla Průměr zadávaných známek Nakreslení pravidelného n-úhelníku Určení, zda je číslo prvočíslem Přihlášení do sítě (zadání jména a hesla) Zdání PIN při platbě kartou (max. dva neúspěšné pokusy) Převod čísla z desítkové do dvojkové soustavy

CZ.1.07/1.3.12/04.0006


30



Napište algoritmus pro zjednodušenou hru NIM – „Odebírání zápalek“ pouze z jedné hromádky ◦ ◦ ◦ ◦



 

Začíná se s počtem N zápalek Střídají se dva hráči Každý odebere 1, 2 nebo 3 zápalky Kdo odebere poslední, prohrál

Jednoduchá varianta – pouze požadavek na funkčnost Složitější varianta s „inteligencí“ – vítězná strategie Originální varianta využívá 3 hromádky

CZ.1.07/1.3.12/04.0006


31

Lekce 01 Úvod do algoritmizace

Recommend Documents