È dato il seguente programma:
#includeint max(int a, int b) { if(a > b) return a; return b; } int f(int a, int b) { if(a == b) return b; if(a < 0) return -b; return max(f(a-1,2*b), f(a-1,2*b+1)); } void main() { printf("%d ", f(8,0)); } Cosa viene visualizzato a video dall'esecuzione di main()?
Soluzione: 5
Osserva
- tra i risultati di diverse chiamate viene restituito il valore massimo
- se a == b restituisce b
- se a < 0 restituisce un valore negativo
- se a < b, f(a,b) = f(a-1,2*b),f(a-1,2*b+1) = ... a diminuisce, b cresce e restituirà un valore negativo
Quindi
- f(1,0) = f(0,0),f(0,1) = 0,f(-1,2),f(-1,3) = 0,-2,-3 = 0
- f(2,0) = f(1,0),f(1,1) = 0,1 = 1
- f(3,0) = f(2,0),f(2,1) = 1,f(1,2),f(1,3) = 1,...,... = 1
- f(4,0) = f(3,0),f(3,1) = 2,f(2,2),f(2,3) = 2,2,... = 2
- f(5,0) = f(4,0),f(4,1) = 2,f(3,2),f(3,3) = 2,f(2,4),f(2,5),3 = 2,...,3 = 3
- f(6,0) = f(5,0),f(5,1) = 3,f(4,2),f(4,3) = 3,f(3,4),f(3,5),f(3,6),f(3,7) = 3,...,...,...,... = 3
- f(7,0) = f(6,0),f(6,1) = 3,f(5,2),f(5,3) ) = 3,f(4,4)f(4,5),f(4,6),f(4,7) = 3,4,...,...,... = 4
- f(8,0) = f(7,0),f(7,1) = 4,f(6,2),f(6,3) = 4,f(5,4),f(5,5),f(5,6),f(5,7) = 4,f(4,8),f(4,9),5,...,... = 4,...,...,5....,... = 5