Divizori

[•SpiderMan]

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?

[•Florian]

Ce inseamna optim? Da si tu niste restrictii de timp, memorie sau limitele numerelor din input.

[•SpiderMan]

nu am timp nu stiu cat poti tu de "repede", adica cat mai optim

[•Florian]

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"...  

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.

[•SpiderMan]

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

[•alexandru92]

Cum un interval reprezinta o multime ordonata de elemente poti face prin metoda Divide et Impera

[•SpiderMan]

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.

[•alexandru92]

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 .

[•toni2007]

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).

[•SpiderMan]

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 

[•Bogdan_tmm]

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

[•alexandru92]

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.

[•Mishu91]

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.

[•SpiderMan]

IN fond si la urma urmei e bine ce am facut eu nu?

[•alexandru92]

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

[•Florian]

Cod:

for( ; a != b; ++a, --b )  
{
      if( check(a) )
          ++nr;
     if( check(b) )
          ++nr;
}
if( check(a) )
  ++nr;

Absolut genial!  Nu e acelasi numar de operatii ca la solutia liniara? Plus ca intra in ciclu infinit pt anumite teste. 

[•blasterz]

Cod:

for( ; a != b; ++a, --b )  
{
      if( check(a) )
          ++nr;
     if( check(b) )
          ++nr;
}
if( check(a) )
  ++nr;

Absolut genial!  Nu e acelasi numar de operatii ca la solutia liniara? Plus ca intra in ciclu infinit pt anumite teste. 

Corect ... eu zic sa impartim intervalul [a,b] in 100 de bucati si sa obtinem O(n/100)

[•Florian]

Cam mult O(N/100).  Nu e mai optim sa scriem de mana MAX_B if-uri ? Iese O(1) !  

[•wefgef]

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.

[•SpiderMan]

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