ESERCIZI CORSO LP (97/98)


ESERCIZIO n. 1

Data una relazione R contenuta in X× X, si dice che un insieme X' contenuto in X è una componente fortemente connessa sse
esiste x appartenente a X' t.c. per ogni y appartenente a X (y appartiene a X') sse ((x R* y) e (y R* x)), dove R* è la chiusura riflessiva e transitiva di R.

Si definiscano tipi PASCAL Relazione e Sottoinsieme per rappresentare le relazioni su X ed i sottoinsiemi di X, dove X è l' intervallo [1,n].

Si scriva quindi il corpo del sottoprogramma Check, che data una relazione R su X ed un sottoinsieme X' di X restituisce true sse X' è una componente fortemente connessa.

vuoi vedere la soluzione ?


ESERCIZIO n. 2

Si consideri la seguente funzione ricorsiva Elev per calcolare x elevato alla n, con x reale ed n intero.
function Elev(x: real; n: integer): real;
{calcola x alla n}
  begin
  Elev:= x*Elev(x,n-1)
  end; 
  1. Individuare l'errore e corregerlo, dando ancora una funzione ricorsiva;
  2. Riscrivere il corpo della funzione Elev senza usare la ricorsione.

vuoi vedere la soluzione ?


ESERCIZIO n. 3

Scrivere una procedura P che, dato un textfile f ed un intero positivo n, riscrive f uniformando la lunghezza delle linee di testo ad n.

Più precisamente, P tronca la parte finale delle linee con più di n caratteri, ed aggiunge spazi bianchi alla fine delle linee con meno di n caratteri. Esplicitare eventuali ipotesi che si fanno sul contenuto di f affinché il programma funzioni correttamente.

vuoi vedere la soluzione ?


ESERCIZIO n. 4

program PROG;
var  X, Y, N: integer;
 procedure Q (N: integer);
 forward;
 procedure P (N: integer);
 begin
  if N > 0 then
   if N mod 2 = 0 then
   begin
    X := X + 1;
    Q(N div 2)
   end
   else
    Q(N)
 end; {P}
 procedure Q (N: integer);
 begin
  if N > 0 then
   if N mod 2 <> 0 then
   begin
    Y := Y + 1;
    P(N div 2)
   end
   else
    P(N)
 end; {Q}
begin
 readln(N);
 X := 0;
 Y := 0;
 P(N);
 writeln(X);
 writeln(Y)
end.
  1. Dire che cosa stampa il programma PROG quando in input viene dato 5; analogamente con 8.
  2. Dare un programma equivalente (cioè che produca gli stessi output a partire dagli stessi input) che usa una sola procedura ricorsiva.
  3. Dare un programma equivalente (cio è che produca gli stessi output a partire dagli stessi input) senza usare procedure e funzioni.

vuoi vedere la soluzione ?


ESERCIZIO n. 5

Scrivere una procedura Cancella che, presi come parametri il nome di un textfile, sia esso EFFE, e di un file di interi positivi in ordine crescente (che identificano linee in EFFE), sia esso ELLE, rimuove da EFFE tutte le linee di testo indicate in ELLE.

vuoi vedere la soluzione ?


ESERCIZIO n. 6

Si rappresenti una operazione binaria op sul tipo finito T con una matrice Op, in modo che Op[x,y] sia il valore dell'operazione op su x e y, ed una matrice n × n a valori in T nel modo ovvio
const
  n = ...;
  primo = ...;
  ultimo = ...;
type
  T = primo..ultimo;
  OpBin = array [T,T] of T;
  Matrice = array [1..n,1..n] of T;
Si scrivano le seguenti procedure Pascal
function commutativa(Op: OpBin): boolean;
function associativa(Op: OpBin): boolean;
procedure prodotto(zero: T; sum,prod: OpBin; A,B: Matrice; var C: Matrice);
Le funzioni commutativa e associativa verificano se la operazione binaria Op gode delle rispettive proprietà, mentre la procedura prodotto assegna a C il valore di A*B dove l'operazione di somma e prodotto su T sono date dai parametri sum e prod e l'unità per la somma è data da zero.

vuoi vedere la soluzione ?


ESERCIZIO n. 7

Scrivere una procedura che, dato il nome di un file di reali (con almeno un elemento) restituisce minimo, massimo e media.

vuoi vedere la soluzione ?


ESERCIZIO n. 8

