2006/07 – Fase scolastica – 07

Cosa stampa il seguente programma?

Program cosa(Input, Output);
Function mistero(m : Integer; n: Integer): Integer;
Begin
   If(m = 0) Then
      mistero:=n
   Else if(n = 0) Then
      mistero:=mistero(m-1, 1)
   Else
      mistero:=mistero(n-1, mistero(m-1, n-1))
End;
Begin
   Writeln(mistero(0, 3), ' ', mistero(1, 3), ' ', mistero(2, 3), ' ', mistero(3, 3));
End.

Risposte:

1. 3 1 2 0
2. 3 1 1 0
3. 3 1 0 1
4. nessuna delle precedenti.

Soluzione: c.

Soluzione

La difficoltà consiste nel fatto che per valori di ingresso di m ed n diversi da 0 viene richiamata la funzione per calcolare il secondo parametro.
Nella stessa chiamata viene inoltre passato come primo paramento il valore di n-1 invece di m-1.
Bisogna quindi tenerne accuratamente conto nell’eseguire lo sviluppo del calcolo.

Vediamo, a titolo di esempio, il calcolo di mistero(1, 3).

Osserviamo preliminarmente che:

mistero(0, x) = x

(calcolo diretto, come base della ricorsione) e che

mistero(x, 0) = mistero(x-1, 1)

Calcoliamo dunque mistero(1, 3):

mistero(1, 3)
mistero(2, mistero(0, 2))
mistero(2, 2)
mistero(1, mistero(1, 1))
mistero(1, mistero(0, 0))
mistero(1, 0)
mistero(0, 1)
1