Računalništvo 1 (PRA)

Tabele in zanka `for`

Tabele

Kot smo že omenili, so tabele posebna vrsta tipov. Vsaka tabela ima velikost v njej pa je spravljenih toliko vrednosti, kot je njena velikost. Na primer, če je x tabela celih števil in je njena velikost

x.length ==
      10

, so vrednosti, ki so shranjene v tabeli x

x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9]

Tabelo deklariramo tako, da napišemo oglate oklepaje za tip. Na primer:

int[] x;
double[] y;

Prva vrstica pomeni "naj bo x tabela celih števil", druga vrstica pa "naj bo y tabela realnih števil". S tema dvema ukazoma še nismo naredili tabel, ampak smo samo povedali, da sta x in y tabeli. Novo tabelo pa naredimo z ukazom new:

x = new int[200];
y = new double[10];

Prva vrstica pomeni "naj bo x nova tabela 200 celih števil". Podobno druga vrstica pomeni "naj bo y nova tabela 10 realnih števil." Java je pri tem samodejno nastavila vseh dvesto vrednosti za x na 0 in vseh deset vrednosti za y na 0.0.

Seveda pa nam ni treba pisati najprej int x[]; in nato še x = new int[200];, ampak to lahko opravimo v eni vrstici:

int[] x = new int[200];

To pomeni "naj bo x tabela celih števil, in sicer naj bo enaka novi tabeli 200 celih števil (ki jih Java nastavi na 0)."

Včasih poznamo elemente tabele, ko pišemo program (bolj pogosto pa jih izračuna program sam, ali pa jih preberemo s standardnega vhoda ali z datoteke). V tem primeru lahko vrednosti v tabeli naštejemo v zavitih oklepajih, takole:

int[] dolgiMeseci = { 1, 3, 5, 7, 8, 10, 12 };

Tabela dolgiMeseci ima 7 elementov in sicer zaporedna števila mesecev, ki imajo 31 dni.

Če želimo peti element tabele dolgiMeseci to zapišemo z dolgiMeseci[5]. Elementi v tabelah se štejejo od ničtega dalje, zato je dolgiMeseci[5] == 10. Zapomnimo si:

Tabela elementov tipa t ima tip t[].
Novo tabelo tipa t[] velikost n naredimo z ukazom new t[n].
V tabeli x je k-ti element x[k]. Pri tem se k imenuje indeks.
Elementi v tabeli se začenjo šteti z indeksom 0.
Velikost tabele x je x.length.
Zadnji element tabele x je x[x.length - 1].

Oglejmo si, kako tabele uporabimo v programu. Napišimo program, ki prebere s standardnega vhoda pet nizov in jih izpiše v obratnem vrstnem redu.

Obratno.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21	import java.io.*; public class Obratno { public static void main(String[] args) throws IOException { final int N = 5; BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in)); String[] a = new String[N]; int k = 0; while (k < N) { System.out.print(k + ". stevilo: "); a[k] = vhod.readLine(); k = k + 1; } int j = N - 1; while (j >= 0) { System.out.println(a[j]); j = j - 1; } } }

Obratno.java

import java.io.*;

public class Obratno {
    public static void main(String[] args) throws IOException {
	final int N = 5;
	BufferedReader vhod =
	    new BufferedReader(new InputStreamReader(System.in));
	String[] a = new String[N];
	int k = 0;
	while (k < N) {
	    System.out.print(k + ". stevilo: ");
	    a[k] = vhod.readLine();
	    k = k + 1;
	}
	int j = N - 1;
	while (j >= 0) {
	    System.out.println(a[j]);
	    j = j - 1;
	}
    }
}

> javac Obratno.java
> java Obratno
0. stevilo: 12
1. stevilo: 8
2. stevilo: 292
3. stevilo: 1
4. stevilo: 123833
123833
1
292
8
12

V 8. vrstici naredimo novo tabelo a celih števil z N elementi, pri čemer je konstanta N enaka 5. Mimogrede, definirali smo konstanto

N
      = 5

in jo uporabili, namesto da bi povsod kar napisali 5. Zakaj? Zato, ker je tako napisan program lažje spremeniti. Če si premislimo, in želimo prebrati 7 števil namesto 5, preprosto spremenimo vrednost konstante N na enem mestu. Če pa bi povsod pisali 5, bi morali ob vsaki spremembi pregledati ves program in ugotoviti, kje so potrebni popravki. Seveda bi lahko namesto N povsod uporabili a.length.

