INF1000 - H?st 2008
Du er her: UiO > 澳门葡京手机版app下载 > Emner > Matematikk og naturvitenskap > Informatikk > INF1000 > h08 > ukeoppgaver >

L?sningsforslag ukeoppg. 8:  13. - 16. okt (INF1000 - H?st 2008)

HashMap (kap. 9.1 - 9.11), oppramstyper (kap. 8.16), innstikksortering (kap. 5.6), og litt om javadoc.
NB! Disse er bare forslag til l?sninger, dine svar kan v?re like gode eller bedre selv om de ser annerledes ut.
Du f?r sannsynligvis mer utbytte av l?sningsforslagene etter at du har fors?kt ? l?se oppgaven selv.  Du kan ogs? finne l?sning p? noen av oppgavene fra l?reboka i bokens hjemmeside: www.universitetsforlaget.no/java.

M?l
Forst? forskjellene mellom arrayer og HashMap; og f? litt ?velse i bruk av enum, innstikksortering, og javadoc-kommentarer.

Oppgaver til teoritimen

  1. HashMap: Hva skrives ut?  (Se oversikten p? side 188 i l?reboka) 
    import java.util.*;
class Personer {
    public static void main(String[] args) {
	HashMap <String, Person> register = new HashMap <String, Person> ();

	Person p1 = new Person("Ida", 19);
	Person p2 = new Person("Lars", 21);

	register.put(p1.navn, p1);
	register.put(p2.navn, p2);

// a)
	Person p = register.get("Ida");
	System.out.println(p.navn + p.alder);

// b)
	for (String s : register.keySet()) {
	    System.out.println(s);
	}
// c)
	p1.alder = 24;
	for (Person p3 : register.values()) {
	    System.out.println(p3.navn + ":" + p3.alder);
	}
// d)
	if (register.containsValue(p2) && ! register.containsKey("Elin")) {
	    System.out.println(true);
	}
// e)
	register.remove("Lars");
	System.out.println(register.size() + " - " + register.isEmpty());
// f)
	System.out.println(register.remove("Ida") == null);
	System.out.println(register.remove("Ida") == null);
    }
}

class Person {
    String navn;
    int alder;

    Person(String navn, int alder) {
	this.navn = navn;
	this.alder = alder;
    }
}

    a)  Ida19
b)  Lars
    Ida
c)  Lars:21
    Ida:24
d)  true
e)  1 - false
f)  false
    true


  2. Bank.java: Array vs. HashMap
    (a) F?lgende program viser et enkelt banksystem med en array kontoer[], og metoder for ? finne en konto vha. navn til eieren og vha. kontonummer.  Skriv om programmet slik at det bruker en HashMap i stedet for arrayen kontoer[].  I f?rste omgang lager vi én HashMap, med personnavn som n?kkel og et Konto-objekt som verdi, deklarert slik:
      HashMap <String, Konto> kontoFraNavn = new HashMap <String, Konto>();
    Hvilke fordeler og ulemper f?r vi av ? bruke HashMap her?  Hva kan variabelen antKontoer erstattes med i programmet?  (Anta forel?pig at personnavnene er unike og at hver person bare kan ha én konto i banken.) 
    class Konto {
    int nr; // kontonummer
    String navn; // eier
    int saldo;

    Konto(int nr, String navn, int saldo) {
	this.nr = nr;
	this.navn = navn;
	this.saldo = saldo;
    }

    void settInn(int innskudd) {
	saldo = saldo + innskudd;
    }
}

class Bank {
    Konto[] kontoer = new Konto[1000];
    int antKontoer = 0;

    public static void main(String[] args) {
	Bank b = new Bank();
    }

    Bank() {
        ?pneNyttKonto(530010, "Nils", 4000);
        ?pneNyttKonto(720020, "Elin", 8000);
        ?pneNyttKonto(910030, "Tina", 9000);

        Konto k = finnKontoFraNavn("Elin");
        System.out.println("Elins kontonr: " + k.nr + ", saldo: " + k.saldo);

	k = finnKontoFraNr(530010);
	System.out.println("Kontonr. " + k.nr + " tilh?rer " + k.navn);
    }

    void ?pneNyttKonto(int nr, String navn, int saldo) {
	Konto k = new Konto(nr, navn, saldo);
	kontoer[antKontoer] = k;
	antKontoer++;
    }

    Konto finnKontoFraNavn(String navn) {
	for (int i = 0; i < antKontoer; i++) {
	    if (kontoer[i].navn.equals(navn)) {
		return kontoer[i];
	    }
	}
	return null;
    }

