h1(#fetite). 'Fetite':problema/fetite

h2. Verificati sa fie pagina private pana dupa terminarea concursului

Vom rezolva problema recursiv. Fie $f(N)$ numarul de ordine al ultimei petale ramase in cazul in care avem la inceput o floare cu $N$ petale. Se disting $2$ cazuri:
 
* $N$ este un numar par. Vor fi eliminate toate petalele pare si ne vom intoarce la petala $1$. Putem considera ca am redus jocul la $N/2$ petale, singurul lucru de care trebuie sa avem grija este renumerotarea petalelor. Deducem ca $f(N) = 2 * f(N/2) - 1$.
* $N$ este un numar impar. Vor fi eliminate toate petalele pare si apoi vom elimina petala numarul $1$. Vom ajunge la petala $3$, si observam ca am redus din nou jocul la $N/2$ petale. Din renumerotare rezulta $f(N) = 2 * f(N/2) + 1$.
 
Complexitatea acestui algoritm este O(log N).
 
*O alta metoda de rezolvare* a acestei probleme se bazeaza pe urmatoarea observatie: Oricare ar fi N ( putere a lui 2 ), ultima petala ce va ramane va fi 1.
Daca se iau mai multe cazuri, se observa faptul ca din momentul acela pentru: $f(N+1) = f(N) + 2$, pana la urmatoarea putere a lui 2.
 
Exemplu: $f(8) = 1$ , $f(8) = 3$ ... $f(14) = 13$, $f(15) = 15$, $f(16) = 1$ ... iar algoritmul se reia.
 
Se determina P: cea mai mare putere a lui 2, mai mica sau egala decat N. Rezultatul se gaseste in: (N - P) * 2 + 1. Complexitatea este aceeasi.

private

public