V 17. vrstici nastavimo vrednost k-tega elementa tabele a na celo število, ki ga preberemo s standardnega vhoda. Pri tem je 17. vrstica del zanke while, ki šteje od 0 do N-1.

V 25. vrstici pa izpišemo vrednost j-tega elementa tabele. Pri tem je 25. vrstica del zanke while, ki šteje od N-1 do 0.

Naloga 1

Dana je tabela celih števil int[] a. Napiši program Najmanjsi, ki v spremenljivko int m shrani najmanjši element tabele int[] a.

Namig

public class Najmanjsi {
  public static void main(String[] args) {
    int a[] = {12, 4, 5, 10, 2, 8, 105};
    int m = (ustrezna zacetna vrednost);
    for (int i = 1; i < a.length; i = i + 1) {
      (tu nekaj naredimo)
    }
    System.out.println("Najmanjsi element je " + m);
  }
}

[rešitev]

Naloga 2

Dana je tabela celih števil int[] a. Napiši program IndeksNajmanjsega, ki v spremenljivko

int
	  k

shrani indeks najmanjšega elementa tabele int[] a.

Namig

public class IndeksNajmanjsega {
  public static void main(String[] args) {
    int a[] = {12, 4, 5, 10, 2, 8, 105};
    int k = (ustrezna zacetna vrednost);
    for (int i = 1; i < a.length; i = i + 1) {
      (tu nekaj naredimo)
    }
    System.out.println("Najmanjsi element je " + k + "-tem mestu.");
  }
}

[rešitev]

Tabela argumentov iz ukazne vrstice

Verjetno ste se že spraševali, kaj pomeni tisti

String[]
	args

, ki ga vedno napišemo pri definiciji metode main.

Ko poženemo program v Javi z ukazne vrstice, lahko podamo tako imenovane argumente. Na primer, ko napišemo ukaz

> java NekiProgram foo bla 12 tralala

se bo pognal program NekiProgram, ki smo mu podali argumente "foo", "bla", "12" in "tralala". Java argumente z ukazne vrstice spravi v tabelo String[] args, ki jo nato lahko uporabimo v metodi main.

Napišimo program, ki izpiše vse argumente iz ukazne vrstice:

Argumenti.java
1 2 3 4 5 6 7	public class Argumenti { public static void main(String[] args) { for (int i = 0; i < args.length; i = i + 1) { System.out.println("Argument " + i + ": " + args[i]); } } }

> java Argumenti foo bar 123 tralala
Argument 0: foo
Argument 1: bar
Argument 2: 123
Argument 3: tralala

Argumenti so vedno nizi znakov, tudi če natipkamo 123.

Naloga 3

Napiši program Sestej, ki z ukazne vrstice sprejme dva celoštevilska argumenta in izpiše na zaslon njuno vsoto. Primer uporabe:

> java Sestej 11 150
161
> java Sestej 23 -6
17

Namig

Argumenta sta args[0] in args[1], vendar sta tipa String in ju je treba najprej pretvoriti v celi števili. Kako se pretvori String v int?

[rešitev]

Mimogrede omenimo, da se tabela argumentov ponavadi imenuje args, vendar pa to ni nujno. Lahko jo poimenujemo poljubno.

Zanka `for`

Na tem mestu velja omeniti novo vrsto zanke, zanko for, ker se pogosto uporablja v zvezi s tabelami. Pri uporabi tabel namreč pogosto naletimo na zanke, pri katerih z neko spremenljivko, denimo i, štejemo od spodnje meje, denimo 0, do zgornje meje, denimo N-1. Z zanko while to že znamo narediti:

int i = 0;
while (i < N) {
   (tu nekaj naredimo)
   i = i + 1;
}

To isto lahko napišemo z zanko for takole:

1
2
3

for (int i = 0; i < N; i = i + 1) {
   (tu nekaj naredimo)
}

Ideja je v tem, da je zanka for (v nekaterih primerih) bolj čitljiva kot pa zanka while, saj so vsi ukazi v zvezi s števcem i zbrani na enem mestu na začetku zanke. Splošna oblika zanke for je:

for (A; p; B) {
  C;
}

To preberemo takole: "Izvedi ukaz A. Dokler je pogoj p enak true ponavljaj: izvedi C in nato še B". Shematični prikažemo zanko for takole: Zanka for

