Tentamen i Programmering för naturvetare, del 2, 950529


  1. Betrakta följande programavsnitt:
           PROCEDURE dubbla(n:INTEGER);
           BEGIN
           n:=2*n
           END dubbla;
           
           VAR x,i:INTEGER;
           
           BEGIN
           x:=1;
           FOR i:=1 TO 5 DO dubbla(x); WriteInt(x,3) END;
           ...
           END
           
    Meningen var att programmet skulle skriva ut talen 2 4 8 16 32, men det har visst blivit något fel på proceduren dubbla.

  2. Notera: procedurerna behöver inte sätta Done rätt.

  3. Skriv ett program som läser in en text från terminalen och räknar hur många gånger varje bokstav förekommer i texten. Stora och små bokstäver räknas som lika. Andra tecken struntar man i. Texten avslutas med filslut. Resultatet ska presenteras med ett histogram där varje bokstav som förekommer minst en gång visas som en stapel av *:or (en *:a för varje förekomst av bokstaven).

    Exempel: om man matar in texten Abra Kadabra ska programmet skriva ut

           A *****
           B **
           D *
           K *
           R **
           
    (10 poäng)

  4. Denna uppgift går ut på att göra ett program som läser in en text och räknar hur vanliga olika ord är. Ett naturligt sätt att göra detta är att använda en datatyp för påsar (eng. bag, multiset). En påse är som en mängd, förutom att antalet förekomster av ett värde har betydelse i påsar.

Biblioteksmoduler

DEFINITION MODULE InOut;

   PROCEDURE Read (VAR x : CHAR);
   (* Read the next character from std input into 'x' *)

   PROCEDURE ReadString (VAR x : ARRAY OF CHAR);
   (* Read the next string from std input into 'x'. *)
   (* Leading blanks are ignored.                   *)
   (* Input is terminated by any character <= ' '   *)

   PROCEDURE ReadCard (VAR x : CARDINAL);
   (* Read the next string from std input and *)
   (* convert it to cardinal 'x'.             *)
   (* Syntax : digit {digit}                  *)

   PROCEDURE ReadInt (VAR x : INTEGER);
   (* Read the next string from std input and *)
   (* convert it to integer 'x'.              *)
   (* Syntax : ['+'|'-'] digit {digit}        *)

   PROCEDURE ReadReal (VAR x : REAL);
   (* Read the next string from std input and convert it   *)
   (* to real 'x'.                                         *)
   (* Syntax : ['+'|'-'] digit {digit} ['.' digit {digit}] *)
   (*          ['E'['+'|'-'] digit {digit}]                *)

   PROCEDURE Write (x : CHAR);
   (* Write character 'x' onto std output *)

   PROCEDURE WriteString (x : ARRAY OF CHAR);
   (* Write the string 'x' onto std output *)

   PROCEDURE WriteCard (x : CARDINAL; n : CARDINAL);
   (* Convert the cardinal 'x' into decimal representation and *)
   (* write it onto std output. Field width is at least 'n'.   *)

   PROCEDURE WriteInt (x : INTEGER; n : CARDINAL);
   (* Convert the integer 'x' into decimal representation and *)
   (* write it onto std output. Field width is at least 'n'.  *)

   PROCEDURE WriteReal (x : REAL; n : CARDINAL; k : INTEGER);
   (* Convert the real 'x' into external representation and  *)
   (* write it onto std output. Field width is at least 'n'. *)
   (* If k > 0 use k decimal places.                         *)
   (* If k = 0 write x as integer.                           *)
   (* If k < 0 use scientific notation.                      *)
 
   PROCEDURE WriteLn;
   (* Write the end of line character onto std output *)
   (* Emit buffer contents immediately                *)
 
   PROCEDURE WriteBf;
   (* Emit buffer contents immediately *)

   PROCEDURE Done () : BOOLEAN;
   (* last operation ok *)

   PROCEDURE EOF () : BOOLEAN;
   (* EOF at standard input *)

END InOut.