    Konto finnKontoFraNr(int kontonr) {
	for (int i = 0; i < antKontoer; i++) {
	    if (kontoer[i].nr == kontonr) {
		return kontoer[i];
	    }
	}
	return null;
    }
}

KJ?REEKSEMPEL:
Elins kontonr: 720020, saldo: 8000
Kontonr. 530010 tilh?rer Nils

    import java.util.*;

class Konto {
    int nr; // kontonummer
    String navn; // eier
    int saldo;

    Konto(int nr, String navn, int saldo) {
	this.nr = nr;
	this.navn = navn;
	this.saldo = saldo;
    }

    void settInn(int innskudd) {
	saldo = saldo + innskudd;
    }
}

class Bank2 {
    HashMap <String, Konto> kontoFraNavn = new HashMap <String, Konto>();
    HashMap <String, Konto> kontoer = new HashMap <String, Konto>();

    public static void main(String[] args) {
	Bank2 b = new Bank2();
    }

    Bank2() {
        ?pneNyttKonto(530010, "Nils", 4000);
        ?pneNyttKonto(720020, "Elin", 8000);
        ?pneNyttKonto(910030, "Tina", 9000);

        Konto k = finnKontoFraNavn("Elin");
        System.out.println("Elins kontonr: " + k.nr + ", saldo: " + k.saldo);

	k = finnKontoFraNr(530010);
	System.out.println("Kontonr. " + k.nr + " tilh?rer " + k.navn);

        System.out.println("Antall kontoer: " + kontoer.size());
	avsluttKonto(k);
	System.out.println("Fins kontoen n??: " + kontoer.containsValue(k));
        System.out.println("Antall kontoer n?: " + kontoer.size());
    }

    void ?pneNyttKonto(int nr, String navn, int saldo) {
	Konto k = new Konto(nr, navn, saldo);
	kontoFraNavn.put(navn, k);
	kontoer.put("" + nr, k);
    }

    Konto finnKontoFraNavn(String navn) {
	return kontoFraNavn.get(navn);
    }

    Konto finnKontoFraNr(int kontonr) {
	return kontoer.get("" + kontonr);
    }

    void avsluttKonto(Konto k) {
	kontoFraNavn.remove("" + k.nr);
	kontoer.remove("" + k.nr);
    }
}

KJ?REEKSEMPEL:
Elins kontonr: 720020, saldo: 8000
Kontonr. 530010 tilh?rer Nils
Antall kontoer: 3
Fins kontoen n??: false
Antall kontoer n?: 2

    (b) Lag en HashMap til, kalt kontoer, hvor du bruker som n?kkel kontonummeret konvertert til String, og fortsatt Konto-objektene som verdi.  Vis at metoden finnKontoFraNr() blir enklere n?.  Videre tenk deg at vi skal ha en metode for ? fjerne en konto.  F?lgende kode viser hvordan det kan gj?res med arrayer.  Hvor mange programsetninger trengs det n?r vi bruker én HashMap i stedet?  Og med to? 
        void avsluttKonto(Konto k) {
	// Fjerner en konto ved ? finne indeksen til kontoen i arrayen
	// kontoer[] og flytte alle kontoene med h?yere indeks en plass ned.
	boolean funnet = false;
	for (int i = 0; i < antKontoer && !funnet; i++) {
	    if (kontoer[i] == k) {
		funnet = true;
		for (int j = i; j < antKontoer - 1; j++) {
		    kontoer[j] = kontoer[j + 1];
		}
		antKontoer--;
	    }
	}
    }
    (L?sningsforslaget st?r i del (a) over)

    (c) Disse oppgavene har begrensningen at personnavnene m? v?re unike og at hver person bare kan ha én konto i banken.  Hvordan ville man unng?tt disse begrensninger i et mer avansert system?  Hvilke fordeler og ulemper ser du av ? bruke HashMap-er i Oblig 3? (foresl? mulige n?kkel/verdi-kombinasjoner).
    Hint: Se avsnitt 9.11 p? side 189 i l?reboka for forskjellene mellom arrayer og HashMap-er.
    I store systemer passer det bedre ? ha personnummer som n?kkel eller noe annet som er unikt for hver verdi, i stedet for navn alene.  Verdi kan v?re et Person-objekt, som i sin tur kan ha en objektvariabel av type HashMap som refererer til alle kontoene for personen.  Hvis programmet trenger ? finne personer ut fra navn s? kan man likevel bruke navn som n?kkel i en tilleggs-HashMap, som f.eks. kan ha som verdi en HashMap over personene med det navnet.

    Arrayer passer best ? bruke n?r maks. antall elementer er kjent p? forh?nd, n?r vi trenger en gitt rekkef?lge p? dataene, og n?r indeksene er numeriske (eller char).  HashMap er bedre n?r maks. antall elementer er ukjent, eller man trenger ? sl? opp i dataene vha. "indekser" som er noe annet enn tall (f.eks. tekster), og n?r rekkef?lgen p? dataene ikke er avgj?rende.  Med HashMap m? dataene v?re objekter (pekere), ikke primitive typer, men det finnes objekt-typer for alle de primitive: Integer, Double, Character, Boolean.

    I Oblig 3 er det mest naturlig ? bruke arrayer, men man kan ogs? bruke HashMap: da kan f.eks. hele hybelnavnet v?re n?kkel.  Man trenger likevel lett tilgang til etasje- og rom-nr. s? disse kan evt. legges til som objektvariabler i Hybel.  En annen fremgangsm?te er ? ha Etasje som egen klasse og da kan denne ha en array (eller HashMap) med hyblene i etasjen.


  3. Oppramstyper: "enum"  (side 158)
    Lag en oppramstype for m?neder (jan, feb,..) og et program som ber bruker taste inn m?nedsnummer (1, 2,..) og gir m?nedsnavnet som svar.  Hint: Se f?lgende eksempel fra side 158 i l?reboka (ogs? gitt p? side 2 i lysarkene uke 8): 
    enum Farge {
    r?d, gr?nn, bl?, gul;
}