Pozor! Čeprav je v zanki for ukaz B napisan pred ukazom C, se najprej izvede C in šele nato B! To začetnike pogosto moti, zato bodite posebej pozorni, kako uporabljate zanke for. Ukaz B se v praksi uporablja večinoma za to, da se poveča števec, s katerim štejemo ponovitve zanke.

Naloga 4

V programu Obratno.java nadomesti zanke while z zankami for.

Namig

Prvo zanko predelamo takole:

for (int k = 0; k < N; k = k + 1) {
  System.out.print(k + ". stevilo: ");

  a[k] = Integer.parseInt(vhod.readLine());
}

[rešitev]

Naloga 5

Napiši program Crke.java, ki izpiše tole:

> java Crke
ABCDEFG
BCDEFGA
CDEFGAB
DEFGABC
EFGABCD
FGABCDE
GABCDEF

Navodilo: uporabi zanke for in tabelo nizov

{
	  "A", "B", "C", "D", "E", "F", "G"}

. Program napiši tako, da ga je treba čim manj popravljati, če želimo spremeniti, dodati ali odstraniti kako črko.

Namig

V pomoč naj ti bo tale nedokončan program:

public class Crke {
  public static void main(String[] args) {
    String[] crke = { "A", "B", "C", "D", "E", "F", "G" };

    for (int i = 0; i < crke.length; i = i + 1) {
      // izpisi crke od i-te do zadnje

      // izpisi crke od nicte do (i-1)-te

      System.out.println();
    }
  }
}

[rešitev]

Naloga 6

Napiši program Prva.java, ki izmed podanih besed (v ukazni vrstici) izbere tisto, ki je prva po abecedi.

> java Prva marko skace marko skace po zeleni trati
marko
> java Prva naj ostanem ali grem
ali

Nasvet: dva niza znakov primerjamo po abecedi z metodama compareTo in compareToIgnoreCase. Sam izberi metodo, ki je bolj primerna.

Namig

Uporabimo spremenljivko String prva (sam ugotovi, kakšna naj bo njena začetna vrednost). Nato za vsak argument args[i] preveri, ali je po abecedi pred trenutno vrednostjo spremenljivke prva in če je, nastavi prva na args[i]. Na koncu izpiši prva.

[rešitev]

Napišimo program, ki računa Pascalov trikotnik:

          1
        1   1
      1   2   1
    1   3   3   1
  1   4   6   4   1
1   5  10  10   5   1

Na robovih so enice. Vsako število, ki ni na robu, pa je vsota dveh števil nad njim. Za programiranje je nekoliko lažje, če trikotnik narišemo takole:

1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1

Najprej moramo ugotoviti, kako se iz trenutne vrstice števil, na primer

1   4   6   4   1

izračuna naslednja. Če si mislimo, da je trenutna vrstica tabela p, potem izračunamo novo vrstico v tabelo n po predpisu:

Velikost nove vrstice je za eno večja od trenutne vrstice.
Ničti in zadnji element tabele n nastavimo na 1.
Za i med 1 in n.length - 1, je n[i] = p[i - 1] + p[i].

To prevedemo v Javo:

int[] n = int[p.length + 1];

n[0] = 1;

for (int i = 1; i < n.length - 1; i = i + 1) {
  n[i] = p[i-1] + p[i];
}

n[n.length - 1] = 1;

To je seveda samo delček programa, ki ga pišemo. Struktura celotnega programa je taka:

Na začetku je int[] p = { 1 };
Ponavljaj:
- izpiši tabelo p na zaslon
- izračunaj n iz p
- nastavi p na n

Koliko časa pa naj ponavljamo ta postopek? Na primer

N =
      10

krat. Ko zložimo skupaj vse dele, dobimo program Pascal.java:

