Du er ikke logget inn. Så lenge du ikke er logget inn går du glipp av muligheten for å holde styr på din egen progresjon.

Logg inn

Valgte tags:

Filtrering:

Skriv ut:

05.3: GeneriskStabel.java

Det er én stor ulempe med vår implementasjon av KvadratStabel: Stabelen virker kun for Kvadrat-objekter.

Vi kan løse dette problemet ved å gjøre listen generisk. Dette fører til at også nodene må være generiske.

Implementér en stabel med samme grensesnitt som KvadratStabel som tar en klasseparameter <E>, og kall den GeneriskStabel. Du kan teste løsningen din med dette testprogrammet:

public class TestGeneriskStabel {
    public static void main(String[] args) {
        GeneriskStabel<String> stabel = new GeneriskStabel<String>();
        stabel.leggPaa("foobar");
        stabel.leggPaa("bazar");
        stabel.leggPaa("baz");
        stabel.leggPaa("bar");
        stabel.leggPaa("Foo");
        String resultat = "";
        while (!stabel.erTom())
            resultat += stabel.taAv() + " ";
        System.out.printf("Resultatet er: '%s'\n", resultat);
    } 
}

Resultatet skal være: 'Foo bar baz bazar foobar '.

05.4: Palindrom.java

Et palindrom er en sekvens med symboler som er helt lik lest fra venstre til høyre som lest fra høyre til venstre.

Skriv et program som tar vilkårlig mange kommandolinjeargumenter. Programmet skal skrive ut om sekvensen av bokstaver fra kommandolinjeargumentene utgjør et palindrom eller ikke. Bruk GeneriskStabel fra oppgave 5.3.

05.5: DobbelLenke.java

I denne utfordringsoppgaven skal vi anvende vår kunnskap om generiske klasser (klasser med parametere) på en lenkeliste. Du skal opprette en dobbeltlenket liste som kan holde på objekter av vilkårlig type. I en dobbeltlenket liste er alle elementer lenket sammen med både det neste, og det forrige elementet i lista. Du trenger med andre ord både en neste-peker og en forrige-peker.

a) Lag en klasse DobbelLenke som tar en generisk parameter . Klassen skal inneholde en indre privat klasse Node.

b) La Node-klassen inneholde en peker Node neste og Node forrige. Node-klassen skal også inneholde en peker til T data. Det er nodene som skal lenkes sammen i din lenkeliste. Legg til slutt inn en peker til Node forste i den ytre klassen (altså DobbelLenke).

c) Nå trenger du en metode for å sette inn data i listen. Lag en metode public void settInn(T element) i DobbelLenke-klassen. Dersom førstepekeren er null, skal du opprette en node med element som data-innhold, og la denne være første element i listen. Er førstepekeren ikke null, skal du gå via første-pekeren, innover i listen, og finne det siste elementet. Etter dette, setter du inn den nye noden. Husk å sette den nye nodens forrige-peker til det nest siste elementet, og det nest siste elementets neste-peker til å peke til noden.

Her er det mye pekere, og det er viktig å holde tungen rett i munnen! Blir det for mye å holde styr på, kan det være en god idé å lage en enkeltlenket liste først, og siden utvide til doble lenker.

05.6: MittSkipErLastetMed.java

I leken "Mitt skip er lastet med" er det om å gjøre å komme på ord som begynner på en gitt bokstav. Vi skal lage et program som skal simulere hvordan leken vil utspille seg gitt en fil med alle ordene i deltagernes ordforråd.

Vi definerer reglene slik at man begynner på en tilfeldig bokstav, så sies det et ord, og neste ord skal da begynne på samme bokstav som det forrige ordet sluttet på. Et ord som er blitt sagt kan ikke brukes igjen.
Det kan for eksempel utspille seg slik:
Bokstaven b velges, så sies "banan", "ninja", "aritet", "tetraeder" osv.

a)
Lag en metode forsteBokstavI(String ord) som returnerer det første tegnet i ord. (Du kan anta at lengden på strengen er større enn 0).

