infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Simoiu Robert din Decembrie 15, 2009, 14:27:33



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;
var sum:array[1..1000000] of longint;
    a,b,i,l,l1,j:longint;
    stop:boolean;
 begin
  write('a=');
  readln(a);
  write('b=');
  readln(b);
  write('Numerele din intervalul [',a,',',b,'] care se divid prin suma cifrelor sale sunt: ');
  l:=99;
  l1:=100;
  stop:=false;
  if (b<100) or (a<100) then
   begin
    if b<100 then
     l:=b;
    for i:=a to l do
     begin
      sum[i]:=i mod 10 + i div 10;
      if i mod sum[i]=0 then
       begin
        write(i,' ');
        stop:=true;
       end;
     end;
    end;
  if l<>b then
   begin
    if a>l then
     l1:=a;
    if b<1000 then
     l:=b
    else
     l:=999;
    for i:=l1 to l do
     begin
      sum[i]:=i mod 10 + (i div 10) mod 10 + (i div 10) div 10;
      if i mod sum[i]=0 then
       begin
        write(i,' ');
        stop:=true;
       end;
     end;
   end;
  if l<>b then
   begin
    if a>l then
     l1:=a
    else
     l1:=1000;
    for i:=l1 to b do
     begin
      j:=i;
      repeat
       sum[i]:=sum[i]+j mod 10;
       j:=j div 10;
      until j=0;
      if i mod sum[i]=0 then
       begin
        write(i,' ');
        stop:=true;
       end;
     end;
   end;
  if not stop then
   write('----nu exista numere din acest interval----');
  readln;
 end.


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)
{
  if(st>dr)
     return;
   if(st==dr)
       calc(st);
   else
   {
      calc (st) ;calc(dr);
      div(st+1,(st+dr)/2);
      div((st+dr)/2+1,dr-1);
   }
}
Dar ce rost are?!


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 )  
{
      if( check(a) )
          ++nr;
     if( check(b) )
          ++nr;
}
if( check(a) )
  ++nr;
@Rober atat timp cat afiseaza valorile corecte e bine


Titlul: Răspuns: Divizori
Scris de: Florian Marcu din Decembrie 16, 2009, 22:05:53
Cod:
for( ; a != b; ++a, --b )  
{
      if( check(a) )
          ++nr;
     if( check(b) )
          ++nr;
}
if( check(a) )
  ++nr;
Absolut genial!  =D&gt; Nu e acelasi numar de operatii ca la solutia liniara? Plus ca intra in ciclu infinit pt anumite teste.  :D


Titlul: Răspuns: Divizori
Scris de: Mircea Dima din Decembrie 16, 2009, 22:15:57
Cod:
for( ; a != b; ++a, --b )  
{
      if( check(a) )
          ++nr;
     if( check(b) )
          ++nr;
}
if( check(a) )
  ++nr;
Absolut genial!  =D&gt; Nu e acelasi numar de operatii ca la solutia liniara? Plus ca intra in ciclu infinit pt anumite teste.  :D

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!!