Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI MATEMATIKA U INFORMATICI MATEMATIKA U PROGRAMIRANJU

[C] Faktorisanje brojeva – optimizacija algoritma

[C] Faktorisanje brojeva – optimizacija algoritma

Postod Miladin Jovic » Nedelja, 11. Mart 2018, 19:43

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.
Zaslužni forumaš
 
Postovi: 378
Zahvalio se: 243 puta
Pohvaljen: 138 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Povratak na MATEMATIKA U PROGRAMIRANJU

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 23 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 14:08 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs