Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: O problema interesanta de impartire  (Citit de 6146 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
alexjj
Vizitator
« : Martie 22, 2004, 17:57:31 »

Va propun urmatoarea problema spre a va da cu parerea daca se poate rezolva sau nu. Nu am inventat-o ci am gasit-o pur si simplu.

Se dau doua numere naturale m si n cu 0<m<n<=100000. Se cere sa se tipareasca numarul m/n in forma zecimala completa (cu perioada, unde este cazul).

Date de intrare : fractie.in care contine m si n despartite printr-un spatiu.

Date de iesire: fractie.out pe o singura linie
sub forma:
0.parte_neperiodica
0.parte_neperiodica(parte_periodica)
sau dupa cum este cazul

EXEMPLE
fractie.in               fractie.out
13 25                    0.52

73 505                   0.1(4455)

De asemenea se cere:
complexitate recomandata O(n);
memorie O(1);

Daca credeti ca ati rezolvat-o cereti-mi date de test.
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #1 : Martie 22, 2004, 19:50:40 »

Problema este destul de clasica si ideea de baza este sa faci ca pe foaie.. adica faci impartirea cum ai invatat la scoala, cat timp nu intalnesti de doua ori un rest. Acest algoritm are complextitate O(N) timp si memorie. O solutie cu O(1) memorie gasesti aici: http://probleme.ldc.ro/arhiva/R00-8/rezolv.html
Daca nu ma insel, problema a fost la Olimpiada Online si se gaseste si la USACO.  wink
Memorat
alexjj
Vizitator
« Răspunde #2 : Martie 23, 2004, 17:05:07 »

multumesc pentru raspuns.
m-am uitat pe site si nu vreau sa par nepoliticos, dar mi s-a servit aceeasi explicatie si de la cine a propus problema.
incearca pentru 0,23(4445) adica (234445-23)/999900. in perioada cifra se poate repeta oricat de mult.
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #3 : Martie 23, 2004, 17:22:27 »

Eu iti recomand sa ma citesti inca o data explicatia si ce am scris eu... si cine ti-a zis solutia ti-a zis bine. Nu a zis nimeni ca in perioada o cifra nu se poate repeta, ci doar ca pe masura ce faci impartirea odata ce ai doua resturi (nu cifre!) identice te poti opri... aceasta observatie este cat se poate de evidenta.. ti-am zis, ia un creion si hartie si fa impartirea si vezi cand apare perioada!  Cool
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines