Přednášky KIV/PPA1, A. Netrvalová, 2010 5. přednáška

Obsah 5. přednášky:

Pole - motivace

Deklarace, vytvoření, inicializace pole

Mechanismus vytváření pole, reference

Pole jako parametr či návratová hodnota

Změna pole daného parametrem

Kopie polí

Pole reprezentující množinu

Vícerozměrná pole, matice

Tato tematika je zpracována v

Záznamy přednášek: str. 91 - 110

Problém: Proveďte jednoduchou analýzu zadaného textu (četnost výskytu písmen).

Zadání a nástin řešení bude uveden na konci přednášky.

Strana 2 (celkem 16)

Pole - motivace

Úkol – zjistit četnost číslic v jednořádkovém textu.

int nula = 0; int jedna = 0; int dva = 0; ... int osm = 0; int devet = 0;

String text = sc.nextLine(); int i=0; while(i<text.length()){ char znak = text.charAt(i); if(znak >= '0' && znak <= '9'){ switch (znak){ case '0': nula++; break; case '1': jedna++; break; case '2': dva++; break;

... case '8': osm++; break; case '9': devet++; break; default: break; } } i++; } System.out.println("0: " + nula); System.out.println("1: " + jedna); System.out.println("2: " + dva);

... System.out.println("8: " + osm); System.out.println("9: " + devet);

Řešení pomocí přepínače = zdlouhavé, obtížná modifikace,

např. pro písmena, ... NE!!!

d123y 662098 0: 1 1: 1 2: 2 3: 1 4: 0 5: 0 6: 2 7: 0 8: 1 9: 1

Strana 3 (celkem 16)

Pole - terminologie - strukturovaný datový typ

- pevné délky (počet prvků, dán při vzniku)

- prvky (položky) pole

- typ: libovolný, ale pro všechny prvky stejný typ (homogenní datová struktura)

- index: přístup k prvkům, typicky int (0 počet-1)

Deklarace, vytvoření, inicializace

Deklarace

datovyTyp[] jmenoPole;

Příklad: int [] mePole;

Vytvoření (v Javě se s polem pracuje jako s objektem)

jmenoPole = new datovyTyp [velikostPole];

Příklad: tyden = new int [7];

Deklarace a vytvoření současně:

datovyTyp[] jmenoPole = new datovyTyp [velikostPole];

Příklad: double [] teplota = new double[5];

Inicializace

Užitím cyklu:

for (int i = 0; i < teplota.length; i++)

teplota[i] = 37 + (double)i/10;

Výčtem hodnot:

double [] teplota = {37.0, 37.1, 37.2, 37.3, 37.4};

Strana 4 (celkem 16)

Mechanismus vytváření pole, reference

Deklarace

int [ ] a = new int[3];

má tento efekt:

– lokální proměnné a se přidělí paměťové místo v zásobníku, které však neobsahuje prvky pole, ale je „dimenzováno“ na uložení čísla reprezentujícího adresu jiného paměťového místa

– operátorem new se v jiné paměťové oblasti rezervuje (alokuje) úsek potřebný pro pole 3 prvků typu int

– adresa tohoto úseku se uloží do a, při grafickém znázornění reprezentace v paměti místo adres kreslíme šipky

Poznámka: reprezentace pole je zjednodušená, chybí ještě počet prvků.

Pozor: referenční proměnnou lze deklarovat i bez vytvoření pole

int [ ] b; V tom případě se zavede referenční proměnná, která má nedefinovanou hodnotu, jde-li o lokální proměnnou, nebo speciální hodnotu null, která neukazuje „nikam“, jde-li o statickou proměnnou.

Strana 5 (celkem 16)

Lze přiřadit jedné referenční proměnné pole jinou referenční proměnnou pole, ale tato pole musí být stejného typu Po přiřazení pak obě proměnné referencují totéž pole!

Příklad:

Poznámka: Přiřazení mezi dvěma poli není v Javě definováno, je řešeno prostřednictvím kopie pole (viz dále).

Nyní můžeme použít pole pro již dříve uvedený příklad na výpočet četnosti číslic.

int[] x = new int [3]; int[] y = x; y[1] = -6;

System.out.println(x[1]);

-6

Strana 6 (celkem 16)

Poznámka: příkaz for each – přístup postupně ke všem prvkům

public class ForEach { public static void main(String[] args) { int pole [] = {1,2,3,4,5}; int soucet = 0; for(int i :pole) { soucet += i; } System.out.println("soucet = " + soucet); } } soucet = 15

import java.util.*;

public class CetnostCislicPole {

static private Scanner sc = new Scanner(System.in);

public static void main(String[] args) {

int cetnost [] = new int[10]; String s = sc.nextLine(); int k=0; while(k<s.length()) { char znak = s.charAt(k++); if(znak >= '0' && znak <= '9'){ cetnost[(znak - (int)'0')]++; } }

for (int i=0; i<cetnost.length; i++) { System.out.println(i + ": " + cetnost[i]); } } }

110w2 t3383g476

0: 1 1: 2 2: 1 3: 3 4: 1 5: 0 6: 1 7: 1 8: 1 9: 0

public class ForEach { public static void main(String[] args) { int pole [] = {1,2,3,4,5}; int soucet = 0; for(int i :pole) { soucet += i; }

System.out.println("soucet = " + soucet); } }

soucet = 15

Strana 7 (celkem 16)

Pole - parametr či návratová hodnota

Reference pole může být parametrem metody

(metoda vypisPole()) či návratovou hodnotou (metoda nactiPole()) - viz následující příklad.

... pokračování na dalším slajdu

import java.util.*; public class PoleParametrANavrat {

static private Scanner sc = new Scanner(System.in);

static int [] nactiPole(int pocet, Scanner sc){ //zde int[] pole = new int [pocet]; for(int i=0; i<pole.length; i++){ System.out.print("Zadej a[" + i + "]: "); pole[i] = sc.nextInt(); } return pole; }

static int [] vynulujPole(int [] pole){ // zmena pole for(int i=0; i<pole.length; i++){ pole[i] = 0; } return pole; }

static void vypisPole(String s, int [] pole){ //zde for(int i=0; i<pole.length; i++){ System.out.println(s + "[" + i + "] = " + pole[i]); } }

Strana 8 (celkem 16)

Změna pole daného parametrem

V metodě vynulujPole() jsme nevytvořili nové pole, ale vynulovali pole dané parametrem.

Proč to funguje? Protože metoda vynulujPole() dostala referenci na stejné pole, na které ukazuje proměnná a.

Kopie polí

- použitím cyklu - metodou třídy System

arraycopy(zdroj, odZdroj, kopie, odKopie, length);

public static void main(String[] args) { System.out.print("Zadej pocet prvku: "); int pocetPrvku = sc.nextInt(); int a [] = new int [pocetPrvku]; a = nactiPole(pocetPrvku, sc); vypisPole("a" + a); System.out.println(Arrays.toString(a)); vynulujPole(a); vypisPole("a" + a); System.out.println(Arrays.toString(a)); } } // vypis pole a najednou //System.out.println(Arrays.toString(a));

Zadej pocet prvku: 3

Zadej a[0]: 1

Zadej a[1]: 2

Zadej a[2]: 3

a[0] = 1

a[1] = 2

a[2] = 3

[1, 2, 3]

a[0] = 0

a[1] = 0

a[2] = 0

[0, 0, 0]

Strana 9 (celkem 16)

Příklad: různé způsoby kopie pole

- pole prvni je prekopirováno do pole druhe

- do pole treti od indexu 0 jsou nakopírovány 2

prvky pole prvni od indexu 2

import java.util.*;

public class KopiePoli{ public static void main(String [] args){

int[] prvni = {2, 3, 1, 5, 10}; int[] druhe = new int[prvni.length]; int[] treti = new int[3]; System.out.println("prvni:" + Arrays.toString(prvni)); System.out.println("druhe:" + Arrays.toString(druhe));

System.out.println("Kopirovani"); for (int i = 0; i < prvni.length; i++){ druhe[i] = prvni[i]; } System.arraycopy(prvni, 2, treti, 0, 2); System.out.println("prvni:" + Arrays.toString(prvni)); System.out.println("druhe:" + Arrays.toString(druhe)); System.out.println("treti:" + Arrays.toString(treti)); } } prvni:[2, 3, 1, 5, 10]

druhe:[0, 0, 0, 0, 0] Kopirovani prvni:[2, 3, 1, 5, 10] druhe:[2, 3, 1, 5, 10] treti:[1, 5, 0]

Strana 10 (celkem 16)

Pole reprezentující množinu

- pole typu boolean, je-li prvek součástí množiny, má hodnotu true, není-li součástí má hodnotu false

Úloha: vypsat všechna prvočísla menší nebo rovna zadanému max 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...

Pro reprezentaci množiny čísel použijeme pole prvků typu boolean

– prvek mnozina[x] bude udávat, zda číslo x v množině je (true) nebo není (false)

Algoritmus:

Vytvoříme množinu obsahující přirozená čísla od čísla 2 do max.

Z množiny vypustíme všechny násobky čísla 2.

Najdeme nejbližší číslo k tomu, jehož násobky jsme v předchozím kroku vypustili, a vypustíme všechny násobky tohoto čísla.

Opakujeme předchozí krok tak dlouho, dokud číslo, jehož násobky jsme vypustili, není větší

než max .

Čísla, která v množině zůstanou, jsou hledaná prvočísla.

Strana 11 (celkem 16)

public class Sito {

static final int MAX = 17; static boolean [] vytvorMnozinu (int max){ boolean [] mnozina = new boolean [max+1]; for(int i=0; i< mnozina.length; i++){ mnozina[i] = true; } return mnozina; } static void sito (boolean [] mnozina){ int max = (int) Math.sqrt(mnozina.length); for(int i=2; i<=max; i++){ if(mnozina[i] == false){ continue; } for(int j=2*i; j<mnozina.length; j += i){ mnozina[j] = false; } } } static void vypisPrvocisla (boolean [] mnozina){ for(int i=2; i<mnozina.length; i++){ if(mnozina[i]){ System.out.print(i + ", "); } } System.out.println(); }

Strana 12 (celkem 16)

Vícerozměrná pole, matice

- přístup prostřednictvím více indexů - práce jako s jednorozměrnými poli (prvky jsou

opět pole – pole s nestejnou délkou řádek) - deklarace stejná, pouze více rozměrů ([])

Obdélníková matice o m řádcích a n sloupcích

int m = 3; int n = 4;

int [][] matice = new int [m][n];

Inicializace matice

int [][] matice = {{1,0,0},{0,1,0},{0,0,1}};

Rozměry matice

matice.length = počet řádků matice[0].length = počet sloupců

public static void main(String [] args){ boolean [] prvocisla = vytvorMnozinu(MAX); sito(prvocisla); vypisPrvocisla(prvocisla); }

2, 3, 5, 7, 11, 13, 17,

Strana 13 (celkem 16)

Příklad: součin matic

242322312321221121

141312311321121111

34333231

24232221

14131211

232221

131211

cccbababa

cccbababa

bbbb

bbbb

bbbb

aaa

aaa

import java.util.*;

public class SoucinMatic {

static private Scanner sc = new Scanner(System.in);

/* static int c[][] = new int [3][4]; static int a[][] = {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}}; static int b[][] = {{1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}}; */

Strana 14 (celkem 16)

static int [][] nactiMatici(Scanner sc, int radky, int sloupce){ int [][] matice = new int[radky][sloupce]; for (int i = 0; i < matice.length; i++){ for (int j = 0; j < matice[i].length; j++) { matice[i][j] = sc.nextInt(); } } return matice; }

static void vypisMatici(int [][] matice){ for (int i = 0; i < matice.length; i++){ for (int j = 0; j < matice[i].length; j++) { System.out.print(matice[i][j] + " "); } System.out.println(); } }

static int [][] vynasobMatice(int[][] a, int [][] b){ int [][] c = new int[a.length][b[0].length]; for (int i = 0; i < a.length; i++) { for (int j = 0; j < b[i].length; j++) { int s=0; for (int k = 0; k < a[i].length ; k++){ s += a[i][k] * b[k][j]; } c[i][j] = s; } } return c; }

Strana 15 (celkem 16)

public static void main(String[] args) { int m = sc.nextInt(); int n = sc.nextInt(); int p = sc.nextInt(); int [][] a = new int [m][n]; int [][] b = new int [n][p]; int [][] c = new int [m][p]; a = nactiMatici(sc, m,n); b = nactiMatici(sc, n,p); c = vynasobMatice(a, b); vypisMatici(a); vypisMatici(b); vypisMatici(c); } }

2 3 4 1 1 1 // A 1 1 1 1 1 1 1 // B 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 // C 3 3 3 3

Strana 16 (celkem 16)

Problém Proveďte jednoduchou analýzu zadaného textu. První

řádek vstupu obsahuje kladné celé číslo n (1 ≤ n ≤ 1000).

Toto číslo představuje počet následujících řádek vstupu.

Dalších n řádek buď nebude obsahovat žádný znak nebo

bude obsahovat jeden či více znaků (přípustné jsou

i mezery). Tyto řádky tvoří text, který má být analyzován.

Můžete předpokládat, že písmena se v textu jsou pouze

z anglické abecedy.

Každý řádek výstupu bude obsahovat jedno velké

písmeno, následované mezerou a kladným celým číslem,

které vyjadřuje počet, kolikrát se toto písmeno objevilo

v textu. Velká a malá písmena jsou považována za totožná.

Kromě písmen nebudou vyhodnocovány žádné jiné znaky.

Písmena musí být na výstupu seřazena sestupně podle

jejich četnosti výskytu, tzn. nejfrekventovanější písmeno

bude na prvním řádku a poslední řádek bude obsahovat

nejméně frekventované písmeno. Pokud bude existovat

více písmen se stejnou frekvencí výskytu, pak budou

řazena vzestupně podle abecedy. Pokud se písmeno v textu

nevyskytlo, nesmí se objevit ani na výstupu.

Problém je možno automaticky validovat na:

http://uva.onlinejudge.org/

Co je nutno udělat? - registrace, pokud již zaregistrováni nejste - přečíst zadání (10008 What is Cryptanalysis) - napsat zdrojový kód - odevzdat zdrojový kód - pozor třída i soubor je

nutno pojmenovat Main! - kontrola validace , obdržíte i validační e-mail