Problema

[Vman]

Salut, am nevoie de o rezolvare urgent la problema asta:

Sqrt

Se da un numar X si un numar K. Se cere sa se afiseze primele K zecimale ale numarului sqrt(X).

Date de intrare

Fi?ierul de intrare sqrt.in va contine doua numere X si K.

Date de ie?ire

Fi?ierul de ie?ire sqrt.out va contine un sir format din K cifre reprezentand primele K zecimale ale numarului sqrt(X).

Restric?ii

1 ? X ? 6666

1 ? K ? 1000

sqrt(X) reprezinta radical de ordinul 2 din X

Pentru 10% din teste K ? 10

Pentru alte 10% din teste K ? 20

Pentru alte 40% din teste K ? 100

Sunt nou in programare si ma gandeam ca prima observatie este aceea ca daca inmultim numarul nostru X cu 100 si extragem radicalul din el, atunci partea intreaga din acest radical va avea ultima cifra egala cu prima zecimala a numarului sqrt(X). Un exemplu: sqrt(2) = 1.41... iar sqrt(200) = 14.1...... Putem generaliza si zicem ca daca inmultim numarul nostru cu 10^(2*K), atunci partea intraga din radicalul acestui numar va contine ultimile K cifre ca fiind primele K zecimale cautate.?Din moment ce precizia nu ne permite sa lucram pe numere reale vom lucra pe numere mari. SI eu inca nu stiu sa lucrez cu numere mari..

[Undeath]

Mai exact aveti aici :

http://infoarena.ro/problema/sqrt

http://infoarena.ro/monitor?task=sqrt

[tjt]

Eu as rezolva problema in felul urmator :

As implementa algoritmul de extragere a radacinii patrate asa cum l-am invatat in scoala generala si as impune limita K pentru primele zecimale .

Astfel ai evita sa lucrezi cu numere foarte mari si in acelasi timp ti-ai genera cate zecimale doresti tu,fara a le afisa pe toate odata asa cum se intampla cu sqrt() .

[Vman]

M-am gandit si eu prima data asa, ba chiar inainte din sqrt() sa scad trunc(sqrt()) astfel puteam citi linistit insa problema vine in momentul in care: de exemplu am 2 20... nu merge pentru 20 de zecimale(sa nu spun pana la max 10^3).

[tjt]

Din ce stiu cu algoritmul de extragere a radacinii patrate poti genera cate zecimale doresti ,chiar si 10^3.

Pe masura ce obtii zecimalele(cifrele) poti forma un numar de tip integer (are 2^16 - 1 ,asadar mai mare ca 10 ^3) cu ajutorul lor.

Edited December 27, 2012 by tjt

[Vman]

Nu ma poti ajuta cu vreo 2 linii de cod daca te rog? ca mie mi se blocheaza la valori pentru k>7

[gotr00t]

Opinia mea de ne-algoritmist.

Folosesti functia sqrt. Din valoarea returnata de functie ai putea sa scazi valoarea intreaga a valorii returnate. Astfel ramai cu un numar de forma 0.n1n2n3n4...nk..nm...nz...

Dupa ce realizezi asta convertesti numarul rezultat in string si, ca sa afisezi primele k zecimale, faci asa:

//nu facem cout pentru string[0] si string [1] acestea fiind caracterele 0 respectiv "." .

for(i=2;i<=k+2;i++)

cout<<string;

Update

#include<iostream>
#include<string.h>
#include <boost/lexical_cast.hpp>
#include<math.h>
using namespace std;
int main ()
{
int n=3123;
long double val;
val=sqrt(n);
val=val-int(val);
int k=8;
std::string s = boost::lexical_cast<std::string>(val);
for(int i=2;i<=k+2;i++)
cout<<s[i];
}

Edited December 31, 2012 by gotr00t