Lösning till fiktiv tentamen i Tilda, 2D1320

1 Sortera kö (5p)

Bubbelsortera tills ingen ändring sker! Kan göras med köanrop:
REPEAT
  changed := FALSE;  (* Flagga som visar om någon ändring skett *)
  x := Queue.Get();  
  y := Queue.Get();  (* Första paret ut! *)
  REPEAT
    IF x.pnr<y.pnr THEN Queue.Put(x); x:=y;
    ELSE Queue.Put(y); changed:=TRUE END;
    y := Queue.Get();
  UNTIL y.pnr=999999999;
  Queue.Put(x); 
  Queue.Put(y):      (* Sista paret in! *)
UNTIL NOT changed;

2 Vattengissning (6p)

Använd en heap (trappa) med plats för tusen poster. Läs tusen poster från filen och sortera sämre gissning ovanpå bättre. Högst upp i trappan finns nu den sämsta av dessa tusen gissningar, och det är den man ska jämföra och eventuellt ersätta med nästa post på filen. Algoritmen kan skrivas:
REPEAT
  Läs Gissning från filen
  IF Gissning är bättre än trappa[1] THEN
     trappa[1]:=Gissning;
     DownHeap(1) END;   (* Sjysta till trappan *)
UNTIL filen slut

3 Nya personnummerlagen (8p)

Lämplig sorteringsmetod för en array är insättningssortering. Eftersom vektorn är nästan sorterad redan blir metoden mycket snabb.

Det finns nog inget smart sätt att utnyttja att det gamla binärträdet är nästan sorterat. Man får sortera in dom gamla posterna en efter en i det nya trädet, men man får inte gå igenom det gamla trädet i inordning (från vänster till höger), då blir det nya trädet katastrofalt obalanserat. Pre- eller postordning fungerar bra.

4 Fikonspråket (9p)

<fördel>::=<vokal>
<fördel>::=<konsonant><fördel>
<efterdel>::=
<efterdel>::=<bokstav><efterdel>
<ord>::=<fördel><efterdel>

Ett program som läser in en text enligt grammatiken och kompilerar den till fikonspråket kan se ut så här:

MODULE Main                                                             ;
IMPORT IO,Mio,Fmt                                                       ;
EXCEPTION Error                                                         ;
CONST vowels= SET OF CHAR{'a','e','i','o','u','y','å','ä','ö'}          ;
  delimiters= SET OF CHAR{' ','.',';','!','?',',',':','\n'}             ;

PROCEDURE ReadFirstPart():TEXT RAISES {Error}=
  BEGIN
    IF Mio.NextChar() IN vowels THEN RETURN Fmt.Char(IO.GetChar())      ;
    ELSIF Mio.NextChar() IN delimiters THEN RAISE Error                 ;
    ELSE RETURN Fmt.Char(IO.GetChar())&ReadFirstPart() END              ;
  END ReadFirstPart                                                     ;

PROCEDURE ReadSecondPart():TEXT =
  BEGIN
    IF Mio.NextChar() IN delimiters THEN RETURN ""                      ;
    ELSE RETURN Fmt.Char(IO.GetChar())&ReadSecondPart() END             ;
  END ReadSecondPart                                                    ;

PROCEDURE ReadWord():TEXT =
  VAR firstpart: TEXT                                                   ;
  BEGIN
    TRY
     firstpart:=ReadFirstPart()                                         ;
     RETURN "fi"&ReadSecondPart()&firstpart&"kon"                       ;
    EXCEPT | Error=> RETURN "***"                                       ;
    END                                                                 ;
  END ReadWord                                                          ;

PROCEDURE ReadText() RAISES {Error}=
  BEGIN
    IF Mio.NextChar() IN delimiters THEN Mio.PutChar(IO.GetChar())      ;
    ELSE IO.Put(ReadWord()) END                                         ;
    IF IO.EOF() THEN RETURN ELSE ReadText() END                         ;
  END ReadText                                                          ;

BEGIN
  IO.Put("Översättning till fikonspråket: ")                            ;
  ReadText()                                                            ;
END Main.

5 Abstrakta pengar (6p)

Datatypen ska kunna ha värden med tolv heltalssiffror och två decimaler. Viktiga procedurer är WriteMoney(x), ReadMoney(), AddMoney(x,y) osv. Den kan implementeras som en
TYPE Money = RECORD
              mille: INTEGER;
                ore: INTEGER;  (* högst åttasiffrigt *)
             END
och den typen kan ligga i Money.i3 medan procedurerna implementeras i Money.m3. Abstraktast blir det med en skum objekttyp
TYPE T<: AbstractMoney;
     AbstractMoney = OBJECT
                     METHODS
                       write();
                       read();
                       add(money:T):T;
                     END

6 Syntetisering (9p)

Databasen läses in i poster av typen NEW(Process) där
TYPE Process = REF RECORD
               substans1: TEXT;
               substans2: TEXT;
                  utbyte: REAL;
                    END;
och hashas med substans1 som söknyckel. Problemträdet byggs upp av typen
TYPE Position = REF RECORD
                  substans: TEXT;
                     massa: REAL;
                     fader: Position;
                    END;
och proceduren MakeSons(pos:Position söker pos.substans i hashvektorn och skapar alla söner (med massan utbyte*pos.massa). Sönerna läggs i en trappa (prioritetskö) där översta positionen har största massan och får föda söner först. Det blir alltså en bästa-först-genomgång av problemträdet.

Om flera positioner har samma substans är det bara den med största massan som är intressant, övriga är dumsöner och kan kasseras. För detta ändamål sparas rekordpositionerna i en annan hashvektor. Speciellt lägger man märke till rekordet för slutsubstansen - när översta posten i trappan har lägre massa än så är algoritmen klar och alla steg kan återskapas via rekordpositionens faderspekare etc.

7 Hashning av substanser (7p)

Hashvektorn bör gärna ha cirka femtio procent luft, så lämplig storlek kan vara primtalet 14999. Bra hashfunktion beräknas i en slinga med
h:=129*h+ORD(k-te tecknet i den kemiska formeln) MOD 14999.
Senast ändrad 17 dec. 1996 <henrik@nada.kth.se>