Oppgave 1: Fibonacci-utskrift

• argumentet
• rekursjonsdybde
• returnert resultat.

Gi en enkel regel som bestemmer, for en slik utskrift, hvilken returverdilinje '=x' som tilhører en gitt kallinje 'f(y)...'
 

Oppgave 2: Rekursjon og avskjæring

1. I den første delen ønsker vi å generere/skrive ut alle mulige kombinasjoner av lengde n av de n første tallene. For n=3 vil vi skrive ut sekvensene

111  112  113  121  122  ...  ...  332  333

Vi har derfor en global array int[] p=new int[n], og ønsker å lage metoder som genererer alle mulige kombinasjoner. For n=3 kunne en iterativ variant være

void gen1() {
  for (int i=1;i<=3;i++) {p[0]=i; gen2();}
}

void gen2() {
  for (int i=1;i<=3;i++) {p[1]=i; gen3();}
}

void gen3() {
  for (int i=1;i<=3;i++) {p[2]=i; "skriv ut p";}
}

int[] p=new int[3];

For n=3 gjør gen1() jobben med å generere (i p) alle kombinasjoner fra 111 til 333. Vi merker at det første sifferet (p[0]) går "sakte" opp, mens det siste (p[2]) går fort. Det er imidlertid  kjedelig/meningsløst/unødvendig å skrive 3 neste like metoder gen1, gen2 og gen3. Dessuten er det umulig å få til dette for vilkårlige n. Derfor skal vi nå la

void gen(int i)

være en rekursiv metode der gen(k) genererer alle mulige kombinasjoner av 1...n i segmentet p[k-1] til p[n-1] (dvs. den genererer fra det k'te tallet i sekvensen). Eksempelvis svarer gen(1) til gen1, gen(2) til gen2 osv. Merk at gen(n) må foreta selve utskriften. Programmer en slik rekursiv metode og test den ut for n=4.
2. I stedet for å generere alle sekvenser av lengde n skal vi i fortsettelsen generere alle permutasjoner av tallene 1 til n. (En permutasjon av 1,2,...,n er en "omordning" av 1,2,...,n. Eksempelvis er 321 en permutasjon av 123, mens 211 ikke er det.) Vi kan først benytte oss av løsningen til det forrige punkt ved at vi like før selve utskrivningen sjekker at p faktisk er en permutasjon av 1...n. Gjør dette, og test ved kjøring at programmet ditt er riktig.
3. Hva er kjøringstiden til programmet over? Kjør programmet for n=8. Går det fort?
4. Avskjæring: Det finnes n! permutasjoner av n elementer, og dette er et stort tall. Dog er antallet sekvenser totalt enda større (hvor stort?), slik at programmet over er enda mindre effektivt enn det kunne vært. Vi skal derfor gjøre en avskjæring ved at vi så tidlig som mulig "oppdager" at en påbegynt sekvens aldrig kan bli en permutasjon, og unngår å bygge videre på en slik løsning. Det er for eksempel ingen vits å bygge videre på en sekvens der det første og tredje tallet er det samme. Denne avskjæringen kan gjøres på flere måter. Før man bygger videre på en sekvens kan man se "bakover" på den hittil genererte sekvensen og oppdage håpløse tilfeller. Vi velger en litt annen variant, nemlig vi bruker en global array

boolean[] brukt=new boolean[n+1]

der brukt[k]==true hviss tallet k allerede er brukt i sekvensen under bygging. (Husk å "blanke ut" deler av denne arrayen når vi prøver et nytt tall!.) Glem brukt[0]. Bruk en slik global array til å foreta avskjæring slik at vi aldrig bygger videre på en påbegynt sekvens som ikke kan bli en lovlig permutasjon. (Ekstraoppgave: Hva er kjøringstiden til generering av alle permutasjoner av 1...n med dette programmet?) Test ved kjøring for n=8. Bruk UNIX-kommandoen /bin/time deresProgram og se på user-time.

Oppgave 3: Data Invarianter -- Rasjonale tall

Rasjonale tall, eller brøker, er slike tall som 1/2, 2/6, -3600/840. De består av to heltall: teller (det som er over brøkstreken) og nevner (det som er under). Det kreves at nevner er ulik 0, for eksempel 8/0 eller 0/0 er ikke rasjonale tall.

Brøker kan adderes 2/6 + 1/2 = 5/6, multipliseres 2/6*1/2=2/12, substraheres 2/6-1/2=-1/6 og divideres (2/6) / (1/2)= 4/6. For addisjon, subtraksjon, divisjon og multiplikasjon har vi at dersom Y=a/b og X=c/d, så er:

Y+X = (a*d+c*b)/b*d
Y-X = (a*d-c*b)/b*d
Y*X = (a*c)/(b*d)
Y/X = (a*d)/(b*c)

Oppgaven går ut på å lage to implementasjoner av et interface Rasjonal med to forskjellige data invarianter.

public interface Rasjonal {
    int teller(); int nevner();
    void add(Rasjonal x);
    void sub(Rasjonal x);
    void mul(Rasjonal x);
    void div(Rasjonal x);
    boolean eq(Rasjonal x);
    boolean lt(Rasjonal x);
}

1. Implementer interface Rasjonal med en klasse med to heltallsattributter nev, tel, tilsvarende nevner og teller, der hele data invarianter sier at nevner må være ulik 0 (nev!=0). Implementer også en metode boolean DI() som skal brukes inne i andre metoder for å verifisere at datainvarianten holder.
2. Lag nå en annen implementasjon med en sterkere datainvariant: nevner skal alltid være positiv (nev>0).

Diskuter forskjeller og evt. fordeler/ulemper med de to implementasjonene. Kan du komme på enda en annen datainvariant som kunne brukes?