Algoritmy I Cvičení č.1, 2
1
ALGI 2016/17
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 2
ALGI 2016/17
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
3
ALGI 2016/17
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
4
ALGI 2016/17
Programátorské desatero • • • • • • • • • • • • • • • • •
5
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 2016/17
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éž
6
ALGI 2016/17
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. 7
ALGI 2016/17
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!
8
ALGI 2016/17
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; }
9
ALGI 2016/17
Visual Studio • • •
• •
10
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 2016/17
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.
11
ALGI 2016/17
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.
12
ALGI 2016/17
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)
13
ALGI 2016/17
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++.
14
ALGI 2016/17
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ů.
15
ALGI 2016/17
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.
16
ALGI 2016/17
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. 17
ALGI 2016/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; 18
ALGI 2016/17
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; 19
ALGI 2016/17
Ří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.
20
ALGI 2016/17
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.
21
P1
P2
ALGI 2016/17
Algoritmy I Cvičení č.2 Číselné soustavy – samostatně přečíst
2
ALGI 2016/17
Čí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} 23
ALGI 2016/17
Čí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}
24
ALGI 2016/17
Číselné soustavy 13
:2
6
1
3
0
1
1
0
1
0
.625*2
1
.25
0
.5
1
.0
1310 = 11012 0.62510 = 0.1012 13.62510 = 1101.1012 11012 = (1*23+1*22+0*21+1*20)10 = 1310
25
ALGI 2016/17
Číselné soustavy 0.110 = = 0*20+0*2-1+0*2-2+0*2-3 +1*2-4 +1*2-5+... = = 0.00011….2
26
0
.1*2
0
.2
0
.4
0
.8
1
.6
1
.2
0
.4
…
… ALGI 2016/17
Čí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é.
27
ALGI 2016/17
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
28
ALGI 2016/17
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
29
ALGI 2016/17
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.
30
ALGI 2016/17
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. 31
ALGI 2016/17
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. 32
ALGI 2016/17
Algoritmy I Cvičení č.2 Řídicí struktury (příkazy pro řízení toku příkazů)
1
ALGI 2016/2017
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.
2
P1
P2
ALGI 2016/2017
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);
} 3
return 0;
ALGI 2016/2017
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;
4
+
P1
Podm
-
P2
ALGI 2016/2017
Selekce (podmínka, větvení) Podmínka neúplná: if (logický_výraz) příkaz;
Podm
-
+ P
5
ALGI 2016/2017
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).
610
ALGI 2016/2017
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.
7
ALGI 2016/2017
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 }
8
Podm
-
+ P1
Pn
ALGI 2016/2017
Cyklus • Cyklus - 1.příklad int i = 1; while (i <= 10) { // příkazy i++; }
9
ALGI 2016/2017
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.
P1
Pn do { tělo cyklu } while (logický_výraz);
10
+
Podm ALGI 2016/2017
Cyklus • Cyklus - 2.příklad int i = 1; do { // příkazy i++; } while (i <= 10);
11
ALGI 2016/2017
Cyklus • Cyklus s pevným počtem opakování for (výraz_start; výraz_stop; výraz_iter) { tělo cyklu }
12
ALGI 2016/2017
Cyklus • Cyklus - 3.příklad for (int i = 1; i <= 10; i++) { // příkazy } for (int i = 2; i <= 100; i += 2) { // příkazy } 13
ALGI 2016/2017
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; }
14
ALGI 2016/2017
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;
} 15
} return 0;
ALGI 2016/2017
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).
16
ALGI 2016/2017
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).
17
ALGI 2016/2017
