Nu exista diferente intre titluri.
Diferente intre continut:
O prima varianta ar fi cautarea binara a radacinii, prin injumatatirea intervalului. Initial se porneste cu intervalul ({$1$},{$A$}), deoarece radacina cubica se afla undeva intre $1$ si $A$ (evident, incadrarea este mai mult decat acoperitoare; ea ar putea fi mai limitativa, dar nu ar reduce timpul de lucru decat cu cateva iteratii). La fiecare pas, intervalul va fi injumatatit. Cum, probabil ca stiti deja; se ia jumatatea intervalului, se ridica la puterea a treia si se compara cu $A$. Daca este mai mare, inseamna ca radacina trebuie cautata in jumatatea inferioara a intervalului. Daca este mai mica, vom continua cautarea in jumatatea superioara a intervalului. Daca cele doua numere sunt egale, inseamna ca am gasit tocmai ce ne interesa. Prima varianta a pseudocodului este:
[ce fac cu secventa de cod in pseudocod???]
== code(c)|
citeste A cu N cifre
Lo <- 1, Hi <- A, X <- 0
cat timp X=0
Mid <- (Lo+Hi)/2
daca Mid^3<A
atunci Lo <- Mid+1
altfel daca Mid^3>A
atunci Hi <- Mid-1
altfel X <- Mid
==
In cazul cel mai rau, algoritmul de mai sus efectueaza $log ~2~ A$ injumatatiri de interval, fiecare din ele presupunand o adunare, o impartire la $2$ si o ridicare la cub. Dintre aceste operatii, cea mai costisitoare este ridicarea la cub, O( $N$^{$2$}^ ). Complexitatea totala este prin urmare O( $N$^{$2$}^ $log ~2~ A$ ). Deoarece $A$ are ordinul de marime $10$^{$N$}^, rezulta complexitatea O( $N$^{$3$}^ $log 10$ )= O( $N$^{$3$}^ ), adica mai proasta decat cea ceruta (de altfel, un algoritm cu aceasta complexitate nici nu s-ar incadra in timp pentru $N$={$1000$}). Daca timpul ne permite, trebuie sa cautam alta metoda.
Procedeul general este urmatorul: dandu-se un numar $A$ cu $N$ cifre, il completam cu zerouri nesemnificative pana cand $N$ se divide cu $3$ (poate fi necesar sa adaugam maxim doua zerouri). Numarul de cifre semnificative ale radacinii cubice este $M$={$N$}/{$3$}. Aflam pe rand fiecare cifra, incepand cu cea mai semnificativa. Sa presupunem ca am aflat cifrele $X$ ~$M$~, $X$ ~$M-1$~,..., $X$ ~$K+1$~. Cifra $X$~$K$~ este cea mai mare cifra pentru care numarul <tex> \overline{(X_MX_{M-1}...X_{K+1}X_K00...00)}^3\leq A</tex>. Cifra $X$~$K$~ este unica, deoarece exista, in general, mai multe cifre care verifica proprietatea ceruta, dar una singura este "cea mai mare". O a doua versiune a pseudocodului este deci:
[cod in pseudocod]
== code(c)|
citeste A cu N cifre
X <- 0; T <- 0
cat timp N%3<>0 adauga un 0 nesemnificativ
repeta de N/3 ori
adauga la T urmatoarele 3 cifre din A
adauga la X cea mai mare cifra astfel incat X^3<= T
==
Sa evaluam complexitatea acestei versiuni. Linia $1$ se executa in timp liniar, O({$N$}). Liniile $2$ si $3$ se executa in timp constant. Linia $5$ se executa in O({$N$}), iar linia $6$ presupune adaugarea unei cifre (O({$N$})) si o ridicare la cub, adica doua inmultiri (O({$N$}^{$2$}^)). Deoarece liniile $5$ si $6$ se executa de $N$/{$3$} ori (linia $4$), rezulta o complexitate de O({$N$}^{$3$}^). Iata ca nici acest algoritm nu a adus imbunatatiri si pare si ceva mai greu de implementat. El poate fi totusi modificat pentru a-i scadea complexitatea la O({$N$}^{$2$}^).
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.