49
ALGI 2017/18 1 Algoritmy I Cvičení č.1, 2, 3
ALGI 2017/18 1
Algoritmy I
Cvičení č.1, 2, 3
ALGI 2017/18 2
ALG I, informace
• Cvičící RNDr. Eliška Ochodková, Ph.D., kancelář EA439
[email protected] www.cs.vsb.cz/ochodkova
• Přednášející doc. Mgr. Jiří Dvorský, Ph.D.,
kancelář EA441 [email protected] www.cs.vsb.cz/dvorsky
Přihlášení • Osobní číslo
– Každý uživatel počítačové sítě TUO-Net má automaticky přiděleno osobní číslo.
– Osobní číslo se skládá ze tří písmen a tří (nebo čtyř) číslic, např.: abc123
– Osobní číslo slouží pro identifikaci v počítačových systémech. • Heslo
– Počáteční heslo je uživateli nastaveno jeho rodné číslo (bez lomítka)
– Uživatel je povinen změnit si heslo co nejdříve – Prvotní heslo opravňuje uživatele k 6 přihlášením – Zapomenuté heslo může nastavit fakultní - požádat musíte
osobně - nelze telefonicky či poštou
ALGI 2017/18 3
ALGI 2017/18 4
ALG I, informace • Ukončení – klasifikovaný zápočet
– Tři testy po max 20 bodech, min z každého 10 bodů – Písemka max 40, min 21 bodů
• Opisování NE!!! – Totožné nebo jen mírně modifikované projekty,
neschopnost vysvětlit zdrojový kód apod. – Opisování u testů Disciplinární komise podmíněné nepodmíněné
vyloučení ze studia
ALGI 2017/18 5
Programátorské desatero • Programování je lidská činnost, vyžaduje tedy trénink. • Programování není cíl, ale prostředek k dosažení cíle. • Programování vyžaduje pochopení algoritmizovaného problému. • Programátor přemýšlí. • Programátor pracuje samostatně. • Programátor čte, zejména dokumentaci. • Programátor se stále učí nové věci. • Programátor testuje to, čemu ještě nerozumí. • Programátor umí improvizovat. • Programátor optimalizuje. • Programátor musí umět přecházet plynule mezi více jazyky. • Programátor umí hledat chyby. • Programátor hledá chyby, aby se poučil. • Programátor umí číst cizí kód. Je to poučné. • Programátor píše slušně. • Programátor si musí poradit s více editory. • Programátor musí umět přečíst kód i bez zvýrazněné syntaxe.
ALGI 2017/18 6
ALG I, informace
• Instalace (odkazy na webové stránce cvičícího a přednášejícího) – MS Visual Studio 2015 (univerzální prostředí
C++, C#, Jscript, VB, …) • Zadání – cvičení, … web cvičícího • Literatura tamtéž
Visual Studio • Vytvoření projektu
– FileNew Project – Klikněte na "Visual C++ Projects" v boxu Project Types. – V boxu Templates vyberte "Win32 Console Project”. – Pojmenujte projekt, např. cv1 (nepoužívejte mezery a
speciální znaky) a vyberte adresář, kam se projekt (zdrojové soubory, výsledný program …) uloží.
– Pro druhý a další projekty bude potřeba vybrat „soultion“ nejlépe mějte stále tutéž, vyberte tedy "Add to Solution"
– Klikněte na Next v boxu "Application Settings" vyberte "Empty project" a klikněte na Finish.
ALGI 2017/18 7
ALGI 2017/18 8
Visual Studio • Přidání souboru do projektu • Klikněte (pravým tl.) v okně Solution Explorer na jméno
projektu (cv1) • Klikněte na Add Add New Item • Vyberte "C++ File“ • Pojmenujte v boxu "Name" Váš zdrojový soubor, např.
„HelloWorld “. Soubor obdrží příponu .cpp • A můžeme začít programovat!
ALGI 2017/18 9
První program // Pokud překladač narazí na výskyt #include, zpřístupní
funkce dané knihovny. #include <stdio.h> // hlavní funkce programu int main() { // na konzoli vypíšeme 'Hello world' a odřádkujeme printf("Hello world\n"); // návratová hodnota 0 return 0; }
ALGI 2017/18 10
Visual Studio • Spuštění programu • Debug "Start Without Debugging” CTRL+F5 • Pokud se objeví následující zpráva:
"These project configuration(s) are out of date: ... Would you like to build them?" vyberte "Yes". Tato volba uloží vaše soubory a vytvoří spustitelný (executable) .exe soubor. Pokaždé když modifikujete vaše soubory a chcete znovu spustit váš program musíte na tuto výzvu odpovědět "Yes".
• Program se nyní spustí. • V adresáři vašeho projektu, tj. v adresáři se zdrojovým souborem .cpp, se
vytvořil nový podadresář "Debug„. Váš program, tedy spustitelný soubor s příponou .exe, se uloží do něj.
ALGI 2017/18 11
Kompilační překladač • Překlad ze zdrojového jazyka (např. C++) do cílového
jazyka (Absolutní binární kód, přemístitelný binární kód (.obj, .o), jazyk symbolických instrukcí)
• C++ je kompilovaný jazyk – Ze zdrojového souboru .cpp se sestaví tzv.
přemístitelný modul (.obj), poté se linkuje do spustitelného (.exe) souboru a pak je spuštěn.
Konvence
• Komentáře – Na začátku každého zdrojového souboru (třídy) uveďte:
- stručný popis zdrojového souboru (třídy), - autora či autory, - označení verze (pořadové číslo či datum poslední změny).
– Před každou funkcí by měl být její popis doplněný o popis významu jednotlivých parametrů a návratových hodnot.
– Vlastní kód můžete rovněž doplnit o komentář, zejména pokud jste začátečníci.
ALGI 2017/18 12
Konvence
• Identifikátory – („C like“ jazyky jsou tzv. case senzitivní jazyky – pozor
tedy na malá a velká písmena!) – Prvním symbolem smí být pouze písmeno nebo
podtržítko, poté následuje libovolná kombinace písmen, číslic a podtržítek
– Klíčová slova se píšou malými písmeny! – Jména proměnných a funkcí pište malými písmeny s
využitím podtržítek – Nevhodné je používat dva stejné identifikátory rozlišené
jen velikostí písmen (suma x SUMA)
ALGI 2017/18 13
Konvence
• Srozumitelnosti přispívá vhodná volba názvů¨proměnných, funkcí, tříd, šablon a jiných entit. – Mnemotechnické názvy - např. pocet_bodu nebo
soucet() - jsou rozhodně vhodnější než názvy, které nic neříkají - jako nb nebo S().
– Šetřit na délce názvů přinese víc problémů než úspor. • Funkce main vrací vždy hodnotu typu int.
– Občas (i v učebnicích) můžete spatřit deklaraci void main(), ale ta neodpovídá žádné z norem jazyka C,
ani normě jazyka C++.
ALGI 2017/18 14
Konvence
• Formátování – Na jednom řádku by měl být jeden příkaz, deklarace
jedné proměnné. – Obsah bloku odsaďte vždy o 3 či 4 mezery. V rámci
jednoho bloku by měly být všechny příkazy odsazeny stejně (většina IDE odsazuje sama).
– Otevírací závorka bloku je obvykle na konci řádku (nebo na začátku dalšího, nemíchat oba přístupy), uzavírací samostatná na řádku.
– V řídících strukturách vždy používejte složené závorky pro bloky (a to i v případě, že v bloku je pouze jeden příkaz).
– Používejte mezeru před otevírací závorkou a okolo operátorů.
ALGI 2017/18 15
Konvence
• Formátování – Doporučuje se, aby délka řádku nepřekročila 120
znaků (jazyk poskytuje dostatek možností, jak zkrátit dlouhé řádky pro zápis na potřebnou délku).
– Tabulátor přitom považujte ve shodě s obvyklými programy pro výpis textu za 8 mezer, ale raději se mu vyhněte úplně.
– Podobně výstupy formátujte tak, aby byly optimalizovány pro terminál o 24 řádcích po 120 znacích. Na konci má program zanechat kursor na novém řádku.
ALGI 2017/18 16
Základní pojmy
• Datový typ určuje jakých hodnot může nabývat objekt daného datového typu a množinu přípustných operací nad tímto datovým typem.
• Objektem rozumíme konstantu, proměnnou, výraz a podprogramy.
• Datový typ také určuje, kolik místa (bajtů) bude v paměti pro např. proměnnou tohoto typu vyhrazeno.
ALGI 2017/18 17
Základní pojmy
• Konstanta - veličina, která nemění hodnotu během řešení problému. Může být použita dvěma způsoby: – přímo (63, …), – pojmenováním (označení identifikátorem), (pi jméno
konstanty 3.14 …).
• Proměnná - veličina, která může měnit hodnotu během řešení problému. – Proměnná se zavádí deklarací (pojmenováním a určením
datového typu konkrétní proměnné, event. určením počáteční hodnoty)
int i, k; int j = 1;
ALGI 2017/18 18
Základní pojmy • Výraz se skládá z operátorů, operandů a speciálních znaků
(např. závorky). Operandem může být: – konstanta, – proměnná, – výraz, – volání podprogramu.
• Operand je tvořen opět výrazem: (a + b) / 2 a => c i = 2 • Příkazy popisují jednotlivé kroky algoritmu a jejich
návaznosti. Rozlišujeme jednoduché a strukturované příkazy. Celý algoritmus lze chápat jako jeden příkaz:
Příkaz přiřazení i = 2; ALGI 2017/18 19
Řídící struktury • Jednoduché příkazy
– příkaz přiřazení (operátor přiřazení = ), – (čtení a výpis (čtení a výpis je zpravidla realizován jako
volání podprogramu)). • Strukturované příkazy
– sekvence (posloupnost), – selekce (podmínka), – cyklus.
ALGI 2017/18 20
Sekvence (posloupnost)
• Sekvence je tvořena posloupností jednoho
nebo více příkazů,
pevně daném pořadí. Příkaz se začne provádět až po
ukončení předchozího příkazu.
P1
P2
ALGI 2017/18 21
Algoritmy I
Cvičení č.2 Číselné soustavy – samostatně
přečíst
ALGI 2017/18 2
ALGI 2017/18 23
Číselné soustavy
• Každé číslo lze zapsat v poziční číselné soustavě ve tvaru:
an*zn+an-1*zn-1+…. +a1*z1+a0*z0+a-1*zn-1+a-2*z-2+…..
• V dekadické soustavě reprezentujeme číslo jako posloupnost číslic, které mají různé váhy, podle jejich pozice, tzv. poziční číselná soustava.
172=1*100+7*10+2*1
• Obecný zápis čísla v desítkové poziční číselné soustavě anan-1…a1a0a-1a-2…. má hodnotu
an*10n+an-1*10n-1+…. +a1*101+a0*100+a-1*10n-1+a-2*10-2+….. kde ai ∈ { 0,1,2,3,4,5,6,7,8,9}
ALGI 2017/18 24
Číselné soustavy
• Počítač je sestrojen z logických obvodů, které pracují pouze s hodnotami 0 a 1. Proto je výhodné použít pro zápis čísel dvojkovou (binární) soustavu.
(101)2 = (1*4+0*2+1*1)2 = 510
• Obecný zápis čísla v binární poziční číselné soustavě anan-1…a1a0a-1a-2…. má hodnotu
an*2n+an-1*2n-1+…. +a1*21+a0*20+a-1*2n-1+a-2*2-2+….. kde ai ∈ { 0,1}
ALGI 2017/18 25
Číselné soustavy
1310 = 11012 0.62510 = 0.1012
13.62510 = 1101.1012
11012 = (1*23+1*22+0*21+1*20)10 = 1310
13 :2
6 1
3 0
1 1
0 1
0 .625*2
1 .25
0 .5
1 .0
ALGI 2017/18 26
Číselné soustavy
0.110 = = 0*20+0*2-1+0*2-2+0*2-3
+1*2-4 +1*2-5+... = = 0.00011….2
0 .1*2
0 .2
0 .4
0 .8
1 .6
1 .2
0 .4
… …
ALGI 2017/18 27
Číselné soustavy
• Paměťová buňka se skládá z osmi bitů. • Zápis hodnot do paměťové buňky
– rozmezí (00000000)2 až (11111111) 2 , 0 až 255. • Tento způsob interpretace obsahu paměťové
buňky ovšem neumožňuje zápis záporných čísel. Proto se používá ještě některých dalších způsobů.
• Přímý kód ukládá absolutní hodnotu čísla se znaménkovým bitem, který určí zda se jedná o číslo kladné nebo záporné.
ALGI 2017/18 28
Přímý kód
123 0 |1111011 -123 1 |1111011 • V tomto způsobu kódování dochází k dvojí
reprezentaci nuly. 0 0 |0000000 -0 1 |0000000
ALGI 2017/18 29
Doplňkový kód
• Číslo v doplňkovém kódu interpretujeme tak, že nejvyšší váha má zápornou hodnotu -(2n). V případě osmibitové reprezentace je tedy hodnota nejvyšší váhy -128.
(1|0000000)2=(1*-27+0*26+.....+0*20)10 =(-128)10 (1|0000001)2 =(1*-27+0*26+.....+0*21+1*20)10 =(-127)10 (1|1111111)2 =(1*-27+1*26+.....+1*20)10 =(-1)10 (0|0000000)2 =(0*-27+0*26+.....+0*20)10 =(0)10 (0|0000001)2 =(0*-27+0*26+.....+0*21+1*20)10 =(1)10 (0|1111111)2 =(0*-27+1*26+.....+1*20)10 =(127)10
ALGI 2017/18 30
Reálná čísla
• Vzhledem k tomu, že libovolný interval reálných čísel obsahuje nekonečný počet hodnot, není možné nalézt jednoznačné zobrazení mezi libovolným reálným intervalem a konečným počtem hodnot, který dává k dispozici kódování do n bitů.
• Do n bitů lze zakódovat nejvýše 2n hodnot. Proto je i počet reálných čísel zakódovaných v n bitech maximálně 2n.
• Reálná čísla jsou v počítači reprezentována vždy s určitou chybou. Tato chyba závisí na velikosti kódovaného intervalu reálných čísel, na počtu bitů do nichž reálné číslo kódujeme a na způsobu jakým kódování provádíme.
ALGI 2017/18 31
Pevná řádová čárka
• Při zobrazení čísla v pevné řádové čárce je číslo zakódováno do n bitů tak, že prvních m bitů odpovídá celé části a zbylých d bitů odpovídá zlomkové části. Takové kódování se pak ve zkratce označuje jako kódování m.d. Stejně jako u celých čísel lze použít přímý i doplňkový kód. Nejčastěji se ale používá doplňkový kód, aby bylo možné používat i záporná čísla.
• Příklad: V kódování 8.4 zapište číslo (13.625)10. (13.625)10=(00001101.1010) 2 • Při kódování s pevnou řádovou čárkou v
doplňkovém kódu m.d je nejmenší zobrazitelné číslo -2m-1 a největší zobrazitelné číslo 2m-1-2-d.
ALGI 2017/18 32
Pohyblivá řádová čárka
• Pro zobrazení velkých čísel bychom potřebovali neúměrné množství bitů. Například pro číslo 10300
přibližně 1000 bitů. Navíc u tak velkých čísel lze obvykle pracovat s menší absolutní přesností (bity nižších řádů lze zanedbat). Obdobná situace je u čísel se zápornými exponenty.
• Proto se číslo s pohyblivou řádovou čárkou skládá ze dvou částí: mantisy a exponentu. Mantisa je číslo s pevnou řádovou čárkou a exponent celé číslo. Hodnota reálného čísla r s mantisou m a exponentem e se vypočte podle vzorce r=m*2e.
ALGI 2017/18 33
Algoritmy I
Cvičení č. 2, 3 Řídicí struktury (příkazy pro řízení
toku příkazů)
ALGI 2017/18 34
Sekvence (posloupnost)
• Sekvence je tvořena posloupností jednoho nebo více příkazů, které se provádějí v pevně daném pořadí. Příkaz se začne provádět až po ukončení předchozího příkazu.
P1
P2
ALGI 2017/18 35
Sekvence (posloupnost) • Sekvence - příklad (Algoritmus na výpočet průměru dvou
daných celých čísel) int main() { int scit1 = 5; int scit2 = 2; int prumer 0; prumer = (scit1+ scit2) / 2; printf(“Prumer je: %d“, prumer); return 0; }
ALGI 2017/18 36
Podmínka (selekce, větvení) • Selekce - provedení
dalšího kroku je podmíněno splněním podmínky.
Podmínka úplná: if (logický_výraz) příkaz1; else příkaz2;
P1
Podm+ -
P2
ALGI 2017/18 37
Selekce (podmínka, větvení)
Podmínka neúplná: if (logický_výraz) příkaz;
P
Podm
+
-
Ternární operátor • Ternární operátor slouží k vytvoření tzv. podmíněného
výrazu, syntaxe: log_vyraz ? výraz1 : výraz2 • Zapíšeme-li například tento podmíněný výraz:
cislo1 < 5 ? cislo2++ : cislo2-- • hodnota proměnné cislo2 se zvýší o jedničku (provede se
výraz1) pokud je hodnota proměnné cislo1 menší než 5 (podmínka (log_vyraz) je splněna). Pokud je hodnota proměnné cislo1 větší nebo rovna 5 (tedy podmínka není splněna), hodnota proměnné cislo2 se sníží (provede se vyraz2).
ALGI 2017/18 38 10
ALGI 2017/18 39
Cyklus
• Cyklus je část algoritmu, která je opakovaně prováděna po splnění určité podmínky (řídící podmínka cyklu). Opakující se kroky nazýváme tělo cyklu.
• Dva typy cyklů: – indukční – tělo cyklu se provede po splnění řídící
podmínky cyklu nebo dojde k předání řízení za tělo cyklu (cyklus s testem před vykonáním těla cyklu, cyklus s testem za tělem cyklu),
– iterační - počet opakování těla cyklu závisí na hodnotě řídící proměnné cyklu.
ALGI 2017/18 40
Cyklus • Cyklus s podmínkou
před vykonáním těla cyklu - u tohoto cyklu dochází k ukončení v případě, že podmínka není splněna. Tělo cyklu se nemusí vykonat ani jednou.
while (logický_výraz) { tělo cyklu }
P1
Podm
+
-
Pn
ALGI 2017/18 41
Cyklus
• Cyklus - 1.příklad
int i = 1; while (i <= 10) { // příkazy i++; }
ALGI 2017/18 42
Cyklus • Cyklus s podmínkou za
tělem cyklu - tělo cyklu provede minimálně jednou, protože k prvnímu testování podmínky dojde až po prvním průchodu tělem cyklu.
do { tělo cyklu } while (logický_výraz);
P1
Podm+-
Pn
ALGI 2017/18 43
Cyklus
• Cyklus - 2.příklad int i = 1; do { // příkazy i++; } while (i <= 10);
ALGI 2017/18 44
Cyklus
• Cyklus s pevným počtem opakování
for (výraz_start; výraz_stop; výraz_iter) { tělo cyklu }
ALGI 2017/18 45
Cyklus
• Cyklus - 3.příklad
for (int i = 1; i <= 10; i++) { // příkazy } for (int i = 2; i <= 100; i += 2) { // příkazy }
ALGI 2017/18 46
Switch • Příkaz switch na základě hodnoty výrazu provádí
příslušnou větev příkazu, výraz musí být typu int. Syntaxe: switch (výraz) { case konstanta1: case konstanta2: příkaz1; break; case konstanta3: příkaz2; break; case konstanta4: příkaz3; break; // ... default: příkaz; break; }
ALGI 2017/18 47
int main() { int cislo = 0; switch (cislo) { case 1 : case 2 : case 3 : printf(“Zadano cislo 1, 2 nebo 3. \n“); break; case 4 : printf(“Zadano cislo 4. \n“); break; default : printf(“Zadano neco jineho. “); break; } return 0; }
ALGI 2017/18 48
Příkazy break a continue
• Příkazy break a continue ovlivňují průběh zpracování příkazů v rámci cyklu (příkaz break se používá i v příkazu switch). – výsledkem použití příkazu break bude skok za
konec tohoto cyklu, – continue způsobí, že je přeskočen zbytek těla
cyklu a znovu se testuje podmínka cyklu (provede se iterace cyklu).
ALGI 2017/18 49
Příkaz return
• Příkazy return ukončí provádění metody (funkce), v metodě main() ukončí return provádění celého programu. Pomocí return se také vrací nějaká hodnota, viz později funkce (metody).
