Problemi di interi

[nochipfritz]

E allora....vi sottopongo questo problema (per niente banale).

Dovrei costruire un algoritmo che preso in input $n$, calcoli floor($\log^2 n$).

Solo che io ho a disposizione una libreria di numeri interi.
Pertanto ho a disposizione :

1) le operazioni di somma, prodotto, divisione, sottrazione, elevamento a potenza, valore assoluto
2) inoltre ho a disposizione floor($\log n$).

Secondo voi con questi strumenti posso risolvere il problema?

[carlo232]

"nochipfritz":E allora....vi sottopongo questo problema (per niente banale).

Dovrei costruire un algoritmo che preso in input $n$, calcoli floor($\log^2 n$).

Solo che io ho a disposizione una libreria di numeri interi.
Pertanto ho a disposizione :

1) le operazioni di somma, prodotto, divisione, sottrazione, elevamento a potenza, valore assoluto
2) inoltre ho a disposizione floor($\log n$).

Secondo voi con questi strumenti posso risolvere il problema?

No, tu vuoi calcolare $[x^2]$ conoscendo solo $[x]$ ma ciò non è possibile poichè a uguali $[*]$ possono corrispondere diversi $[*^2]$, ad esempio $[3/2]=1$ e $[5/4]=1$ mentre $[(3/2)^2]=2$ e $[(5/4)^2]=1$.

[TomSawyer1]

Ma se puoi calcolare $[logn]$, perché non puoi calcolare $logn$? Comunque, al massimo puoi sapere l'intervallo in cui si trova $[log^2n]$, cioè tra $[logn]^2$ e $([logn]+1)^2$.

[nochipfritz]

Ho risolto il problema....avendo anche a disposizione una libreria che mi gestisce i numeri decimali, posso calcolarmi il risultato con approssimazione al millesimo con l'algoritmo seguente . L'algoritmo è in pseudocodice, ma adesso viene l'impresa più ardua...trasformarlo in java.

n= "numero su cui calcolare il floor((log n)*(log n))"

va = floor(log(n) / log(2)); //valore approssimato del logaritmo.

k = pow(2,va);

for(i=0; i<1000; i++)
{
k = k * 1.000693387;
if(k > n)
{
logn = va + i * 0.001;
break;
}

}

print floor(logn * logn);

[carlo232]

"nochipfritz":Ho risolto il problema....avendo anche a disposizione una libreria che mi gestisce i numeri decimali,

Ah, allora ovviamente tutto risolto