Hint: Du kan bruke metoden charAt(int pos) i String for å hente ut tegnet på plass pos i strengen.

b)
Lag en metode sisteBokstavI(String ord) som returnerer det siste tegnet i ord. (Du kan også her anta at lengden på strengen er større enn 0).

c)
Lag en klasse Ordliste som har en HashMap<Character, Node> som skal kunne gi den første noden i lenkelisten med alle ordene som begynner på en gitt bokstav, og la den ha en indre klasse Node med metoder for å hente ut ordet og hente / sette neste.

d)
Utvid Ordliste med en metode leggTil(String ord).

e)
Utvid Ordliste med en metode taUt(char forsteBokstav). Denne metoden tar ut et ord fra listen. Du kan selv bestemme hvordan du velger hvilket ord som skal tas ut. (Det er lov å gjøre det enkelt).

Du kan anta det finnes et ord som begynner på denne bokstaven hvis metoden kalles.

f)
Lag til slutt en metode spill(char startbokstav) som simulerer et spill inntil det ikke finnes noe ord som begynner på samme bokstav som det forrige ordet sluttet med.

Skriv ut ordene etter hvert som de tas ut.

Du kan bruke følgende hovedprogram til å teste koden din.

class MittSkipErLastetMed {
    public static void main(String[] args) {
        String filnavn = args[0];
        File fil = new File(filnavn);
        Scanner inn = null;
        try {
            inn = new Scanner(fil);
        } catch (FileNotFoundException e) {
            System.out.printf("Fant ikke filen '%s'\n", filnavn);
            System.exit(1);
        }

        Ordliste ordliste = new Ordliste();
        while (inn.hasNextLine()) {
            String ord = inn.nextLine();
            ordliste.leggTil(ord);
        }

        inn.close();

        char startbokstav = args[1].charAt(0);
        ordliste.spill(startbokstav);
    }
}

Programmet kan brukes på følgende måte (da leses ord fra ord.txt og
programmet begynner på bokstaven b)

java MittSkipErLastetMed ord.txt b

Filnavn: MittSkipErLastetMed.java, Ordliste.java.

Vis løsningsforslag
import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Scanner;

class MittSkipErLastetMed {
    public static void main(String[] args) {
        String filnavn = args[0];
        File fil = new File(filnavn);
        Scanner inn = null;
        try {
            inn = new Scanner(fil);
        } catch (FileNotFoundException e) {
            System.out.printf("Fant ikke filen '%s'\n", filnavn);
            System.exit(1);
        }

        Ordliste ordliste = new Ordliste();
        while (inn.hasNextLine()) {
            String ord = inn.nextLine();
            ordliste.leggTil(ord);
        }

        inn.close();

        char startbokstav = args[1].charAt(0);
        ordliste.spill(startbokstav);
    }

    public static char forsteBokstavI(String ord) {
        return ord.charAt(0);
    }

    public static char sisteBokstavI(String ord) {
        return ord.charAt(ord.length()-1);
    }
}
class Ordliste {
    private HashMap<Character, Node> forstenoder;

    private class Node {
        private Node neste;
        private String ord;

        Node(String ord) {
            this.ord = ord;
        }

        public String hentOrd() {
            return this.ord;
        }

        public Node hentNeste() {
            return this.neste;
        }

        public void settNeste(Node neste) {
            this.neste = neste;
        }
    }

    Ordliste() {
        forstenoder = new HashMap<>();
    }

    public void leggTil(String ord) {
        char forsteBokstav = MittSkipErLastetMed.forsteBokstavI(ord);
        Node ny = new Node(ord);
        if (forstenoder.containsKey(forsteBokstav)) {
            Node foran = forstenoder.get(forsteBokstav);

            /* vi setter inn det nye ordet rett bak det forste for aa 
               slippe aa endre HashMap-et */
            // sett ny til aa peke pa det som kommer etter neste
            // (dette kan vaere null, men det gaar greit)
            ny.settNeste(foran.hentNeste());

            // saa settes foran sin neste til aa peke paa ny
            foran.settNeste(ny);
        } else {
            // dette er det forste ordet som begynner paa den bokstaven
            forstenoder.put(forsteBokstav, ny);
        }
    }