DEFINITION MODULE MathLib;
  
   PROCEDURE sqrt (x : REAL) : REAL;
      (* calculates the square root of 'x' *)
   
   PROCEDURE sqrtL (x : LONGREAL) : LONGREAL;
      (* calculates the square root of 'x' *)
   
   PROCEDURE exp (x : REAL) : REAL;
      (* calculates 'e' to the power of 'x', 'e' Euler's number *)

   PROCEDURE expL (x : LONGREAL) : LONGREAL;
      (* calculates 'e' to the power of 'x', 'e' Euler's number *)

   PROCEDURE ln (x : REAL) : REAL;
      (* calculates natural logarithm of 'x' *)

   PROCEDURE lnL (x : LONGREAL) : LONGREAL;
      (* calculates natural logarithm of 'x' *)

   PROCEDURE sin (x : REAL) : REAL;
      (* calculates sine of 'x' *)

   PROCEDURE sinL (x : LONGREAL) : LONGREAL;
      (* calculates sine of 'x' *)

   PROCEDURE cos (x : REAL) : REAL;
      (* calculates cosine of 'x' *)

   PROCEDURE cosL (x : LONGREAL) : LONGREAL;
      (* calculates cosine of 'x' *)
  
   PROCEDURE arctan (x : REAL) : REAL;
      (* calculates arc tangent of 'x' *)

   PROCEDURE arctanL (x : LONGREAL) : LONGREAL;
      (* calculates arc tangent of 'x' *)

   PROCEDURE real (x : INTEGER) : REAL;
      (* converts 'x' to type 'REAL' *)

   PROCEDURE realL (x : INTEGER) : LONGREAL;
      (* converts 'x' to type 'LONGREAL' *)

   PROCEDURE entier (x : REAL) : INTEGER;
      (* calculates the largest integer <= 'x' *)

   PROCEDURE entierL (x : LONGREAL) : INTEGER;
      (* calculates the largest long integer <= 'x' *)
  
END MathLib.

DEFINITION MODULE Storage;
(******************************************************************************)
(* Copyright (c) 1988 by GMD Karlruhe, Germany				      *)
(* Gesellschaft fuer Mathematik und Datenverarbeitung			      *)
(* (German National Research Center for Computer Science)		      *)
(* Forschungsstelle fuer Programmstrukturen an Universitaet Karlsruhe	      *)
(* All rights reserved.							      *)
(* Don't modify this file under any circumstances			      *)
(******************************************************************************)

   FROM SYSTEM IMPORT ADDRESS;

   PROCEDURE ALLOCATE (VAR a : ADDRESS; size : CARDINAL);
      (* Allocates an area of the given size 'size' and returns it's *) 
      (* address in 'a'. If no space is available, 'a' becomes 'NIL'. *)

   PROCEDURE DEALLOCATE (VAR a : ADDRESS; size : CARDINAL);
      (* Frees the area of size 'size' starting at address 'a'. *)
      (* Upon return 'a' is set 'NIL' *)

END Storage.

DEFINITION MODULE String;
(******************************************************************************)
(* Copyright (c) 1988 by GMD Karlruhe, Germany				      *)
(* Gesellschaft fuer Mathematik und Datenverarbeitung			      *)
(* (German National Research Center for Computer Science)		      *)
(* Forschungsstelle fuer Programmstrukturen an Universitaet Karlsruhe	      *)
(* All rights reserved.							      *)
(* Don't modify this file under any circumstances			      *)
(******************************************************************************)

   TYPE String = ARRAY [0..255] OF CHAR;

   PROCEDURE EmptyString (VAR str: ARRAY OF CHAR);
      (* str := "" *)

   PROCEDURE Assign (VAR dst, src: ARRAY OF CHAR);
      (* assign string 'src' to string 'dst'. 'src' must be terminated by 0C *)

   PROCEDURE Append (VAR dest, suffix: ARRAY OF CHAR);
      (* append 'suffix' to 'dest', only significant characters. *)

   PROCEDURE StrEq (VAR x, y: ARRAY OF CHAR): BOOLEAN;
      (* x = y , only significant characters. *)

   PROCEDURE Length (VAR str : ARRAY OF CHAR) : CARDINAL;
      (* returns the number of significant characters. *)

   PROCEDURE Insert
      (substr: ARRAY OF CHAR; VAR str: ARRAY OF CHAR; inx: CARDINAL);
      (* Inserts 'substr' into 'str', starting at str[inx] *)

   PROCEDURE Delete (VAR str: ARRAY OF CHAR; inx, len: CARDINAL);
      (* Deletes 'len' characters from 'str', starting at str[inx] *)

   PROCEDURE pos (substr: ARRAY OF CHAR; str: ARRAY OF CHAR): CARDINAL;
      (* Returns the index of the first occurrence of 'substr' in 'str' or *)
      (* HIGH (str) + 1 if 'substr' not found. *)

   PROCEDURE Copy
      (str: ARRAY OF CHAR; inx, len: CARDINAL; VAR result: ARRAY OF CHAR);
      (* Copies 'len' characters from 'str' into 'result', *)
      (* starting at str[inx] *)

   PROCEDURE Concat
      (s1, s2: ARRAY OF CHAR; VAR result: ARRAY OF CHAR);
      (* Returns in 'result' the concatenation of 's1' and 's2' *)

   PROCEDURE compare (s1, s2: ARRAY OF CHAR): INTEGER;
      (* Compares 's1' with 's2' and returns -1 if s1 < s2, 0 if s1 = s2, *)
      (* or 1 if s1 > s2 *)

   PROCEDURE CAPS (VAR str: ARRAY OF CHAR);
      (* CAP for the entire 'str' *)

END Strings.