Stranica 1 od 1

[C] Faktorisanje brojeva – optimizacija algoritma

PostPoslato: Nedelja, 11. Mart 2018, 19:43
od Miladin Jovic
Pozdrav ljudi. Iako ovaj potforum nije namenjen problemima optimizacije algoritama, postaviću zadatak ovde jer smatram da ima dosta veze sa matematikom. Tekst zadatka možete naći ovde. Naime, imam rešenje koje radi u predviđenom vremenskom roku za najviše [inlmath]8[/inlmath] od [inlmath]10[/inlmath] test primera (ne znam kako, ali njihov checker nekada izbacuje da je za [inlmath]6[/inlmath] ulaza zadovoljeno ograničenje, a ponekad za [inlmath]8[/inlmath]). Algoritam za preostale ulaze prekoračuje dozvoljeno vreme izvršavanja. Priložiću program, pisan u C-u u nastavku.

Kôd: Obeleži sve
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
 int brojKoraka(int x, int y)
{
   int pom;
   int cond;
   int col;
   int ex=0;
   int ey=0;
   int k=0;


   if(x==y) return 0;

       /* u x ćemo čuvati vrednost većeg broja. Tako da ako je ulaz 6 10, x će biti 10, a y 6. Zapravo, 10 ćemo svoditi na 6, iako je originalno dato da od 6 treba dobiti 10. Svakako je u pitanju isti broj koraka. */

   if(x>y)
   {
      cond=x%y;
      col=x/y;
   }
   else
   {
      cond=y%x;
      col=y/x;
   }

   if(cond == 0)
   {
      while(col%2 == 0)
      {
         col>>=1;
         k++;
      }
      for (int i = 3; i <= sqrt(col); i = i+2)
      {
         while (col%i == 0) //  % izračunava ostatak pri deljenju levog operanda desnim (analogija MOD u pascalu)
         {
            col = col/i;
            k++;
         }
      }
      k+=(col>2);
   }
   else
   {
      while (x%2 == 0)
      {
         x = x >> 1;
         ex++;
      }

      while(y%2 == 0)
      {
         y>>=1;
         ey++;
      }

      if(y>x)
      {
         pom=x;
         x=y;
         y=pom;
      }
      k+=abs(ex-ey);

      for (int i = 3; i <= sqrt(x); i = i+2)
      {
         ex=ey=0;
         while (x%i == 0)
         {
            x = x/i;
            ex++;
         }
         if(x==y) return (k+ex);

         while(y%i == 0)
         {
            y/=i;
            ey++;
         }

         if(y>x)
         {
            pom=x;
            x=y;
            y=pom;
         }

         k+=abs(ex-ey);
      }

      if(x!=y)
         k+=(x>2)+(y>2); // izraz (x>2) daje jedinicu ako je x>2, u suprotnom nulu. Isto vazi i za y
   }

   return k;
}

int main()
{
    int n,i,x,y;
    scanf("%d",&n);

   for(i=0; i<n; i++)
   {
      scanf("%d%d",&x,&y);
      printf("%d\n",brojKoraka(x,y));
   }
   return 0;
}

Ukratko, ideja je sledeća. Ako je veći broj deljiv manjim, razložićemo njihov količnik na proste činioce i to će biti broj potrebnih "specijalnih operacija", gde su specijalne operacije definisane na način naveden u zadatku. Ukoliko to nije slučaj, broj specijalnih operacija određujemo kao razliku eksponenata prostih činioca koji ulaze u faktorizacioni oblik jednog od brojeva. Dakle, za ulaz [inlmath]10[/inlmath] [inlmath]6[/inlmath] algoritam bi radio na sledeći način. [inlmath]10=2\cdot5[/inlmath], [inlmath]6=2\cdot3[/inlmath]. Za faktor [inlmath]2[/inlmath] razlika između izložioca je [inlmath]0[/inlmath]. Kako smo oba broja sveli na neparne proste, algoritam stiže do poslednjeg if-a u funkciji vratiBrojKoraka. Kako su obe vrednosti različite i veće od dva, [inlmath]k[/inlmath] će uzeti vrednost [inlmath]2[/inlmath].

For petlja, koja sledi nakon svođenja oba broja na neparne, će se (u najgorem slučaju) izvršavati sve dok obe početne vrednosti ne svede na odgovarajuće najveće proste činioce. Otuda i potreba za pomenutim if-om na kraju.