    /* tar ut det nest forste ordet i listen (eller det forste, hvis det
       bare er ett igjen) */
    public String taUtVariant1(char forsteBokstav) {
        String ord;
        Node foran = forstenoder.get(forsteBokstav);
        if (foran.hentNeste() != null) {
            Node naavaerende = foran.hentNeste();
            ord = naavaerende.hentOrd();
            foran.settNeste(naavaerende.hentNeste());
        } else {
            ord = foran.hentOrd();
            /* fjern noden fra HashMap-et siden det ikke er flere 
               ord som begynner paa den bokstaven */
            forstenoder.remove(forsteBokstav);
        }
        return ord;
    }

    /* tar ut det forste ordet i listen */
    public String taUtVariant2(char forsteBokstav) {
        Node foran = forstenoder.get(forsteBokstav);
        String ord = foran.hentOrd();

        Node etter = foran.hentNeste();
        if (etter != null) {
            forstenoder.put(forsteBokstav, etter);
        } else {
            forstenoder.remove(forsteBokstav);
        }

        return ord;
    }

    public String taUt(char forsteBokstav) {
        return taUtVariant2(forsteBokstav);
    }

    public void spill(char startbokstav) {
        int teller = 0;
        char forsteBokstav = startbokstav;
        while (forstenoder.containsKey(forsteBokstav)) {
            String ord = taUt(forsteBokstav);
            System.out.println(ord);

            // gjor klar til neste runde
            forsteBokstav = MittSkipErLastetMed.sisteBokstavI(ord);
            teller++;
        }

        System.out.println("\nSPILLET ER OVER");
        System.out.printf("\nAntall ord som ble brukt: %d\n", teller);
    }
}

06.1: SimpleArrayList.java

Implementer klassen SimpleArrayList som er en liste basert på et array. En liste skal inneholde et array, og elementene i listen puttes på neste ledige plass i arrayen når de blir lagt til. For enkelhets skyld vil vi ikke tillate sletting fra listen, kun innlegging. La også listen ha en bestemt kapasitet som konstruktøren tar som parameter. Du trenger ikke implementere utvidelse av kapasiteten.

Listen skal være itererbar, dvs. implementere grensesnittet java.util.Iterable med medfølgende implementasjon av java.util.Iterator.

(Hint: Generiske arrayer er tildels vanskelige å jobbe med. Bruk heller et Object-array.)

06.2: SimpleQueue.java

Gitt følgende interface:

/** A simple queue interface.
 * This is a subset of the Queue interface in the java api.
 * @param <E> The type of element to put in the queue (a
 *            class name).
 * */
public interface SimpleQueue<E>
{
    /** Add an element to the collection.
     * @param e The element.
     * @return true if this collection changed as a result
     *         of the the call.
     * */
    public boolean add(E e);
    /** Remove and return one element from the queue.
     * @return a element or null if the queue is empty.
     * */
    public E poll();
}

a) Lag en FIFO. og en LIFO-kø som implementerer interfacet.

b) Implementer java.lang.Iterable interfacet i listeklassene du lagde i deloppgave a.

c) Legg til andre metoder som du mener er nyttige å ha i en kø.

06.3: DobbeltLenket.java

Skriv et generisk grensesnitt for en beholder som implementerer en stakk (stabel) . La de offentlige metodene være push(), top() og pop(). I tillegg skal det være mulig å iterere over innholdet i stakken (grensesnittet skal utvide Iterable).

Du skal skrive to implementasjoner av dette grensesnittet som begge brukere lenkelister. I iteratoren skal du implementere alle de tre metodene (dvs. også remove()).

