Algoritmy a datové struktury

Úvod Základní řídící struktury Jednoduchá proměnná Struktury Pole Vícerozměrná pole Konec

Algoritmy a datové struktury

1 / 34


Obsah přednášky

I

Základní řídící struktury I I I I I

posloupnost příkazů podmínka cyklus s podmínkou na začátku cyklus s podmínkou na konci cyklus s pevným počtem opakování

I

Jednoduchá proměnná

I

Struktury (třídy)

I

Pole

I

Matice

2 / 34


Posloupnost příkazů

I

Nejjednodušší konstrukce

I

Sled postupně prováděných příkazů, bez možnosti změny Příklad

I

1. Vezmi konvici 2. Napusť vodu 3. Dej vařit I

Ve většině jazyků se bloky nějak oddělují I I

I

složené závorky klíčová slova

Pro lepší orientaci se většinou odsazují o několik znaků

3 / 34


Posloupnost příkazů – Java

{ x=z; z=x; } I

Horní zápis ve většině případů neudělá to co jsme si představovali

{ pomoc = x ; x=z; z = pomoc ; }

4 / 34


Podmínka

I

I

Umožňuje provádět některý z bloků příkazů v závislosti na splnění podmínky – větvení programu Příklad 1. Vezmi konvici 2. Jestliže je prázdná, pak napusť vodu jinak si dej pauzu 3. Dej vařit

I

Podmínka může být úplná či neúplná (chybí větev jinak)

I

Ve většině jazyků se podmínka uvádí klíčovým slovem IF

I

Větev jinak (ELSE) se vztahuje k nejbližšímu IF

5 / 34


Podmínka – Java

if ( znamka >1) { System . out . println ( " Prosel skvele " ); } else if ( znamka >2) { System . out . println ( " Prosel jen taktak " ); } else { System . out .. println ( " Neprosel " ); }

6 / 34


Přepínač

I

Přepínač je podobný podmínce I I

umožňuje vícenásobné větvení většinou dost omezený