Assumendo che i numeri naturali "grandi", cioè molto maggiori degli interi supportati dagli usuali compilatori per il Pascal, siano rappresentati usando i tipi seguenti
type  CIFRE = 0..9;
      BNAT = record 
               NUM: array [1..5000] of CIFRE;
               PRIMA_C: 1..5000
             end
dove le cifre del numero sono negli elementi dell'array NUM dalla posizione PRIMA_C alla posizione 5000 (la cifra più significativa in PRIMA_C e quella meno significativa in 5000); per esempio una variabile N: BNAT contiene il valore 13 quando N.PRIMA_C contiene 4999, e N.NUM[4999], N.NUM[5000] contengono rispettivamente 1 e 3.

Dare il body delle seguenti procedure

procedure STAMPA(N: BNAT; var F: text);
{stampa N sul file F, mettendo al più 20 cifre su ogni riga}
...

procedure LEGGI(var N: BNAT);
{legge N dall'input standard leggendo prima il numero di cifre di N
e poi le sue cifre partendo dalla piu' significativa}
...

procedure SOMMA(N1, N2: BNAT;  var RIS: BNAT);
{ritorna in RIS la somma di N1 con N2}
...

procedure PER_CIFRA(N: BNAT; C: CIFRA; var RIS: BNAT);
{ritorna in RIS il prodotto di N per la cifra C}
...

procedure PER_DIECI_MULT(N: BNAT; D: integer;  var RIS: BNAT);
{ritorna in RIS il prodotto di N per 10 elevato a D, 
si assuma che   D sia sempre non negativo}
...

procedure PROD(N1, N2: BNAT;  var RIS: BNAT);
{ritorna in RIS il prodotto di N1 per N2}
...
Si ricorda che gli algoritmi per la somma ed i vari prodotti sono gli stessi che vengono usati per eseguire le operazioni sulla carta con la matita.

vuoi vedere la soluzione ?


ESERCIZIO n. 9

Gli insiemi finiti i cui elementi sono rappresentati da un tipo Pascal ELEM e la cui cardinalità è minore di 10000 sono rappresentati dal seguente tipo
INSIEME = record 
            ELEMENTI: array [1..10000] of ELEM;
            N_ELEMENT: 0..10000
          end;
Dare il body delle seguenti funzioni e procedure
function APPARTIENE(X: ELEM; S: INSIEME): boolean;
(* controlla se X appartiene ad S *)
...
end; (*APPARTIENE*)

function CONTENUTO(S1,S2: INSIEME): boolean;
(* controlla se S1 e' contenuto in S2 *)
...
end; (*CONTENUTO*)

procedure SINGLETON(X:ELEM; var S: INSIEME);
(* ritorna in S l'insieme il cui unico elemento e' X *)
...
end; (*SINGLETON*)

vuoi vedere la soluzione ?


ESERCIZIO n. 10

Scrivere una procedura che dato un textfile f e un intero n modifica f aggiungendo all'inizio di ogni riga il numero di linea seguito dal carattere ':' e aggiunge ogni n righe una riga che contiene solo il numero di linea. NOTA: supponendo che n=5 dopo la modifica f dovrà avere la seguente forma
1: linea 1
2: linea 2
3: linea 3
4: linea 4
5: linea 5
6
7: linea 6
...

vuoi vedere la soluzione ?


ESERCIZIO n. 11

Si rappresenti un vettore con un file di reali. Scrivere una funzione che dati due vettori a e b restituisce il loro prodotto scalare, se i due vettori hanno lo stesso numero di elementi, altrimenti deve restituire O.

vuoi vedere la soluzione ?


ESERCIZIO n. 12

Dare la sequenza dei numeri (in ordine di apparizione) stampati dal seguente programma. Giustificare la risposta.
program Traccia;
type T = record a,b: integer end; 
var  x: T;
procedure P;
begin
   writeln(x.a,x.b)
end; { P }
procedure Q(var y: T; var z: integer);
type T = record b,a: integer end;   
var  x: T;
begin
   x.a:=z;
   z:=z+1;
   P;
   y.b:=x.a+y.a;
end; { Q }
begin
   x.a:=0;
   x.b:=10;
   Q(x,x.a);
   P;
   Q(x,x.b);
   P
end.

vuoi vedere la soluzione ?


ESERCIZIO n. 13

program Scope;
type
(1) T1 = (a,b);
(2) T2 = record a,b: T1	end;
var x: T2;
procedure P(x: T2);
(3) type T1 = (c,b,a);
begin
   if x.a=x.b then writeln('x.a uguale a x.b');
   if x.a=b   then writeln('x.a uguale a b');
end; { P }
begin x.a:=b; x.b:=b; P(x) end.
  1. A quali dichiarazioni fanno riferimento gli identificatori a e b usati nelle due istruzioni della procedura P?
  2. Relativamente alle due istruzioni della procedura P dire se sono causa di errore in compilazione o esecuzione. (Spiegare l'errore, o se non vi sono errori dire cosa viene stampato dal programma Scope).

vuoi vedere la soluzione ?


ESERCIZIO n. 14

Dare il corpo dei seguenti sottoprogrammi PASCAL descritti informalmente dai commenti.
program B;
type  BINARY = record
                  NCIFRE: 1 .. 100;
                  BCIFRE: array [1..100] of '0'..'1'
               end;
{i valori di questo tipo corrispondono a rappresentazioni binarie di numeri naturali}
{di al piu' 100 cifre; si assuma che la cifra piu' significativa e' la prima}

function BIN-NUM(NB: BINARY): integer;
{data la rappresentazione binaria di un numero NB, ritorna il numero rappresentato}
.....

procedure NUM-BIN(N: integer; var NB: BINARY);
{dato un numero N ritorna in NB la sua rappresentazione binaria}
.....

vuoi vedere la soluzione ?


ESERCIZIO n. 15

  1. Qual'è il valore della funzione Ric data sotto per N=5 e N=7?
    function Ric(N: integer): integer;
    begin
      if N <= 0 then Ric := 0
      else if (N = 1) or (N = 2) then Ric := 1
      else Ric := Ric(N - 2) + Ric(N - 3);
    end;
    
  2. Scrivere una versione non ricorsiva della funzione Ric.

vuoi vedere la soluzione ?


ESERCIZIO n. 16

La seguente funzione ricorsiva Presente dovrebbe verificare se x=A[k] per qualche indice k tale che i<=k<=j. Tuttavia, essa contiene degli errori sia sintattici (cioè identificabili a tempo di compilazione) che logici (cioè identificabili solo testando il programma).
const  n = ...;
function Presente(var A: array [1..n] of real;
		          i,j: 1..n;
		          x: real): Boolean;
var  k: 1..n;
begin
   k:=(i+j) mod 2;
   if Presente(A,i,k,x) then Presente
   else if Presente(A,k,j,x) then Presente
   else not(Presente);
end; { Presente }
Individuare gli errori. Successivamente corregerli, continuando ad usare una funzione ricorsiva (con istruzioni strutturate if-then-else).

vuoi vedere la soluzione ?


ESERCIZIO n. 17

Dare la sequenza dei numeri (in ordine di apparizione) stampati dal seguente programma. Giustificare la risposta.
program Stampa;
var x: integer;
procedure P1;
  begin writeln(x) end;
procedure P2(var y: integer);
  var x: integer;
  procedure P3(var z: integer);
    begin z := y+1 end;
  begin
  x := 0; P1; P3(x); P1; P3(y); P1
  end; {P2}
begin
x := 0;
P2(x);
P1
end.

vuoi vedere la soluzione ?


ESERCIZIO n. 18

Dare la sequenza dei numeri (in ordine di apparizione) stampati dal seguente programma. Giustificare la risposta.
program Stampa;
var x: integer;
procedure P1(var x:integer);
  begin	x := x + 1 end;
procedure P2(x:integer);
  begin x := x+10; P1(x); writeln(x) end;
begin
  x := 0;
  P1(x);
  writeln(x);
  P2(x);
  writeln(x)
end.

vuoi vedere la soluzione ?


ESERCIZIO n. 19

Individuare gli errori presenti nella dichiarazione della funzione Member e correggerli continuando ad usare solo le istruzioni while e if.
program Errore;
const n = ...;
type vettore = array[1..n] of real;
...
function Member(var x: real; var V: vettore): boolean;
{ritorna false se x non compare in V altrimenti true}
  var i: integer;
  begin
  i := 1;
  while (V[i] <> x) and (i <= k) do i := i+1;
  if (V[i] = x)
    then Member := true
    else Member := false;
  end; {Member}
begin ... end.

vuoi vedere la soluzione ?


ESERCIZIO n. 20

Nel seguente programma un insieme finito S di interi è rappresentato mediante un file che contiene gli elementi di S in ordine crescente e senza ripetizioni. Si scriva il corpo delle procedure Present e Difference come descritto nei commenti.
program Esercizio;
type
  Elem = integer;
  Insieme = file of Elem;
...
function Present(x: Elem; var S: Insieme): Boolean;
{true se l'insieme S contiene l'elemento x}
  ...
 procedure Difference (var S1, S2,S: Insieme);
{ad S e' assegnato l'insieme S1 a cui sono stati tolti gli elementi in S2}
  ...
begin ... end.

vuoi vedere la soluzione ?


ESERCIZIO n. 21

Dare la sequenza dei numeri (in ordine di apparizione) stampati dal seguente programma. Giustificare la risposta.
program Stampa;
 const
  n = 2;
 type
  I = 1..n;
  A = array[I] of I;
 var
  a1, a2: A;
  i1: I;
 procedure Stampa (var a1: A);
  var
   i1: I;
 begin
  for i1 := 1 to n do
   write(a1[i1]);
  writeln
 end;
 procedure Init (var a1: A);
  var
   i1: I;
 begin
  for i1 := 1 to n do
   a1[i1] := i1
 end;
 procedure Op1 (var a1, a2: A; i1: I);
  var
   i2: I;
 begin
  a2[1] := a1[i1];
  for i2 := 2 to n do
   a2[i2] := a1[a2[i2 - 1]]
 end;
 procedure Op2 (var a1, a2: A);
  var
   i1: I;
 begin
  for i1 := 1 to n do
   a2[i1] := a2[a1[i1]];
 end;
begin
 Init(a1);
 Init(a2);
 Stampa(a1);
 Op1(a1, a1, 1);
 Stampa(a1);
 Op1(a2, a2, 2);
 Stampa(a2);
 Op2(a1, a2);
 Stampa(a2)
end.

vuoi vedere la soluzione ?


ESERCIZIO n. 22

L'insieme delle funzioni su X è dotato di una struttura di monoide non commutativo, dove g o f è la composizione funzionale (e l'indentità su X è l'elemento neutro).
Si introduca un tipo PASCAL per rappresentare tale insieme nella ipotesi che X sia finito. Si definiscano inoltre il corpo delle procedure di cui è data la intestazione.
program Endofunzioni;
const
  n=...; {cardinalita' di X}
type
  X=1..n;
  Fun=...;
...
procedure Moltiplicazione(f,g:Fun; var h:Fun);
  {h:=la composizione di f e g, cioe' h(x)=g(f(x))}
  ...
procedure Unita(var f:Fun);
  {f:=identita' su X}
  ...
function Invertibile(f:Fun): Boolean;
  {Invertibile(f) sse f è invertibile}
  ...
procedure Inversa(f:Fun; var g:Fun);
  {g:=l'inversa di f, se esiste}
  ...

vuoi vedere la soluzione ?


ESERCIZIO n. 23

Si considerino i seguenti programmi Pascal.
program ESEMPIO1;
 const
  N = 10;
 type
  VECTOR = array[1..N] of integer;
 var
  I: integer;
  A, B, C: VECTOR;
 procedure SX (A, B: VECTOR; var C: VECTOR);
  var
   J: integer;
 begin
  for J := 1 to N do
   if J mod 2 = 0 then
    C[J] := A[J]
   else
    C[J] := B[J]
 end; {SX}
 procedure PR (A: VECTOR);
  var
   H, I: integer;
 begin
  for H := 1 to N do
  begin
   if (H - 1) mod 2 = 0 then
    writeln;
   write(A[H]);
   write(' ');
  end;
 end; {PR}
begin
 for I := 1 to N do
  A[I] := I;
 for I := N downto 1 do
  B[I] := I;
 SX(A, B, C);
 PR(C);
 SX(B, A, C);
 PR(C)
end.

program ESEMPIO2;
 const
  N = 10;
 type
  VECTOR = array[1..N] of integer;
 var
  I: integer;
  A, B, C: VECTOR;
 procedure SX (A, B: VECTOR);
  var
   J: integer;
 begin
  for J := 1 to N do
   if J mod 2 = 0 then
    C[J] := A[J]
   else
    C[J] := B[J]
 end; {SX}
 procedure PR (A: VECTOR);
  var
   H: integer;
 begin
  for H := 1 to N do
  begin
   if (H - 1) mod 2 = 0 then
    writeln;
   write(A[H]);
   write(' ');
  end;
 end; {PR}
begin
 for I := 1 to N do
  A[I] := I;
 for I := N downto 1 do
  B[I] := I;
 SX(A, B);
 PR(C);
 SX(B, A);
 PR(C)
end.

program ESEMPIO3;
 const
  N = 10;
 type
  VECTOR = array[1..N] of integer;
 var
  I: integer;
  A, B, C: VECTOR;
 procedure SX (var A, B, C: VECTOR);
  var
   J: integer;
 begin
  for J := 1 to N do
   if J mod 2 = 0 then
    C[J] := A[J]
   else
    C[J] := B[J]
 end; {SX}
 procedure PR (var A: VECTOR);
  var
   H: integer;
 begin
  for H := 1 to N do
  begin
   if (H - 1) mod 2 = 0 then
    writeln;
   write(A[H]);
   write(' ');
  end;
 end;{PR}
begin
 for I := 1 to N do
  A[I] := I;
 for I := N downto 1 do
  B[I] := I;
 SX(A, B, C);
 PR(C);
 SX(B, A, C);
 PR(C)
end.
Dire quali tra ESEMPIO1, ESEMPIO2 ed ESEMPIO3 sono equivalenti, cioè producono gli stessi risultati dati gli stessi input.

vuoi vedere la soluzione ?


ESERCIZIO n. 24

Scrivere un programma Pascal che legge dall'input standard una stringa di 5 caratteri, e poi stampa sull'output standard le righe di un file di tipo testo di nome SCHEDARIO che contengono tale stringa. Si assuma che le righe di SCHEDARIO siano lunghe al più 180 caratteri e che non succeda mai che la stringa di cui sopra compaia a cavallo di due righe.

vuoi vedere la soluzione ?


ESERCIZIO n. 25

Assumendo che le matrici di reali N × M le cui dimensioni N e M sono minori od uguali di 1000 siano rappresentate usando dai seguenti tipi
 const
  DIM = 1000;
 type
  INDICI = 1..DIM;
  V_MATRICI = record
    N, M: INDICI;
    MAT: array[INDICI, INDICI] of integer
   end;
Dare il body delle seguenti procedure e funzioni
 procedure RIDOTTO (VM: V_MATRICI; I, J: INDICI; var RID: V_MATRICI);
{ritorna in RID il ridotto di VM rispetto alla riga I ed alla colonna J,}
{se I e J sono una riga ed una colonna di VM, altrimenti stampa un messaggio}
{di errore sull'output standard}
...

function DET (VM: V_MATRICI): integer;
{calcola il determinante di VM}
...

procedure PRODOTTO (VM1, VM2: V_MATRICI; var VM: V_MATRICI);
{ritorna in VM il prodotto  di VM1 con VM2, se le dimensioni}
{sono corrette, altrimenti stampa un messaggio di errore  sull'output standard}
...
Si ricorda che il ridotto di una matrice A di dimensioni N, M rispetto ad I, J, è la matrice di dimensioni N-1, M-1 ottenuta eliminando da A la riga I e la colonna J.

vuoi vedere la soluzione ?


ESERCIZIO n. 26

Si consideri il seguente programma.
program ES3;
type PAROLA = array[1..10] of integer;
var  F, G: file of PAROLA;
     X: integer; A, B: PAROLA;

function SUM (A: PAROLA): integer;
var I, X: integer;
begin for I := 1 to 10 do X := X + A[I] end;

begin
 X := 0;
 open(F, 'FF'); open(G, 'GG');
 while not eof(F) do
 begin
  read(F, A);
  read(F, A);
  if SUM(A) >= 0 then write(G, A)
 end;
 close(F); close(G);

 open(F, 'FF '); open(G, 'GG');
 while not eof(G) do
 begin
  read(G, B);
  if SUM(B) >= 0 then write(F, B)
 end;
 close(F); close(G);
end.
  1. È corretto il programma dato sopra, cioè verrà eseguito senza problemi in ogni caso ? Se no corregerlo.
  2. Dare un programma equivalente a ES3, se fosse errato considerare quello corretto, che non usa procedure o funzioni.
  3. Dare un programma equivalente a ES3, se fosse errato considerare quello corretto, usando una procedura SUMP al posto della funzione SUM.

vuoi vedere la soluzione ?