I den ene implementasjonen skal du bruke en dobbeltlenket liste for å kunne fjerne et element midt i lista. I den andre implementasjonen skal du bruke en enkeltlenket liste.

(Hint: Da må du ha en peker i iteratoren som “liggre litt etter”.)

07.1: RekursivListe.java

For å gjøre denne oppgaven trenger vi en liste å ta utgangspunkt i, så vi bruker lista fra oppgave 5.5).

a) Skriv innsettingsmetoden helt uten bruk av for- eller while-løkker. For å få til dette trenger du en rekursiv metode i nodeklassen.
(Hint: innsettingsmetoden vil kun trenge gjøre et kall på hode-objektet sin rekursive metode.)

b) Skriv om resten av metodene som inneholder for- eller while-løkker til rekursive varianter.

Dersom du ønsker mer øving i rekursjon kan du gjøre deloppgave a og b for alle listene du skrev i uke 5.

07.2: RekursivStack.java - utvidelse

a) Utvid RekursivListe.java fra forrige oppgave ved å implementere grensesnittet Iterable. Du trenger da en indre klasse "ListIterator" som implementerer grensesnittet Iterator.

b) Lag et testprogram som lager en RekursivListe, fyller den med Square-objekter, og skriver ut disse ved hjelp av en for-each-løkke ("forenklet for-løkke").

07.3: Fakultet.java

n! ("n fakultet") er matematisk definert til å være produktet av alle positive heltall mellom n og 1.

a) Skriv en klasse Fakultet med en metode static int fakultet(int n) som beregner n! ved hjelp av ekte rekursjon.

b) Skriv en metode static int fak-iter(int n) som beregner n! iterativt, altså ved hjelp av en løkkestruktur.

08.1: TallMonitor.java

a) Skriv en monitor som holder orden på to tall, f.eks. kalt hhv. detMinste og detStorste. En invariant tilstandspåstand i monitoren skal være at detMinste < detStorste. Monitoren skal ha to offentlige (boolske) metoder settMinste og settStorste som gir ny verdi til hhv. det minste og det største tallet. Dersom operasjonen ikke ødelegger innvarianten skal det returneres sann (true). Hvis operasjonen ikke kan utføres (altså at det vil bryte med innvarianten), skal det returneres usann (false).

b) Skriv to tråder Nedover og Oppover. Nedover skal starte med Integer.MAX_VALUE og telle nedover. For hvert nye tall kalles metoden settStorste i monitoren. Oppover skal starte med Integer.MIN_VALUE, telle oppover og kalle monitorens sin settMinste. Trådene skal fortsette så lenge sann returneres. Dersom det returneres usant skal tallet som ble forsøkt lagt inn skrives ut, og tråden skal stoppe.

08.2 N-te tall

a) Lag en trådklasse som skriver ut hvert 10ende tall fra 5 opp til 1000.

b) Lag en trådklasse som skriver ut hvert n -te tall fra start opp til maks . La n , start og maks være parametre til trådens konstruktør.

c) Opprett og start 10 slike tråder der hver tråd skriver ut hvert 10ende tall (med start hhv. 0,1, ..., 9) opp til 10000.

d) Skriv en monitor med en metode som tar i mot et tall og skriver det ut. Modifiser trådklassen fra deloppgave b slik at den kaller metoden i denne monitoren med tallet som parameter istedenfor å skrive tallet ut. La metoden i monitoren skrive ut tallet istedet. (Hint: Det skal ikke være noe venting i denne monitoren.)

e) Modifiser monitoren i deloppgave d slik at den skriver ut alle tallene den mottar i riktig rekkefølge (dvs. 0,1,2,3, ..., 10000). (Altså en svært komplisert måte å skrive ut tallene fra 0 til 10000). (Hint: Det skal være venting i denne monitoren.)

08.3 Producer - consumer, Postkontor

I denne oppgaven skal vi modellere en enkel versjon av hvordan et postkontor fungerer. Vi skal ha klassene for Post, Postmann, Postkontor og Kunde. I denne versjonen av et postkontor skal postmannen levere pakker til kontoret og kundene skal plukke opp pakker som er til dem.