switch ( mesic ) { case 1 : System . out . println ( " leden " ); break ; case 2 : System . out . println ( " unor " ); break ; ... case 12 : System . out . println ( " prosinec " ); break ; default : System . out . println ( " asi mate spatny kalendar " }

7 / 34


Cyklus s podmínkou na začátku

I I

Dokud není splněna podmínka, umožňuje vykonávat činnost Příklad 1. Vezmi konvici 2. Dokud není voda pro tři lidi 2.1 přidej 1 hrneček vody

3. Dej vařit I

Pokud je podmínka splněna hned na začátku, příkazy v cyklu se neprovedou

I

Ve většině jazyků se uvádí slovem WHILE

8 / 34


Cyklus s podmínkou na začátku – Java

pocitadlo = 3; while ( pocitadlo <3) { pocitadlo ++; }

9 / 34


Cyklus s podmínkou na konci

I I

Umožňuje vykonávat činnost, dokud není splněna podmínka Příklad 1. 2. 3. 4.

I

Vezmi konvici Přidej 1 hrneček vody Pokud není voda pro tři lidi, opakuj 2 Dej vařit

Pokud je podmínka splněna hned na začátku, příkazy v cyklu se stejně provedou

10 / 34


Cyklus s podmínkou na konci – Java

pocitadlo = 3; do { pocitadlo ++; } while ( pocitadlo <3);

11 / 34


Cyklus s pevným počtem opakování

I I

Umožňuje vykonávat činnost, po předem daný počet opakování Příklad 1. Vezmi konvici 2. Pro počet hrnečků 1 až 3 2.1 Přidej hrneček vody

3. Dej vařit I

Ve většině jazyků se používá klíčové slovo FOR

I

Cyklus nemusí proběhnout ani jednou

12 / 34


Cyklus s pevným počtem opakování – Java

I

V javě (a ostatních C příbuzných jazycích) trochu divoký zápis

for ( int i =0; i <5; i ++) { System . out . println ( " i je menší než 5 " ); }

13 / 34


Sudé číslo

I

Zjistěte zda dané číslo A je sudé

14 / 34


Sudé číslo

’ vstup : číslo A ’ výstup : ANO pokud je sudé , jinak NE jestliže a modulo 2 = 0 , pak vrať ANO jinak vrať NE

15 / 34


Dělitelné dvěma nebo třema

I

Zjistěte zda dané číslo A je dělitelné dvěma nebo třema

16 / 34


Dělitelné dvěma nebo třema

’ vstup : číslo A ’ výstup : ANO pokud je dělitelné dvěma nebo třema , jinak NE jestliže A modulo 2 = 0 , pak vrať ANO jinak jestliže A modulo 3 = 0 , pak vrať ANO jinak vrať NE

nebo ’ vstup : číslo A ’ výstup : ANO pokud je dělitelné dvěma nebo třema , jinak NE jestliže ( A modulo 2 = 0) nebo ( A modulo 3 = 0) , pak vrať ANO jinak vrať NE

17 / 34


Dělitelné dvěma a třema

I

Zjistěte zda dané číslo A je dělitelné dvěma a třema

18 / 34


Dělitelné dvěma a třema

’ vstup : číslo A ’ výstup : ANO pokud je dělitelné dvěma a třema , jinak NE jestliže A modulo 2 = 0 , pak jestliže A modulo 3 = 0 , pak vrať ANO jinak vrať NE jinak vrať NE

nebo ’ vstup : číslo A ’ výstup : ANO pokud je dělitelné dvěma a třema , jinak NE jestliže ( A modulo 2 = 0) a ( A modulo 3 = 0) , pak jinak vrať NE

19 / 34


Dělitelné něčím – prvočíslo

I

Zjistěte zda dané číslo A je prvočíslo

I

Číslo je prvočíslo, pokud je dělitelné pouze samo sebou a jedničkou

20 / 34



I

Zjistěte zda dané číslo A je prvočíslo

I

Číslo je prvočíslo, pokud je dělitelné pouze samo sebou a jedničkou Musíme zjistit dělitelnost každým z čísel 2,3,4,. . . A-1

I

I I

Cyklus s pevným počtem opakování Pokud je dělitelné jedním z nich, pak není prvočíslo

20 / 34



’ vstup : číslo A ’ výstup : ANO pokud je prvočíslo , jinak NE pro I od 2 do A -1 jestliže A modulo I = 0 , pak vrať NE vrať ANO

21 / 34



I

Nelze to vylepšit?

22 / 34



I

Nelze to vylepšit?

I

Stačí testovat jen do odmocniny, pokud je dělitelné nějakým vyšším, muselo být dělitelné i nižším

22 / 34


Struktury

I

Data je lepší sdružovat do logických celků popisujících nějakou entitu I

I

Ke strukturám lze přidávat i funkčnost I

I

např. vozidlo má kola např. vozidlo se pohybuje

V objektově orientovaném programování (např. Java) lze od obecných entit dědit entity specializované I

specializovaným případem vozidla je motorové vozidlo – má navíc motor

23 / 34


Geometrický bod

I

Navrhněte strukturu (třídu), která bude popisovat bod na čtverečkovaném papíře

24 / 34


Geometrický bod

třída Bod řádek sloupec

25 / 34


Vzdálenost bodů

I

Napište algoritmus, který vypočte vzdálenost dvou bodů

26 / 34


Geometrický bod

’ vstup : bod A a B ’ výstup : vzdálenost A a B řádky = B . řádek - A . řádek sloupce = B . sloupec - A . sloupec vrať odmocnina z ( řádky * řádky + sloupce * sloupce )

27 / 34


Nejvzdálenější body

I

Napište algoritmus, který načte 10 dvojic bodů a určí dvojici s největší vzdáleností

28 / 34


Nejvzdálenější body

’ vstup : dvojice bodů ’ výstup : body C a D s největší vzdáleností největší vzdálenost <- 0 pro i od 1 do 10 načti dvojici bodů A a B vypočítej vdálenost bodů A a B jesltiže je vzdálenost > největší vzdálenost , pak největší vzdálenost <- vzdálenost C <- A D <- B vrať C a D

29 / 34


Pole

I

Pole je posloupnost dat stejného typu I I

I

Díky přímému přístupu k prvkům je pole velmi rychlé I I

I

je uložena v souvislém bloku paměti k prvkům lze přistupovat pomocí indexu jedna z nejzákladnějších struktur přístupné ve většině jazyků

Nevýhodou je omezená velikost

30 / 34


Vkládání prvku do pole

I

Napište algoritmus, který bude načítat čísla a ukládat je do pole velikosti 10. Pokud zaplní celé pole, začne nejstarší hodnoty přepisovat novými. Algoritmus se ukonči když uživatel zadá -1

31 / 34


Vkládání prvku do pole

’ vstup : čísla z klávesnice , pole A velikosti n ’ výstup : v poli posledních n načtených hodnot velikost <- n pozice <- 0 opakuj načti i A [ pozice ] <- i pozice <- pozice + 1 jestliže pozice = velikost , pak pozice <- 0 dokud i různé od -1

32 / 34


Najděte a překopírujte

I

Najděte v poli A všechna sudá čísla a zkopírujte je do pole B

33 / 34


Najděte a překopírujte

I

Najděte v poli A všechna sudá čísla a zkopírujte je do pole B

I

Doma vyzkoušejte

33 / 34


Konec

34 / 34

Algoritmy a datové struktury

Recommend Documents