Si consideri la seguente funzione, che viene chiamata con n >= k >= 1.
|
1 2 3 4 5 6 7 |
Function f(n, k: Integer): Integer; Begin If(n = k) Or (k = 0) Then f:=1 Else f:=f(n-1, k-1)+f(n-1, k) End; |
Quale tra le seguenti espressioni viene calcolata dalla funzione f?
Si ricordi che 
e che n! è il fattoriale di n (cioè il prodotto dei numeri interi positivi da 1 a n, ovvero 1 × 2 × 3 × … × n).
È dato il seguente programma:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Program E11(input, output); Function g(x: Integer): Integer; forward; Function f(x: Integer): Integer; Begin If(x <= 0) Then f:=0 Else If(x mod 2)=0 Then f:= g(x Div 2) Else f:= g((x Div 2)+1) End; Function g(x: Integer): Integer; Begin If(x <= 0) Then g:=0 Else g:=1+f(x-2) End; Begin Write(f(100)) End. |
Cosa viene visualizzato a video dall’esecuzione del programma?
Siano A e B due insiemi di uguale cardinalità N (cioè con uguale numero di elementi) contenenti ciascuno N numeri interi diversi tra loro.
I numeri dei due insiemi A e B vengono memorizzati, ordinati per valori crescenti, nei due vettori v e w.
Si dica che insieme calcola nel vettore z il seguente codice:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
Var v, w : Array[1..N] of Integer; z : Array[1..2*N] of Integer; i, j, k: Integer; While(i <= N) And (j <= N) Do Begin If(v[i] = w[j]) Then Begin i:=i+1; j:=j+1 End Else If(v[i] < w[j]) Then Begin z[k]:=v[i]; k:=k+1; i:=i+1 End Else Begin z[k]:=w[j]; k:=k+1; j:=j+1 End; End; While(i <= N) Do Begin z[k]:=v[i]; k:=k+1; i:=i+1 End; While(j <= N) Do Begin z[k]:=w[j]; k:=k+1; j:=j+1 End; |
Si consideri la seguente funzione:
|
1 2 3 4 5 6 7 8 9 |
Function f(a, b: Integer): Integer; Begin If(a = b) Then f:=a Else If(a > b) Then f:=f(a-b, b) Else f:=f(a, b-a) End; |
Cosa restituisce la funzione se viene chiamata passandole due numeri a e b maggiori di zero?
È dato il seguente programma
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Program E8(Input, Output); Var i, j: integer; Function max(a, b: Integer): Integer; Begin If(a > b) Then max:=a Else max:=b End; Function f(a, b: Integer): Integer; Begin If(a = b) Then f:=b Else If(a < 0) Then f:=-b Else f:=max(f(a-1, 2*b), f(a-1, 2*b+1)) End; Begin Write(' ', f(8, 0)) End. |
Cosa viene visualizzato a video dall’esecuzione del programma?
È dato il seguente programma:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Program E7(Input, Output); Var f: Array[1..10] Of Integer; i: Integer; Begin f[1]:=5; f[2]:=3; For i:=1 To 8 Do f[i+2]:=f[i]-f[i+1]; For i:=1 To 10 Do Write(f[i], ', ') End. |
Cosa viene visualizzato a video dall’esecuzione del programma?
È dato il seguente programma:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Program E6 (input, output); Var i, c: Integer; Begin c:=0; i:=0; While(i < 100) Do Begin c:=c+1; If(c mod 2 <> 0) Then i:=i+1 Else i:=i+c; End; Writeln('c=', c); End. |
Cosa viene visualizzato a video dall’esecuzione del programma?
Si consideri la seguente funzione:
|
1 2 3 4 5 6 7 8 9 10 |
Function A(n: Integer; m: Integer): Integer; Begin If n = 0 Then A:=1 Else If n Mod 2 = 0 Then A:=A(n Div 2, m)*A(n Div 2, m) Else A:=m*A(n-1, m) End; |
Dire quale sarà il valore tornato dalle chiamate
Nella versione Pascal c’è un errore di trascrizione del testo proposto: return n*A(n-1, m) invece di m*A(n-1, m).
Pertanto la risposta corretta è 3, 1, 5.Considerando peraltro che qualcuno avrebbe potuto identificare l’errore (confrontando con la versione C, ad esempio), si possono ritenere valide sia la risposta 8, 81, 1024 che quella 3, 1, 5.
Si consideri la seguente funzione conta() che prende in input un vettore di numeri di lunghezza n (assumendo che n sia compreso fra 2 e 100):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Type sequenza = Array[1..100] Of Integer; Function conta(vett: sequenza; n: Integer): Integer; Var i, j, k: Integer; Begin i:=0; k:=0; j:=1; For i:=1 To n-1 Do If(vett[i] < vett[i+1]) Then j := j+1 Else Begin If(k < j) Then k:=j; j:=1; End; conta:=k End; |
Quale delle seguenti affermazioni è vera?
Risposte:
Se la sottosequenza più lunga non è l’ultima del vettore, allora la funzione ne restituisce la lunghezza (risposta c); se, invece, questa sottosequenza è l’ultima del vettore, il programma non ne conta correttamente la lunghezza (risposta d).
Si decide, dunque, di ritenere valida sia la risposta c che la d.
Si considerino le due seguenti funzioni:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Function A(n: Integer): Integer; Begin If n > 0 Then A:=n+A(n-1) Else A:=0 End; function B(n: integer): integer; begin B := (n*(n+1) div 2) end; |
Quale delle seguenti affermazioni è vera?
Risposte:
Soluzione: b.
Si tratta di riconoscere semplici algoritmi e formule di base; nel caso specifico della funzione A l’algoritmo ricorsivo che calcola la somma dei naturali da 1 ad n.
Nel caso della funzione B occorre riconoscere la formula di Gauss per lo stesso calcolo.