I120 - Algoritmer, Datastrukturer og Programmering

Løsningsforslag
Oppgavesett 3

Oppgave 1

public class Oppgave1 {
    int fib(int tall, String innrykk) {
        // Skriv ut dette kallet:
        System.out.println(innrykk+"f("+tall+") ...");
        int res;
        if (tall<2) res = 1;
        else res = fib(tall-1,innrykk+"  ")+fib(tall-2,innrykk+"  ");
        // Skriv ut resultatet:
        System.out.println(innrykk+"= "+res);
        return res;
    }
    public static void main(String[] args) {
        Oppgave1 f = new Oppgave1(); // Kunne vaert static over??
        f.fib(5,"");
        f.fib(6,"");
    }
}
 

 

Oppgave 2

Vi viser hele programmet, der gensek løser punkt. 1 av oppgaven, og genperm punkt 4. Det er ingen løsning for punkt 2, men bare ta gensek og legg inn en test like før man begynner å skrive ut på om aktuell sekvens faktisk er en permutasjon.

Pseudokode for gensek(int i): 

for 1<j<n do
    insert j in position i
    if i==n do
        print sequence
    else
        gensek(i+1)
    endif
Pseudokode for genperm(int i): 
for 1<j<n do
    if digit j not already used earlier do
        insert j in position i
        if i==n do
            printout
        else
            genperm(i+1)
        endif
    endif
Kjøringstid til gensek: Grovt sett kaller gensek(i) gensek(i+1) n ganger, slik at kjøringstiden til gensek(i) blir n ganger kjøringstiden til gensek(i+1). Dette slutter med gensek(n) som har orden O(n2). Total kjøringstid blir altså O(n* n * n* ... * n2)=O(nn+1) når i = 1 (dvs vi starter med i=1 og generer sekvenser som er n tall lange). Mer generelt for metoden gensek(i) kan vi si den har tidskompleksitet O(nn-i+2). Test dette for i=1 og n=10 (som er tilfellet over) og i=5, n= 10.

Kjøringstiden til genperm: Her er det nyttig å se på de første metodekallene. I første iterasjon, kaller genperm(i) genperm(i+1) n ganger. I neste iterasjon blir gensek(i+2) kalt n-1 ganger  (fordi vi har brukt ett tall) osv. Tidskompleksiteten blir derfor n*(n-1)*(n-2)*...* 1 = n!

Her ser vi at n! < nn+1 fordi 1*2*...*(n-1)*n helt klart er mindre enn n*n*...*n
 
 

Oppgave 3

En datainvariant for Conways life er følgende. For enhver eksisterende celle i,j i generasjon k, så hadde den 2 eller tre naboer i generasjon k-1.
Utifra denne invarianten kan vi si at regelsettet for Conways life er en potensiell datainvariant.

Et potensielt problem med denne invarianten er hva som skjer når vi oppdaterer matrisen via det grafiske grensesnittet (GridMatrix) og/eller kommandoen b x y. Dette er faktisk ikke et problem fordi det grafiske grensesnittet har sin egen interne matrise (med egne datainvarianter!) og Conways life en matrise. En slik datainvariant har konsekvenser for implementasjonen av Conways life. Blant annet må vi kopiere matrisen fra GridMatrix til Conways Life foran hvert steg av algoritmen. Dersom disse hadde delt på matrisen, så hadde algoritmen vært raskere fordi vi slipper å kopiere matrisen hver gang, men mulighetene for at feil eller unntakstilfeller oppstår er mye større.

Oppgave 3.1

public class DIException extends RuntimeException {
    public DIException() {
        super();}
    public DIException(String s) {
        super(s);}
}
public class R1 implements Rasjonal {
    private int nev, tel;
    public R1(int teller, int nevner) {    
        if(DI()) { 
            nev = nevner;
            tel = teller;
        } else {
            throw new DIException(); 
        }
    }
    public int teller() { return tel; }
    public int nevner() { return nev; }
    public void add(Rasjonal x) {
        if(!DI()) throw new DIException();
        n = nev*x.nevner();
        tel = tel*x.nevner() + x.teller()*nev;
        nev = n;
        if(!DI()) throw new DIException();
        }
    public void sub(Rasjonal x) {
        if(!DI()) throw new DIException();
        n = nev*x.nevner();
        tel = tel*x.nevner() - x.teller()*nev;
        nev = n;
        if(!DI()) throw new DIException();
        }
    public void mul(Rasjonal x) {
        if(!DI()) throw new DIException();
        nev = nev*x.nevner();
        tel = tel*x.teller();
        if(!DI()) throw new DIException();
        }
    public void div(Rasjonal x) {
        if(x.teller() == 0) throw new DIException();
        nev = nev*x.teller();
        tel = tel*x.nevner();
        if(!DI()) throw new DIException();
        }
    public boolean eq(Rasjonal x) {
        return tel*x.nevner()==nev*x.teller(); }
    public boolean lt(Rasjonal x) {
        if(nev * x.nevner() < 0) 
            return tel*x.nevner() < x.teller()*nev;
        else 
            return tel*x.nevner() > x.teller()*nev; 
        }
    protected boolean DI() {
        return (nev != 0); }
}

Oppgave 3.2

I den neste implementasjonen bruker vi en sterkere datainvariant: 
    protected boolean DI() {
        return (nev > 0); }
Nå er kravet at nevner også må være positiv, ikke bare forskjellig fra 0.  I tillegg til å endre metoden protected boolean DI(), så endres også implementasjonen av metoden public boolean lt(Rasjonal x): 
    public boolean lt(Rasjonal x) {
        return tel*x.nevner() < x.teller()*nev;
        }
Denne er blitt forenklet siden vi ikke lenger trenger å sjekke fortegnet til begge nevnerne. Dette viser at ved å bruke en sterkere datainvariant, kan vi gjøre implementasjon enklere og mer forståelig. I de andre metodene verken kan eller trenger vi endre implementasjonen.

Oppgave 3.3

Et tredje alternativ for datainvariant er å kreve at nevner er positiv og at brøken er forkortet, dvs at teller og nevner er dividert med største felles divisor (Greatest Common Divisor). Metoden DI() vil da se ut som følger: 
protected boolean DI() {
    return (nev > 0 && gcd(tel,nev) == 1)
protected int gcd(tel,nev) {
    if(nev == 0) then return tel
    else return (gcd(nev, tel%nev);}
der gcd(a,b) er en metode som finner den største felles divisor mellom to tall a og b.
gcd(a,b) er også et godt eksempel på en rekursiv metode!!

I dette tilfellet kan vi forenkle public boolean eq(Rasjonal x) til å sammenligne teller mot teller og nevner mot nevner, istedenfor den formelen som brukes i implementasjonen i oppgave 2.1. 

    public boolean eq(Rasjonal x) {
        return (tel==x.teller && nev==x.nevner()); }
Men i dette tilfellet må vi også legge til en metode som forenkler brøken etter en addisjon, subtraksjon, multiplikasjon og divisjon, siden vi ikke er garantert at brøken er forkortet etter en slik operasjon.

Poenget med denne oppgaven har vært å vise hvordan man kan forenkle implementasjonen ved å innføre en sterkere datainvariant. I noen tilfeller vil vi måtte utvide enkelte metoder for å sikre at datainvarianten er oppfylt, men alt i alt vil vi
som regel få en ryddigere og enklere implementasjon når vi bruker sterkere datainvarianter.