a) Skriv klassen Post. Klassen skal inneholde en beskrivelse i form av en String og en mottaker i for av en String. Legg også til relevate get- og set-metoder.

b) Skriv en trådklassen Postmann. I run-metoden skal postmannen lage 100 pakker og levere dem en etter en til postkontoret.

c) Skriv trådklassen Kunde. Kunden skal være identifiserbar med en navn (String) som skal matche det brukt i mottaker-stringen i klassen Post. Kunden skal stille seg i kø på postkontoret og plukke opp post til seg. Når kunden får post skal innholdet skrives ut og kunden stille seg i kø og vente på mer post.

d) Skriv monitoren Postkontor. Postkontoret skal inneholde et array med Post av lengde 10.

1) Lag en metode public void leverPost(Post p). Pust posten inn i arrayet dersom det er plass til det, eller vent til det er ledig plass (Hint: bruk wait() eller en Condition)

2) Lag metode public Post hentPost() som returnerer post dersom det er en post på postkontoret eller som venter dersom det ikke er det. (Hint: bruk wait() eller en Condition)

(Hint: metodene leverPost og hentPost utfyller hverandre som hent/sett-metoder)

e) Utvidt metoded hentpost til å ta imot en en String mottaker. Da skal den kun returnere pakker som har personen som kaller den som mottaker, eller vente dersom det ikke er noen slike pakker. (Hint: bruk wait() eller en Condition)

f) Utvid klassen Post med to subklasser Brev og Pakke med ulike utskrifter for personen.

08.4 Bank og saldo

Lag en monitor-klasse som du kaller Bank og som inneholder et pengebeløp. Den skal
inneholde metodene ta() , gi() og saldo() .

Lag en trådklasse som først tar ut et beløp (kaller på ta() ), og så setter inn det samme beløpet (kaller gi() ). Tråden skal gå i løkke og gjøre dette mange ganger.

Hver gang en tråd er ferdig med å både ta ut penger og sette inn det samme beløpet skal den kalle metoden saldo() for å finne hvor mange penger det er i banken. Skriv ut dette beløpet.

Opprett mange tråder av trådklassen og kjør disse i parallell. Lag gjerne en konstruktør til trådklassen slik at alle trådene tar ut og setter inn forskjellige beløp.

a) Skriv først monitoren uten synchronized foran noen av metodene, og se hva som da skjer. Er saldoen alltid den samme før og etter uttak?

Legg inn et kall på metoden Thread.sleep() mellom alle (eller noen av) setningene i
metodene ta og gi. Hva skjer da? Hva skjer hvis du lar parameteren til sleep være et tilfeldig tall? (Bruk f.eks. Math.random()*1000 i parameteren til Thread.sleep )

b) Legg til synchronized foran alle metodene og se hva som skjer.

09.1 Moenster.java

I denne oppgaven skal du trene på å bruke modulo-operatoren %. Fra før kjenner du divisjonsoperatoren /. Den gir som svar hvor mange ganger divisoren (tallet det deles på) går opp i dividenden (tallet som deles). Modulo-operatoren gir i stedet resten ved divisjon.
For eksempel er 7 / 3 lik 2 (7 går opp 2 ganger i 3) og 7 % 3 lik 1 (resten som blir igjen når vi deler 7 på 3).
En annen måte å se det på er som en omskrivning til blandede tall. 7/3 er det samme som 2 + 1/3. Generelt kan vi skrive om en uekte (a > b) brøk a/b til blandede tall ved å bruke heltallsdivisjon og modulo. Resultatet blir (a / b) + (a % b) b-deler.

Lag en klasse Moenster. Metodene du skriver i denne oppgaven kan alle være public static void. Du kan bruke følgende main-metode for å teste utskriftene dine.

class Moenster {
    public static void main(String[] args) {
        uthevHverNteEnkel(3, 16);
        uthevHverNteModulo(3, 16);
        sjakk(16, 10);
        uthevRektangler(16, 10, 3, 2);
        firkantception(16, 10);
    }
}

Merk: Kodeblokker i trix har dobbel linjeavstand. Derfor ser mønstrene mer luftige ut (i vertikal retning) her enn de vil gjøre i et terminalvindu.

a) Skriv en metode uthevHverNteEnkel(int n, int antTegn) som skriver ut en linje med antTegn tegn, hvor hvert n-te tegn er en X og resten er mellomrom. Bruk en for-løkke som for hver runde skriver ut et mellomrom n-1 ganger og skriv så ut en X. Pass på at det ikke skrives ut for mange tegn. Legg inn to linjeskift på slutten slik at det blir lettere å se hva utskriften inneholder.
Eksempel på utskrift fra et kall på metoden med n=3 og antTegn = 16:

  X  X  X  X  X 

b) Skriv en ny metode uthevHverNteModulo(int n, int antTegn) som gjør det samme som den forrige metoden, men som bruker modulo for å avgjøre om tegnet skal utheves eller ikke.

c) Skriv en metode sjakk(int bredde, int hoyde) som lager et sjakkmønster innenfor et rektangulært område.

Eksempel på utskrift med bredde=16 og hoyde=10:

 X X X X X X X X
X X X X X X X X
 X X X X X X X X
X X X X X X X X
 X X X X X X X X
X X X X X X X X
 X X X X X X X X
X X X X X X X X
 X X X X X X X X
X X X X X X X X

Tips: Bruk 2 for-løkker inni hverandre som beveger seg i hver sin dimensjon.
Hint: Hva er spesielt for x- og y-koordinatene i ruter som skal utheves?

d) Skriv en metode uthevRektangler(int bredde, int hoyde, int rBredde, int rHoyde) som lager et sjakkmønster med rektangler med dimensjoner (rBredde x rHoyde).

Eksempel på utskrift med bredde=16, hoyde=10, rBredde=3 og rHoyde=2:

   XXX   XXX   X
   XXX   XXX   X
XXX   XXX   XXX
XXX   XXX   XXX
   XXX   XXX   X
   XXX   XXX   X
XXX   XXX   XXX
XXX   XXX   XXX
   XXX   XXX   X
   XXX   XXX   X

Hint: Forsøk å definere (matematisk) en funksjon slik at alle koordinatene innenfor et av rektanglene ordnes til én rute i sjakkbrettet fra forrige oppgave.

e) Skriv en metode firkantception(int bredde, int hoyde) som kalt med bredde=16 og hoyde=10 lager følgende mønster:

XXXXXXXXXXXXXXXX
X
X XXXXXXXXXXXXXX
X X
X X XXXXXXXXXXXX
X X X
X X X XXXXXXXXXX
X X X X
X X X X XXXXXXXX
X X X X X

Tips: Du kan få bruk for Math.min() for å finne det minste av to tall.

Vis løsningsforslag
class Moenster {
    public static void main(String[] args) {
        uthevHverNteEnkel(3, 16);
        uthevHverNteModulo(3, 16);
        sjakk(16, 10);
        uthevRektangler(16, 10, 3, 2);
        firkantception(16, 10);
    }

    public static void uthevHverNteEnkel(int n, int antTegn) {
        for (int i=0; i < antTegn/n; i++) {
            for (int j=0; j < n-1; j++) {
                System.out.print(' ');
            }
            System.out.print('X');
        }
        System.out.println();
        System.out.println();
    }

    public static void uthevHverNteModulo(int n, int antTegn) {
        for (int i=1; i <= antTegn; i++) {
            if ((i % n) == 0) {
                System.out.print('X');
            } else {
                System.out.print(' ');
            }
        }
        System.out.println();
        System.out.println();
    }

