2005/06 – Fase scolastica – 05

Cosa stampa il seguente programma?

Program Test(Input, Output);
Type
   vett = Array[0..9] Of Integer;
Var
   i, f, a, b: Integer;
   arr       : vett;
 
Function funzione1(arr: vett): Integer;
Var
   i: Integer;
Begin
   i:=1;
   While(arr[i] <> -1) Do
      i:=i*2;
   funzione1:=i;
End;
 
Function funzione2(arr: vett; f: Integer; k: Integer): Integer;
Var
   i, m, temp: Integer;
Begin
   i:=0;
   m:=0;
   temp:=-1;
   While(i <= f) Do
      Begin
         m:=(i+f) Div 2;
         If(arr[m] = k) Then
            temp:=m;
         If((arr[m] = -1) Or (arr[m] > k)) Then
            f:=m-1
         Else
            i:=m+1;
      End;
   funzione2:= temp;
End;
    
Begin
   For i:=0 To 9 Do
      arr[i] := -1;
   arr[0]:=1;
   arr[1]:=2;
   arr[2]:=4;
   arr[3]:=8;
   f:=funzione1(arr);
   a:=funzione2(arr, f, 4);
   b:=funzione2(arr, f, 7);
   Writeln("a=", a, ",b=", b);
End.

Risposte:

1. a=2, b=4
2. a=2, b=-1
3. a=-1, b=4
4. a=-1, b=-1.

Soluzione: b.

Soluzione

Il programma principale chiama la funzione1 passando come unico parametro l’array arr.
All’ingresso della funzione avremo che la variabile i ad ogni ciclo while viene moltiplicata per 2, assumendo quindi i valori 2, 4, 8,…
Dal while si esce quando arr[i] vale -1, quindi quando i vale 4, che è il valore restituito.
Quindi ora f = 4.
Viene ora effettuata la chiamata: a:=funzione2 (arr, f, 4).
funzione2 riceve i parametri in arr, f, k, quindi avremo, al suo ingresso

arr = {1,2,4,8,-1,-1,-1,-1,-1,-1}
i = 0
f = 4
k = 4

la condizione di ingresso nel while (i<=f) è vera, quindi viene calcolato

m = (i+f)/2 = (0+4)/2 = 2

ora arr[m] = k è vera, quindi la funzione termina restituendo m, cioè 2.
Ora nel programma principale avremo:

a = 2
f = 4

Viene effettuata la chiamata: b:=funzione2 (arr, f, 7)
In funzione2:

i = 0
f = 4
k = 7

la condizione di ingresso nel while (i<=f) è vera, quindi viene calcolato:

m = (i+f)/2 = (0+4)/2 = 2

ora (arr[m] = k) e ((arr[m] = -1) or (arr[m] > k)) sono false, e viene calcolata i = m+1 = 3 quindi ora

i = 3
f = 4
k = 7
m = 2

(i<=f) è ancora vera, quindi viene calcolato:

m = (i+f)/2 = (3+4)/2 = 3 (essendo m un integer)
i = 3
f = 4
k = 7
m = 3

ora ((arr[m] = -1) or (arr[m] > k)) è vera, essendo vera arr[m] > k, quindi f = m-1 = 3-1 = 2

i = 3
f = 2
k = 7
m = 3

(i<=f) è diventata falsa, il ciclo while non viene più eseguito e si esce dalla funzione restituendo -1.

a = 2
b = -1

sono i valori delle variabili del programma principale che vengono visualizzati nell’ordine.