Diferente pentru algoritmiada-2009/runda-3/solutii/fetite intre reviziile #4 si #3

Nu exista diferente intre titluri.

Diferente intre continut:

* $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.
Complexitatea acestui algoritm este O(log N).

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.