class EnumEks {
    public static void main(String[] args) {
	Farge f = Farge.r?d;
	System.out.println("Farge f er:" + f);

	for (Farge ff: Farge.values()) {
	    System.out.println("ff:" + ff + ", nummer:" + ff.ordinal());
	}
    }
} // end class EnumEks

KJ?REEKSEMPEL:
Farge f er:r?d
ff:r?d, nummer:0
ff:gr?nn, nummer:1
ff:bl?, nummer:2
ff:gul, nummer:3

    enum Mnd {
    JAN, FEB, MAR, APR, MAI, JUN, JUL, AUG, SEP, OKT, NOV, DES;
}

class MndEks {
    public static void main(String[] args) {
	System.out.print("Tast m?nednr.: ");
	int mndNr = (new easyIO.In()).inInt();

	for (Mnd mnd : Mnd.values()) {
	    if (mnd.ordinal() == mndNr - 1) {
		System.out.println("M?neden heter: " + mnd);
	    }
	}
    }
}

KJ?REEKSEMPEL:
Tast m?nednr.: 10
M?neden heter: OKT
    For spesielt interesserte:
      // Mnd kan v?re nyttig for ? uttrykke m?neder direkte i programkode:
  Mnd julem?ned = Mnd.DES;
  Mnd nasjonalmnd = Mnd.MAI;
  Mnd[] sommer = { Mnd.JUN, Mnd.JUL, Mnd.AUG };
  // switch(m?ned) { case JAN: ... case FEB: ... }
    Mer info: http://java.sun.com/docs/books/tutorial/java/javaOO/enum.html


  4. Innstikksortering av kontoer:  (l?reboka side 93; lysark uke 8 s. 36)
    Ta utgangspunkt i programmet fra side 25 og 36 i lysarkene uke 8 (gjengitt under) som sorterer en heltalls-array og en String-array, og lag en metode som sorterer arrayen kontoer[] fra punkt 2 (a) alfabetisk p? navn.  Etter et kall p? metoden skal f.eks. kontoer[0] v?re Elins konto, kontoer[1] Nils sin, osv.  Metoden skal ha to inn-parametre: Konto[] kontoer, og int antKontoer; og skal kunne sortere et vilk?rlig antall kontoer.  Utvid programmet i punkt 2 (a) med et kall p? metoden for ? sjekke at den fungerer. 
    class Innstikksort {

    /** Sorterer en heltallsarray */
    public static void sorter(int[] a) {
	for (int k = 0 ; k < a.length - 1; k++) {

	    if (a[k] > a[k + 1]) {
		// a[k + 1] st?r p? feil plass, ta den ut:
		int tmp = a[k + 1];
                int i = k;

		// Skyv a[i] mot h?yre ett hakk til
		// vi finner riktig plass til tmp:
		while (i >= 0 && a[i] > tmp) {
		    a[i + 1] = a[i];
		    i--;
		}
		// Sett tmp inn p? riktig plass:
		a[i + 1] = tmp;
	    }
	}
    }

    /** Sorterer en String-array */
    public static void sorter(String[] a) {
	for (int k = 0 ; k < a.length - 1; k++) {
	    if (a[k].compareTo(a[k + 1]) > 0 ) {
		String tmp = a[k + 1];
		int i = k;
		while (i >= 0 && (a[i].compareTo(tmp) > 0)) {
		    a[i + 1] = a[i];
		    i--;
		}
		a[i + 1] = tmp;
	    }
	}
    }
}