    public static void sjakk(int bredde, int hoyde) {
        for (int i=0; i < hoyde; i++) {
            for (int j=0; j < bredde; j++) {
                if ((i+j) % 2 == 1) {
                    System.out.print('X');
                } else {
                    System.out.print(' ');
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void uthevRektangler(int bredde, int hoyde, 
                                       int rBredde, int rHoyde) {
        for (int i=0; i < hoyde; i++) {
            for (int j=0; j < bredde; j++) {
                if ((i / rHoyde + j / rBredde) % 2 == 1) {
                    System.out.print('X');
                } else {
                    System.out.print(' ');
                }
            }
            System.out.println();
        }
        System.out.println();        
    }

    public static void firkantception(int bredde, int hoyde) {
        for (int i=0; i < hoyde; i++) {
            for (int j=0; j < bredde; j++) {
                if (Math.min(i,j) % 2 == 0) {
                    System.out.print('X');
                } else {
                    System.out.print(' ');
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

10.0: Om sortering og invarianter

Studien av sorteringsalgoritmer er et eget felt som ikke har så mye med objektorientert programmering å gjøre, men det er likevel en type algoritmer som egner seg godt til bruk i introduksjonskurs i programmering av flere grunner: Sortering er et enkelt problem å forstå, idéen bak algoritmen er ofte ikke så vanskelig å skjønne og dessuten er det trivielt å sjekke om svaret (og dermed også implementasjonen) er riktig.

I INF1010 er vi ikke så opptatt av hvilke algoritmer som er raske og det er heller ikke viktig å kunne dem utenat - det sentrale er at en skal kunne implementere en gitt algoritme basert på en detaljert beskrivelse.

En algoritmebeskrivelse inneholder gjerne et sett med regler som må følges for at algoritmen skal virke. En type av slike regler kalles invarianter. En invariant er en betingelse som alltid er sann så lenge programmet kjører. I sortering er denne ofte utformet slik at den først gjelder kun noen få av elementene, og så følger vi en algoritme slik at stadig flere av elementene oppfyller denne betingelsen. For eksempel kan en sortere kort ved å trekke ett og ett kort og sørge for at det nye kortet alltid settes inn på riktig plass. Da vil kortene på hånden alltid være sortert - dette er invarianten som brukes i innstikksortering.

10.1: Utvalgssortering.java

En av de enkleste sorteringsalgoritmene er utvalgssortering (eng: selection sort).
Enkelt forklart finner algoritmen det minste elementet og bytter det med det første elementet, så finner den det minste elementet blant alle elementene unntatt det første og bytter dette med det andre elementet.

Invarianten her er at etter n runder ligger de n minste tallene i stigende rekkefølge på de n første plassene, og vi sørger for å opprettholde den ved å finne det n+1-te minste elementet og bytte dette med det som står på plass n+1.

a)

Skriv en static metode sorter(ArrayList<String> a) som sorterer elementene i a ved hjelp av utvalgssortering.

Metoden kan returnere en ArrayList<String>.

Hint: La metoden opprette en ny ArrayList<String> b. Finn og fjern det (leksikalsk) minste elementet i a og legg dette inn bakerst i b inntil a er tom, og returnér til slutt b.

b)

Skriv en static metode sorter(int[] a) som sorterer a ved hjelp av utvalgssortering. Metoden trenger ikke å returnere noe.

10.2: Innstikksortering.java

En annen enkel sorteringsalgoritmene er innstikksortering
(eng: insertion sort).
Dette er en vanlig algoritme å bruke til å sortere kort som deles ut.
Invarianten er at kortene på hånden alltid er sortert.

  1. En starter med å trekke ett kort. Ett kort er uansett sortert - invarianten holder.
  2. Så trekker en enda et kort og setter det inn på riktig plass - invarianten holder fortsatt.

Steg 2 gjentas inntil det ikke er flere kort å trekke.

a)

Skriv en static metode sorter(int[] a) som sorterer a ved hjelp av
innstikksortering. Metoden trenger ikke å returnere noe.

11.1 Lesing fra fil med GUI

  1. Lag et program som tegner et vindu med en knapp (se Button) på skjermen. Teksten på knappen velger du selv.
  2. Lag et program med en knapp og et tekstområde (f.eks. med TextArea). Når brukeren trykker på knappen, skal det vises en tekst i tekstområdet.
  3. Lag et program med en knapp, et tekstfelt og et tekstområde. I tekstfeltet skal brukeren oppgi et filnavn. Hvis filen finnes, skal innholdet vises i tekstområdet når brukeren har trykket på knappen. Eksperimentér med forskjellige layouter til du får et fint skjermbilde.

OBS: Her kan man bruke klassen FileChooser som finnes i JavaFX. Eks:

// Først oppretter man FileChooseren
FileChooser fileChooser = new FileChooser();
fileChooser.setTitle("Last inn fil...");
// Deretter vil vi ha et filter for tekstfiler
ExtensionFilter filter = new ExtensionFilter("Tekstfiler", "*.txt");
fileChooser.getExtensionFilters().add(filter);
// Åpne dialogvinduet, med peker til Stage som skal "låses" mens dialogvinduet er åpent
File selectedFile = fileChooser.showOpenDialog(mainStage);
// returnerer et filobjekt eller null hvis ingen fil ble valgt
if (selectedFile != null) {
    // File-objektet kan nå leses med Scanner
}

11.2 Tripp, trapp, tresko

I denne oppgaven skal man lage en enkel versjon av spillet tripp trapp tresko (også kjent som bondesjakk eller tre på rad).

Spillet har to spillere og foregår på et 3x3-brett. Spillerne setter enten ut et kryss (X) eller en sirkel (O). Brettet blir da f.eks. seende slik ut:

X| |O
-----
 |X|O
-----
 |O|x

I dette tilfellet har spilleren med kryss vunnet da hun har tre på rad. Oppgaven vil gå ut på å implementere spillet slik at man kan sette ut brikker og forsøke å få 3 på rad.

  1. Først skal du lage et vindu og fylle det med 9 (3x3) knapper (se Button). Til å begynne med skal ikke knappene ha noe tekst.
  2. Legg til en EventHandler på knappene. Når man trykker på en knapp skal enten et kryss eller en sirkel skrives på knappen. Til dette kan man bruke metoden setText(). (Husk at man må holde styr på hvilke spiller det er sin tur.)
  3. Lag en beholder for rutene (knappene) slik at man kan holde styr på hvilken rad, kolonne og evt diagonal ruten ligger i. Opprett en beholder per rad, kolonne og diagonal og putt de riktige rutene i rikitige beholdere.
  4. Lag en metode i beholderen som sjekker om det er tre like i beholderen (husk å ignorere det dersom det er tre tomme ruter)
  5. Sjekk om noen har vunnet hver gang en rute blir endret og skriv ut dersom vi har en vinner. (Her kan man bruke klassen Alert for å vise et dialogvindu)
  6. Når en knapp har blitt trykket ønsker vi ikke lenger at noen kan endre brikken i ruten. Gjør at det ikke lenger er mulig.
  7. Lag en knapp som nullstiller brettet slik at det er tomt og at spilleren med kryss starter.

Tips til bruk av klassen Alert i deloppgave 5:

// Lag en alert med typen Information
Alert alert = new Alert(AlertType.INFORMATION);
alert.setTitle("Information Dialog"); // tekst i tittelfeltet
alert.setHeaderText(null); // Ingen headertekst
alert.setContentText("Spiller X har vunnet!");
alert.showAndWait();

Ekstra oppgave:

Dersom man vil kan man følge reglene litt mer strengt. Ta hensyn til at en spiller kun kan ha 3 brikker på brettet på en gang (altså må en brikke plukkes opp og settes ut på nytt). I dette tilfellet må man deaktivere knappene som ikke inneholder den brikken man skal flytte. Dette må gjøres i to trykk (ett for å plukke opp, og ett for å sette ned brikken).