meny2.html – INF3110 - H?st 2003 – Universitetet i Oslo_澳门葡京手机版app下载

Ukeoppgaver i INF3110


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);