|
Titlul: O problema interesanta de impartire Scris de: alexjj din 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. Titlul: O problema interesanta de impartire Scris de: Mircea Pasoi din 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: Titlul: O problema interesanta de impartire Scris de: alexjj din 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. Titlul: O problema interesanta de impartire Scris de: Mircea Pasoi din 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! 8)
|