Titlul: Divizori Scris de: Simoiu Robert din Decembrie 15, 2009, 14:27:33 Am o problema de genul: Sa se gaseasca toate numerele din intervalul [a,b] care sa se divida prin suma cifrelor(ex. 36->3+6=9 si 9|36). Exista vreo metoda optima de rezolvare?
Titlul: Răspuns: Divizori Scris de: Florian Marcu din Decembrie 15, 2009, 17:29:17 Ce inseamna optim? Da si tu niste restrictii de timp, memorie sau limitele numerelor din input.
Titlul: Răspuns: Divizori Scris de: Simoiu Robert din Decembrie 15, 2009, 19:53:41 nu am timp nu stiu cat poti tu de "repede", adica cat mai optim
Titlul: Răspuns: Divizori Scris de: Florian Marcu din Decembrie 15, 2009, 19:58:29 Parcugi fiecare element de la a la b, si le faci suma cifrelor, verificand apoi daca se divid prin ea. E brute force... E problema de "curtea scolii"... :-k
Daca a si b sunt relativ mici, poti precalcula un vector sum[ i ] = suma cifrelor lui i. Si o sa ai sum[ i ] = sum[i/10] + i%10 ( i = 1, b ) ( asta ca sa nu mai faci la fiecare pas suma cifrelor ) => complexitate O(b) . Ceva mai optim nu vad. Titlul: Răspuns: Divizori Scris de: Simoiu Robert din Decembrie 15, 2009, 20:34:45 Aham dar totusi vine [a,b], le parcurg pe toate si fac o structura repetitiva in care calculez suma cifrelor si apoi verific, nu stiu intervalul poate fi longint :( e cam mare
Titlul: Răspuns: Divizori Scris de: alexandru din Decembrie 15, 2009, 20:56:34 Cum un interval reprezinta o multime ordonata de elemente poti face prin metoda Divide et Impera
Titlul: Răspuns: Divizori Scris de: Simoiu Robert din Decembrie 15, 2009, 21:22:39 Ce este metoda divide et impera? Si in legatura cu problema am facut-o asa nu stiu daca pot sa o fac mai optim
Cod: program intervalsuma; Titlul: Răspuns: Divizori Scris de: alexandru din Decembrie 16, 2009, 11:28:00 Divide et Impera este o metoda de programare. Sa zicem ca avem o multime finita si ordonata de elemente S={ x1, x2, x3, ... , xn }. Metoda se bazeaza pe impartirea multimi in doua multumi. Apoi se ia prima multime si se imparte in 2 pana cand ajungem la o multime ce poate fi evaluata direct si apoi se reunesc solutiile. Analog cu a doua multime si apoi se reunesc solutiile. Desi suna complicat este defapt foarte usor :D.
Titlul: Răspuns: Divizori Scris de: Pripoae Teodor Anton din Decembrie 16, 2009, 11:34:11 Cum un interval reprezinta o multime ordonata de elemente poti face prin metoda Divide et Impera Vezi ca zici prostii. Cu divide et impera ai o(n log n) si merge si o(n). Titlul: Răspuns: Divizori Scris de: Simoiu Robert din Decembrie 16, 2009, 12:27:34 MErci fain as mai vrea sa-mi spuneti ceva is incepator si nu ma stiu adica nu stiu EXACt ce inseamna complexitate, stiu ca inseamna timpul de executie dar imi puteti explica mai "amanuntit"? Si imi poti detalia acea metoda daca nu te supara? MERCI :winner1:
Titlul: Răspuns: Divizori Scris de: Tirca Bogdan din Decembrie 16, 2009, 15:41:07 Poti si cu Divide et Impera in o(n).
Cod: void div(int st,int dr) Titlul: Răspuns: Divizori Scris de: alexandru din Decembrie 16, 2009, 18:28:23 Vezi ca zici prostii. Cu divide et impera ai o(n log n) si merge si o(n). Nu stiu de unde ai scos O( n log n ), nu fac pentru fiecare numar o cautare binara si le grupez.O alta idee ar fi sa parcurgi , in acelsi timp, sirul de la a si de la b si sa verific daca respecta proprietatile. Complexitatea este O(n/2). Pentru mai multe detalii despre complexitate gasesti aici (http://en.wikipedia.org/wiki/Computational_complexity_theory). Titlul: Răspuns: Divizori Scris de: Andrei Misarca din Decembrie 16, 2009, 19:23:22 1) Nu are sens să faci divide et impera în cazul de față.
2) Cum să îți iasă complexitatea O(N/2)? Pe lângă faptul că O(N/2) este incorect din punct de vedere formal, întrucât constantele se elimină, nici nu prea îmi dau seama de unde ți-ar ieși ție N/2 pași. Titlul: Răspuns: Divizori Scris de: Simoiu Robert din Decembrie 16, 2009, 19:29:43 IN fond si la urma urmei e bine ce am facut eu nu?
Titlul: Răspuns: Divizori Scris de: alexandru din Decembrie 16, 2009, 20:25:47 2) Cum să îți iasă complexitatea O(N/2)? Desigur consider ca check(a) se executa in O(1)Cod: for( ; a != b; ++a, --b ) Titlul: Răspuns: Divizori Scris de: Florian Marcu din Decembrie 16, 2009, 22:05:53 Cod: for( ; a != b; ++a, --b ) Titlul: Răspuns: Divizori Scris de: Mircea Dima din Decembrie 16, 2009, 22:15:57 Cod: for( ; a != b; ++a, --b ) Corect :P... eu zic sa impartim intervalul [a,b] in 100 de bucati si sa obtinem O(n/100) :D Titlul: Răspuns: Divizori Scris de: Florian Marcu din Decembrie 16, 2009, 22:18:16 Cam mult O(N/100). [-X Nu e mai optim sa scriem de mana MAX_B if-uri ? Iese O(1) ! :D
Titlul: Răspuns: Divizori Scris de: Andrei Grigorean din Decembrie 17, 2009, 03:58:27 Lasand mistourile la o parte...
Alexandru, cand un incepator pune o intrebare pe forum, lasa-i pe cei mai experimentati sa-si spuna parerea inaintea ta. Posturile tale de mai sus, pe langa inexactitatile pe care le contin, nu cred ca au reusit sa faca altceva decat sa il bage si mai tare in ceata pe Robert. Ceilalti, inteleg ca e greu sa va abtineti, dar haideti totusi sa fim mai seriosi un pic. Titlul: Răspuns: Divizori Scris de: Simoiu Robert din Decembrie 17, 2009, 09:30:04 Merci Andrei Grigorean, man eu nu am invatat subprograme, au nu am invatat nici vectorii, am facut PASCALUL (nu c++, dar stiu si ceva din el) de 3 zile, dar cum eu is mai curios il stiu cam de cand am inceput pseudocodul, am facut probleme de pe infoarena, destul de grele, ma pasioneaza, dar nu am facut subprograme si inca nu am experienta necesara ca voi sa puteti vorbi cu mine "asa". Oricum peste 1 an poate putem vorbi "asa". Merci!!
|