agent3889's blog

By agent3889, 8 years ago, In English,
hey guys i found this book while i search the net. this might be useful for some of you.

http://acm.uva.es/problemset/Art_of_Programming_Contest_SE_for_uva.pdf
 
 
 
 
  • Vote: I like it
  • -13
  • Vote: I do not like it

8 years ago, # |
Rev. 3   Vote: I like it +30 Vote: I do not like it

Mmm...

int gcd(int a, int b)
{
int r=1;
if(a>b)
{
while ( r!=0)
{
r=a%b;
a=b;
b=r;
}
return a;
}
else if ( b>a)
{
while (r!=0)
{
r=b%a;
b=a;
a=r;
}
return b;
}
else if ( a==b)
return a;
}


I love this book!

  • 8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    H-m... 

    ===
    int gcd(int a, int b)
    {
      while ((a > 0) && (b > 0)){  
        if (a > b) a = a % b;
        else b = b % a;
       }
      return a + b;
    }
    ===
    ?
    • 8 years ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      NO!
      int gcd(int x, int y)
      {
             return y ? gcd(y,x%y) : x;
      }

      • 8 years ago, # ^ |
          Vote: I like it -12 Vote: I do not like it
        Yes!
         :) 
        • 8 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          int gcd(int a, int b)
          {
              while (a)
              {
                  int c = b % a;
                  b = a;
                  a = c;
              }
              return b;
          }
          
          • 8 years ago, # ^ |
            Rev. 2   Vote: I like it +4 Vote: I do not like it

            Попсово, но всё же...

            int gcd (int a, int b) 

            {

                while (b) 

                    b ^= a ^= b ^= a %= b;

                return a;

            }


            Кстати, а каким тегом можно обрамить для синтаксической подсветки?

  • 8 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Where did you get this snippet? Can't find it in the mentioned book (or the link have changed?)

    Ah... It is in appendix B... But in chapter 7 there is proper and far shorter implementation... What is this wonderful stuff which the author uses for loading his cigarettes, I wonder?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
another way.... :)

public static int gcd(int a, int b) {
        int gcd = 0;

        while (a != b) {

            if (a > b) {
                a -= b;
            } else {
                b -= a;
            }

        }
        gcd = a;

        return gcd;
    }
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    This way is far slower, since these repetitious (a -= b) are the same as a %= b, but performed in a/b steps.

    Since all modern computers perform division operation with the same speed as addition/subtraction it is obvious waste of time.

    The only worse thing I can think of is:

    public static int gcd(int a, int b) {
        int gcd = Math.min(a, b);
        while (a % gcd != 0 || b % gcd != 0)
            gcd--;
        return gcd;
    } // gcd
    
    • »
      »
      »
      8 years ago, # ^ |
      Rev. 5   Vote: I like it -9 Vote: I do not like it

      By the way, gcd with subtraction is only 1.5 times slower in average than gcd with division :)

      Moreover:

      long long gcd1(long long a, long long b)
      {
         return b ? gcd1(b,a%b) : a;
      }
      long long gcd2(long long a, long long b)
      {
          while (a != b) {
              if (a > b) {
                  a -= b;
              } else {
                  b -= a;
              }
          }
          return a;
      }
      
      int main()
      {
         int n, m;
         cin >> n >> m;
         long long result = 0; 
         cout<<clock()<<endl; 
         for (int j=0;j<m;j++) 
          for (int i=1;i<=n; i++) 
             result += gcd1(n, i);
      
         cout<<clock()<<endl; 
         for (int j=0;j<m;j++,rand()) 
           for (int i=1;i<=n; i++) 
             result += gcd2(n, i);
          
         cout<<clock()<<endl; 
         cout<<result<<endl; 
      }
      
      CF server, gcc, input "2000 3000", gcd1 in 718ms, gcd2 in 625ms (!)
      
      
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it
        try something more interesting, try "2 10.000.000.001" as input ;-)
  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    def gcd(a,b):
        r=a%b
        while r > 0:a, b, r = b, r, b%r
        return b

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it
      def gcd(a,b):
          while b:
              a, b = b, a % b
          return a