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.
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;
Elev
senza usare la ricorsione.
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.
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.
PROG
quando in input
viene dato 5; analogamente con 8.
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
.
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
.
type CIFRE = 0..9; BNAT = record NUM: array [1..5000] of CIFRE; PRIMA_C: 1..5000 enddove 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.
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*)
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 ...
a
e b
restituisce il loro prodotto scalare,
se i due vettori hanno lo stesso numero di
elementi, altrimenti deve restituire O
.
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.
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.
a
e
b
usati nelle due istruzioni della procedura P
?
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
).
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} .....
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;
Ric
.
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).
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.
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.
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.
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.
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.
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} ...
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.
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.
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.
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.
ES3
,
se fosse errato considerare quello corretto, che non usa procedure o funzioni.
ES3
,
se fosse errato considerare quello corretto, usando una procedura SUMP
al posto
della funzione SUM
.