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 <stdio.h> 
 
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<x then xx::insert(ll,x) else x::l; 
 
   fun sorter(l:L):L  = case l of nil  => 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);