Euclid's algorithm

This is a discussion on Euclid's algorithm within the C Programming forums, part of the General Programming Boards category; ok i have to write a program that reduces fractions by using the euclidean algorithm.... i need help figuring out ...

  1. #1
    Unregistered
    Guest

    Unhappy Euclid's algorithm

    ok i have to write a program that reduces fractions by using the euclidean algorithm....

    i need help figuring out how to implement this algorithm into "C" code this is what my program looks like so far.......
    /*project2*/
    #include<stdio.h>
    int main ()
    {
    int x,
    y,
    a,
    b,
    c,
    result = 1;

    printf("Enter a fraction\n");
    scanf("%d/%d", &x, &y);
    printf( "You entered %d/%d\n", x, y );

    a = x / y;
    b = x % y;
    c = y;


    if(x < y)
    printf("That fraction reduces to %d/%d\n", &x, &y);
    if(x = y)
    printf("That fraction reduces to 1\n");
    if(x > y)
    {
    while( result != 0)
    result = b;
    x = y;
    y = result;




    return 0;

    }







    Please.....any help(comments, hints) would be very much appreciated

  2. #2
    Unregistered
    Guest
    i tried this......What am i doing wrong?????

    if(x > y)
    {
    while( result != 0)
    {
    result = x % y;
    x = y;
    y = result;

    }
    gcf = x;
    printf("that fraction reduces to %d/%d\n",&gcf, &a);
    }

  3. #3
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    Almost, but your loop wont prevent result from becoming zero, it'll only stop when it becomes zero. Something like this should work -

    Code:
    #include <stdio.h>
    
    
    int main()
    
     {
              int a =12, b=20;
    	  int gcd;
    	  int result,x,y;
    	  
       	  x=a;
    	  y=b;
    
    	  while(result!=0)
    	  {
    		  gcd=result;
    		  result =x%y;
    		  x=y;
    		  y=result;
    	  }
    
    	  printf("%d/%d = %d/%d",a,b,a/gcd,b/gcd);
    
    
    	  return 0;
    
    }

  4. #4
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    ...that wouldn't work if there was no initial remainder. This is better -

    Code:
    #include <stdio.h>
    
    int main()
    
     {
          int a =12,b=20;
    	  int gcd;
    	  int result,x,y;
    	  
       	  x=a;
    	  y=b;
    
    	  if(a%b)
    	  {
    		while(result!=0)
    		{
    		  gcd=result;
    		  result =x%y;
    		  x=y;
    		  y=result;
    		}
    	  }
    	  else
    		  gcd=b;
    
    	  printf("%d/%d = %d/%d",a,b,a/gcd,b/gcd);
    
    
    	  return 0;
    
    }

  5. #5
    Unregistered
    Guest
    Arent you testing the value of result without initializing it in the while loop ?

  6. #6
    Registered User
    Join Date
    Sep 2001
    Location
    Australia
    Posts
    212
    I cant help to notice that this question on this algorithm has been posted many times before. Perhaps the Cboard FAQ needs updating a bit. Am I the only one who finds all this repetition annoying?

  7. #7
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    Arent you testing the value of result without initializing it in the while loop ?
    Yes, to be safe the line

    y=b;

    should be

    result=y=b;

    Although as long as result is initialised to any non-zero value the code should work.

    There also should be some code that checks for divide by zero.
    zen

  8. #8
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284

    Post

    there is another interesting algorithm to find out the gcd of two positive numbers
    if u,v are even
    gcd(u,v)=2gcd(u/2,v/2)
    if u is even and v is odd
    gcd(u,v)=gcd(u/2,v)
    if both are odd
    gcd(u,v) is =gcd(u-v,v)
    note u-v is even and |u-v|<=max(u,v) (if u>=,v>=0)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 11-13-2005, 02:53 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Binary Euclid's Algorithm
    By exluddite in forum C++ Programming
    Replies: 7
    Last Post: 09-26-2004, 09:08 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21