/** Test av innstikksortering */
class TestInnstikksort {
    public static void main(String[] args) {

	int[] a = { 3, 1, 7, 14, 2, 156, 77 };
	Innstikksort.sorter(a);
	for (int i = 0; i < a.length; i++) {
	    System.out.println("a[" + i + "] = " + a[i]);
	}

	String[] navn = { "Ola", "Kari", "Arne", "Jo" };
	Innstikksort.sorter(navn);
	for (int i = 0; i < navn.length; i++) {
	    System.out.println("navn[" + i + "] = " + navn[i]);
	}
    }
}

KJ?REEKSEMPEL:
a[0] = 1
a[1] = 2
a[2] = 3
a[3] = 7
a[4] = 14
a[5] = 77
a[6] = 156
navn[0] = Arne
navn[1] = Jo
navn[2] = Kari
navn[3] = Ola

        /** Sorterer en Konto-array: Koden er basert p? sorter(String[] a) men
      * erstatter a[] med enten kontoer[] eller kontoer[].navn avhengig av om
      * man trenger objektet eller sorteringsnavn.  a.length -> antKontoer */
    public static void sorter(Konto[] kontoer, int antKontoer) {
	for (int k = 0 ; k < antKontoer - 1; k++) {
	    if (kontoer[k].navn.compareTo(kontoer[k + 1].navn) > 0 ) {
		Konto tmp = kontoer[k + 1];
		int i = k;
		while (i >= 0 && (kontoer[i].navn.compareTo(tmp.navn) > 0)) {
		    kontoer[i + 1] = kontoer[i];
		    i--;
		}
		kontoer[i + 1] = tmp;
	    }
	}
    }
    Legger ogs? til f?lgende testkode p? slutten av konstrukt?ren til Bank: 
    	// Kontosortering:
	System.out.println("Sorterer kontoene p? navn...");
	sorter(kontoer, antKontoer);
	for (int i = 0; i < antKontoer; i++) {
	    System.out.println("kontoer[" + i + "].navn = " + kontoer[i].navn
			       + ", saldo: " + kontoer[i].saldo);
	}

KJ?REEKSEMPEL:
Sorterer kontoene p? navn...
kontoer[0].navn = Elin, saldo: 8000
kontoer[1].navn = Nils, saldo: 4000
kontoer[2].navn = Tina, saldo: 9000

Oppgaver til terminaltimen

  1. HashMap, enum, og innstikksortering:
    (Samme oppgaver som i punkt 2 - 4 for teoritimen).
    (Se l?sningsforslagene ovenfor).


  2. Fortsett ? jobbe med din Oblig 3.  Se tipsene fra seminaret og Marits objekter.pdf.


  3. Mer om HashMap-er:  (som oppgave 4 i kap. 9, side 195)
    Finn fram en oppgave du har l?st vha. arrayer, og bytt ut noen av arrayene med HashMap-er.  Hvilke deler av programmet blir enklere n?, evt. vanskeligere?  Bruk gjerne din egen Oblig 2 eller 3.


  4. Javadoc:  (lysark uke 8, side 39 - 44)
    Se eksemplene p? javadoc-kommentarer her eller p? side 39 i lysarkene uke 8 og skriv lignende kommentarer i din Oblig 3.  Javadoc-kommentarer startes med /** og avsluttes med */, og plasseres i linjen(e) rett f?r klassen, metoden, eller objektvariabelen man ?nsker ? kommentere.  Kj?r deretter javadoc-kommandoen som vist p? side 40 i lysarkene: 
    > javadoc -package Programnavn.java
> opera index.html &
    ?pne til slutt den genererte index.html-filen i en browser for ? se p? resultatet.  (NB! Javadoc er ikke et krav i Oblig 3, men du kan godt begynne ? eksperimentere med det allerede n?!). 


  5. Ukens n?tt: Dobbel-sortert utskrift av HashMap  (veldig vanskelig!)
    Lag en metode "void skrivSortert(HashMap <String, Person> register)" som skriver ut innholdet i HashMap-en fra punkt 1 for teoritimen sortert p? alder.  Utskriften skal vise alder og navn for personene, og hvis det er flere med samme alder skal disse skrives ut sortert p? navn.  For ? teste metoden lager du et objekt av klassen Personer og kaller metoden din via dette objektet, etter ? ha lagt inn 5 personer i HashMap-en: Ida 19, Lars 21, Elin 21, Nils 19, og Anna 19.
    6. Send gjerne l?sningen din til josek@ifi.uio.no s? legger jeg den ut her.