INF3110/4110
L�sningsforslag uke 36 (3.-5.9.2003)
Oppgave 1 (Oppgave 1.3 fra l�reboka)
---------
Et mulig eksempel ser slik ut:
#include
int y;
int fun(int i) {
y++;
return i;
}
int main(void) {
int x, z;
z = 3;
y = 2;
x = fun(y) + z + fun(y); /* Opprinnelig setning */
printf("%d\n",x);
y = 2;
x = 2*fun(y)+z; /* Fors�k p� optimalisering */
printf("%d\n",x);
}
Den f�rste print-setningen vil skrive ut 8, mens den andre vil skrive
ut 7.
En slik optimalisering kan heller ikke gj�res i Java. C-programmet
over kan oversettes til:
class Test{
static int y;
public static void main(String[] args) {
int x, z;
z = 3;
y = 2;
x = fun(y) + z + fun(y);
System.out.println(x);
y = 2;
x = 2*fun(y) + z;
System.out.println(x);
}
static int fun(int i) {
y++;
return i;
}
}
Ogs� her vil print-setningene skrive ut henholdsvis 8 og 7.
Oppgave 3
---------
Alt unntatt levetiden til klasseobjektene er statisk kjent.
N�r det gjelder pekere, har vi at typen til _pekerne_ er bestemt
statisk, mens typen til _objektene_ som pekerne peker p�, ikke kan
bestemmes f�r programmet kj�rer.
Levetiden til objektvariable samsvarer med levetiden til objektene
disse befinner seg i.
Oppgave 4
---------
Fra deklarasjonen Hele blokken
Ytre Indre Ytre Indre
x y x y x y x y
BEGIN | |
VAR x, y; | | | |
| | | |
PROCEDURE P; | | | |
BEGIN | | | |
PROCEDURE Q; | | | |
BEGIN | | | |
VAR y; | | | |
| | | |
PRINT x; | | | |
END Q; | | | |
| | | |
VAR x; | | | |
| | | |
x := 2; y := 3; | | | |
CALL Q; | | | |
END P; | | | |
| | | |
x := 1; | | | |
CALL P; | | | |
END
Her ser vi at det blir skrevet ut 1 n�r deklarasjonens skop starter
ved deklarasjonsstedet, og 2 n�r skopet er hele blokken. Hvis x hadde
v�rt dynamisk bundet hadde det blitt skrevet ut 2.
Oppgave 5
---------
Et lite eksempel:
BEGIN
VAR x;
x := 1;
BEGIN
PROCEDURE P;
BEGIN
PRINT x;
END;
VAR x;
x := 2;
BEGIN
VAR x;
x := 3;
CALL P;
END;
END;
END;
Oppgave 6
---------
1. fun flatut(l:LL):L = case l of nil => nil
| x::l => x@flatut(l);
2. fun sum(l:L):int = case l of nil => 0
| x::l => x+sum(l);
fun summer(l:LL):L = case l of nil => nil
| x::l => sum(x)::summer(l);
3. fun sumall(l:LL):int = sum(summer(l));
4. fun snu(l:L):L = case l of nil => nil
| x::l => snu(l)@[x];
fun speil(l:LL):LL = case l of nil => nil
| x::l => speil(l)@[snu(x)];
5. fun insert(l:L,x:int):L =
case l of nil => [x]
| xx::ll => if xx nil
| x::l => insert(sorter(l),x);
6. fun sorterindre(l:LL):LL =
case l of nil => nil
| x::l => sorter(x)::sorterindre(l);
En annen m�te � gj�re det samme p� er:
1. fun flatut(nil:LL):L = nil
| flatut((x::l):LL):L = x@flatut(l);
2. fun sum(nil:L):int = 0
| sum((x::l):L):int = x+sum(l);
... etc. (P� samme m�te for de andre oppgavene.)
Oppgave 7
---------
fun settInnSist(x,l) = case l of [] => [x]
| y :: r => y :: settInnSist(x,r);
En kanskje enklere l�sning er:
fun settInnSist(x,l) = l @ [x];
Jobben som m� gj�res blir essensielt den samme, men dette skjules n� av
operatoren @ (pr�v � implementere denne!).
Oppgave 8
---------
exception Empty;
fun last(l) = case l of [] => raise Empty
| x :: r => case r of [] => x
| x' :: r' => last(r);
Oppgave 9
---------
fun plukk(n,l) = case l of [] => []
| x :: r => if n = 0 then []
else x :: plukk(n-1,r);
Det er vilk�rlig om man velger � teste p� l eller n f�rst. Her er det
valgt � sjekke l f�rst, mens det i neste oppgave testes p� n
f�rst. (Dette er tilfeldig valgt.)
Oppgave 10
----------
fun fjern(n,l) = if n = 0 then l
else case l of [] => []
| x :: r => fjern(n-1,r);