Pascal.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22	public class Pascal { public static void main(String[] args) { final int N = 10; int[] p = { 1 }; for (int j = 0; j < N; j = j + 1) { // izpisemo p for (int k = 0; k < p.length; k = k + 1) { System.out.print(p[k] + " "); } System.out.println(); // izracunamo novo vrstico int[] n = new int[p.length + 1]; n[0] = 1; for (int i = 1; i < n.length - 1; i = i + 1) { n[i] = p[i-1] + p[i]; } n[n.length - 1] = 1; // nastavimo p na novo vrstico p = n; } } }

Pascal.java

public class Pascal {
    public static void main(String[] args) {
	final int N = 10;
	int[] p = { 1 };
	for (int j = 0; j < N; j = j + 1) {
	    // izpisemo p
	    for (int k = 0; k < p.length; k = k + 1) {
		System.out.print(p[k] + " ");
	    }
	    System.out.println();
	    // izracunamo novo vrstico
	    int[] n = new int[p.length + 1];
	    n[0] = 1;
	    for (int i = 1; i < n.length - 1; i = i + 1) {
		n[i] = p[i-1] + p[i];
	    }
	    n[n.length - 1] = 1;
	    // nastavimo p na novo vrstico
	    p = n;
	}
    }
}

> javac Pascal.java
> java Pascal
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1

Naloga 7

Spremeni program Pascal.java tako, da bo iz ukazne vrstice vzel arugment, ki pove, koliko vrstic naj se izpiše. Se pravi, namesto, da bi bil N konstanta nastavljena na 10, naj bo spremenljivka, katere vrednost je ničti argument iz komandne vrstice.

Namig

int N = Integer.parseInt(args[0]);

[rešitev]

Dvojne tabele

Dvojna tabela je tabela tabel, na primer

int[][] a = { {1, 2}, {3, 4, 5}, {6, 7, 8, 9} };

je tabela tabel celih števil. Dolžina tabele a je 3. Elementi tabele a so:

a[0] == {1, 2}
a[1] == {3, 4, 5}
a[2] == {6, 7, 8, 9}

Vidimo torej, da je a[0] tabela velikosti 2, a[1] je tabela velikosti 3 in a[2] je tabela velikosti 4. Če želimo ničti element tabele a[2], ga dobimo tako, da napišemo a[2][0]. Vrednost a[2][0] je 6. Velikost dvojne tabele int[][] a je a.length in nam pove, koliko tabel vsebuje tabela a. Dolžine posameznih tabel so a[0].length, a[1].length, ..., a[a.length-1].length.

Novo dvojno tabelo celih števil int[][] x velikosti n naredimo z ukazom

int[][] x = new int[n][];

Seveda moramo potem še narediti tabele x[0], ..., x[n-1] s primernimi ukazi

x[i] = new
      int[...];

Na primer, da želimo narediti tabelo tabel int[][] a, ki vsebuje 100 tabel, pri čemer ima i-ta tabela velikost 2 * i + 1. To naredimo z naslednjimi ukazi:

int[]][] a = new int[100][];
for (int i = 0; i < 100; i = i + 1) {
  a[i] = new int[2 * i + 1];
}

S tem smo naredili dvojno tabelo a, ki ima naslednje elemente:

a[0][0]
a[1][0], a[1][1], a[1][2]
a[2][0], a[2][1], a[2][2], a[2][3], a[2][4]
a[3][0], a[3][1], a[3][2], a[3][3], a[3][4], a[3][5], a[3][6]
...
a[99][0], a[99][1], ..., a[99][199], a[99][200]

Dvojna tabela je tabela tabel.
Novo dvojno tabelo t[][] x velikost n naredimo z ukazom x = new t[n][];. Posamezne tabele x[0], ..., x[n-1] naredimo z ukazom x[i] = new t[...];.
x[n] pomeni "n-ta tabela v tabeli tabel x."
x[n][m] pomeni "m-ti element tabele x[n]."
x.length je število tabel, ki so v tabeli x.
x[n].length je dolžina tabele x[n].

1 2
3 4 5
6 7 8 9

Namig

Program sestoji iz dveh vgnezdenih zank for. Prva zanka šteje po tabeli a s števcem i, notranja zanka pa šteje s števcem j po tabeli a[i].

[rešitev]

Naloga 10

Napiši program Pascal3.java, ki z ukazne vrstice sprejme pozitivno celo število n in naredi dvojno tabelo pascal, ki ima n vrstic, pri čemer je k-ta vrstica enaka k-ti vrstici Pascalovega trikotnika. Program naj tudi izpiše vsebino tabele pascal na zaslon.

Na primer, če poženemo program z ukazom

java Pascal3
	    5

, program izračuna dvojno tabelo pascal z elementi

pascal[0] = { 1 }
pascal[1] = { 1, 1 }
pascal[2] = { 1, 2, 1 }
pascal[3] = { 1, 3, 3, 1 }
pascal[4] = { 1, 4, 6, 4, 1 }

in izpiše na zaslon

> java Pascal3 4
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Namig

Uporabi kodo iz programov Pascal2.java in IzpisiTabelo.java.

[rešitev]

Matrike

Dvojni tabeli a, v kateri so vse tabele a[0], ..., a[a.length-1] enako velike, pravimo matrika.

Matrika je dvojna tabela, v kateri imajo vse enojne podtabele enako velikost.
Število vrstic v matriki a je a.length.
Število stolpcev v matriki a je a[0].length.
Matriko z n vrsticami in m stolpci, ki vsebuje elemente tipa t, naredimo z ukazom new t[n][m].

Napišimo program, ki sešteje matriki

 1  2  3  4  5
-1  0  0  2  7
 3  4  1  6  8
 1  6  6  1  0
 3  1  2  4  2

 1  1  0  0  0
 1  1  1  0  0
 0  1  1  1  0
 0  0  1  1  1
 0  0  0  1  1

Program naredi novo matriko c in nato v dvojni zanki for napolni njene elemente z ustreznimi vrednostmi:

Vsota.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39	public class Vsota { public static void main(String[] args) { int[][] a = { { 1, 2, 3, 4, 5}, {-1, 0, 0, 2, 7}, { 3, 4, 1, 6, 8}, { 1, 6, 6, 1, 0}, { 3, 1, 2, 4, 2} }; int[][] b = { { 1, 1, 0, 0, 0}, { 1, 1, 1, 0, 0}, { 0, 1, 1, 1, 0}, { 0, 0, 1, 1, 1}, { 0, 0, 0, 1, 1} }; int n = a.length; // Stevilo vrstic int m = a[0].length; // Stevilo stolpcev int[][] c = new int[n][m]; // c = a + b // sestejemo a in b v c for (int i = 0; i < n; i = i + 1) { for (int j = 0; j < m; j = j + 1) { c[i][j] = a[i][j] + b[i][j]; } } // izpisemo matriko c for (int i = 0; i < c.length; i = i + 1) { for (int j = 0; j < c[i].length; j = j + 1) { System.out.print(c[i][j] + " "); } System.out.println(); } } }

Vsota.java

public class Vsota {
    public static void main(String[] args) {
	int[][] a = {
	    { 1,  2,  3,  4,  5}, 
	    {-1,  0,  0,  2,  7},
	    { 3,  4,  1,  6,  8},
	    { 1,  6,  6,  1,  0},
	    { 3,  1,  2,  4,  2}
	};

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

	int n = a.length;    // Stevilo vrstic
	int m = a[0].length; // Stevilo stolpcev

	int[][] c = new int[n][m]; // c = a + b

	// sestejemo a in b v c
	for (int i = 0; i < n; i = i + 1) {
	    for (int j = 0; j < m; j = j + 1) {
		c[i][j] = a[i][j] + b[i][j];
	    }
	}

	// izpisemo matriko c
	for (int i = 0; i < c.length; i = i + 1) {
	    for (int j = 0; j < c[i].length; j = j + 1) {
		System.out.print(c[i][j] + " ");
	    }
	    System.out.println();
	}
    }
}

Naloga 11

Napiši program, ki izračuna produkt matrike

 1  2  3  4  5
-1  0  0  2  7
 3  4  1  6  8
 1  6  6  1  0
 3  1  2  4  2

in matrike

 1  1  0  0  0
 1  1  1  0  0
 0  1  1  1  0
 0  0  1  1  1
 0  0  0  1  1

Prvo matriko bi v Javo prepisali takole:

int[][] a =
  {
    { 1,  2,  3,  4,  5}, 
    {-1,  0,  0,  2,  7},
    { 3,  4,  1,  6,  8},
    { 1,  6,  6,  1,  0},
    { 3,  1,  2,  4,  2}
  };

Zapis a[i][j] pomeni "vrstica i, stolpec j", pri čemer se vrstice in stolpci štejejo od nič dalje. Tako je na primer a[2][4] == 8. Novo matriko z n vrsticami in m stolpci naredimo z ukazom

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

Namig

Če je c produkt matrik a in b, tedaj velja

c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + ... + a[i][n] * b[n][j]

pri čemer je n število stolpcev matrike a in mora biti enako številu vrstic matrike b.

[rešitev]

> java PrvaBeseda banana ananas pomaranca jabolko
ananas

Tabele in zanka for

Tabele

Tabela argumentov iz ukazne vrstice

Zanka for

Namig

Namig

Dvojne tabele

Matrike

Naloge za predavanja in vaje

Tabele in zanka `for`

Zanka `for`