Fetite
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.
