----- 14/12/16 -----

> Oggi, al termine della lezione di programmazione, ha scritto la procedura "ufo";
> ho scritto una formula che per un certo numero naturale n restituisca lo stesso valore di (ufo n).
> Secondo lei la soluzione riportata nell'allegato PDF e' corretta?

-----

Non mi e' chiaro quale sia stato il ragionamento per arrivare a una formula del genere,
che e' piuttosto complicata, ma in effetti e' corretta.

Un possibile percorso per verificarla e' il seguente:

1. Innanzitutto, in base allo sviluppo binario,
n puo' essere rappresentato come somma dei termini  bi * 2^i
per i che varia nell'intervallo [0,k].
Detto altrimenti, bi e' il valore della cifra di peso 2^i nella rappresentazione binaria,
che puo' essere 0 oppure 1;
l'indice 0 corrisponde alla cifra meno significativa e l'indice k a quella piu' significativa
(e quindi quest'ultima vale sempre 1).

2. In relazione a questo sviluppo, la formula nell'allegato e' equivalente
alla somma dei termini  (2*bi - 1) * 2^i  sempre per i che varia nell'intervallo [0,k].
In questo caso  (2*bi - 1)  puo' valere -1 oppure +1,
e corrisponde al (-1) elevato a una certa potenza nella formula,
dove conta solo se il quoziente della divisione per 2^i e' pari o dispari;
ma dalla parita' del risultato del quoziente si determina proprio il valore della cifra binaria bi.
Inoltre, il valore della somma puo' essere anche espresso come  2*n - (2^(k+1) - 1) = 2*(n - 2^k) + 1 .

3. Si puo' infine osservare che il secondo sviluppo e' coerente con proprieta'
dei valori della funzione "ufo" in relazione alla rappresentazione binaria dell'argomento n,
proprieta' che puo' essere riletta alla luce della dimostrazione di correttezza della procedura
(vedi appunti relativi alle lezioni sulla correttezza dei programmi ricorsivi)...

----- * -----