Si consideri la seguente funzione:
int f(int n) { int i=1; while(n > 0) { n -= i; i += 2; } if(n == 0) return 1; else return 0; }Cosa restituisce la funzione se viene chiamata passandole un numero n maggiore o uguale a zero?
- 1 se n è primo, 0 altrimenti
- 1 se n è dispari, 0 altrimenti
- 1 se n è un quadrato perfetto, 0 altrimenti
- 1 se n è una potenza di due, 0 altrimenti
Soluzione: 3 (1 se n è un quadrato perfetto, 0 altrimenti)
Osserva i risultati delle chiamate
- f(0): 0 –> 1
- f(1): 1-1 = 0 –> 1
- f(2): 2-1-3 = -2
- f(3): 3-1-3 = -1
- f(4): 4-1-3 = 0 –> 1
- f(5): 5-1-3-5 = -4
- f(6): 6-1-3-5 = -3
- f(7): 7-1-3-5 = -2
- f(8): 8-1-3-5 = -1
- f(9): 9-1-3-5 = 0 –> 1
- …
- f(16): 16-1-3-5-7 = 0 –> 1
- …
Si basa sulla proprietà che il quadrato di n è dato dalla somma dei primi n dispari.