euclids algorithm

This is a discussion on euclids algorithm within the C Programming forums, part of the General Programming Boards category; Hi everyone I have to write a c program that calculates the greatest common divisor of two positive numbers , ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    19

    euclids algorithm

    Hi everyone

    I have to write a c program that calculates the greatest common divisor of two positive numbers , using the euclides algorithm . I have to implement two functions , one that works recursively to find the gdc and one that works with WHILE .

    The main has to call both functions and print the gcd found by each one PLUS how many steps each function needed to complete the task . By steps , i mean how many times the recursive function was called in the first function
    and how many times the WHILE looped in the second function

    Here is my solution . I would really appreciate any corrections or tips

    Thanks in advance

    Code:
    #include <stdlib.h>
                         
    int gcdrecurs(int m,int n,int *steps1 ) 
    {
      int temp , r ;
    
      *steps1 = *steps1 + 1;
      r = m % n;
      if (r == 0) 
      {
        return n;
      } 
      else 
      {
        return gdcrecurs(n , r , steps1 );
      }
    
    }
                         
    
    int gdcwhile(int m , int n , int *steps2)
    {
          int temp ;
          *steps2 = 0 ; 
          while (n !=0 )
          {
               *steps2 = *steps2 + 1 ;
               temp = m ;
               m = n ;
               n = temp % n ;
          }
           return  m;
    }
    
    main() 
    {
      int a1 , a2  , temp ,  gdc1 , gdc2 , steps1 , steps2 ; 
      printf("type two positive numbers\n");
      scanf("%d",&a1);
      scanf("%d",&a2)
      if (a1 < a2) 
      {
        temp = a1;
        a1 = a2;
        a2 = temp ;
      } 
      steps1 = 0;
      gdc1 = gcdrecurs(a1,a2,steps1);
      printf("the gdc is %d and  %d steps were needed using recursion" ,gdc1,steps1);
      gdc2 = gdcwhile(a1,a2,steps2);
      printf("the gdc is %d and %d steps were needed using while loop",gdc,steps2);
      return 0;
    
    }

  2. #2
    Epy
    Epy is offline
    Fortran lover Epy's Avatar
    Join Date
    Sep 2009
    Location
    California, USA
    Posts
    999
    main() should be an int type, also, you don't need brackets for one line statements in if-then-else structures, i.e:
    Code:
    if ... then
    something
    else
    something else

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,303
    Quote Originally Posted by Epy
    you don't need brackets for one line statements in if-then-else structures
    But if you want to continue using those braces even then, go ahead. You're in good company either way. (Though I think that the crowd that always uses them makes for better company )
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    Thanks for replying

    I have one more question for the first function

    Code:
    int gcdrecurs(int m,int n,int *steps1 ) 
    {
      int temp , r ;
    
      *steps1 = *steps1 + 1;
      r = m % n;
      if (r == 0) 
      {
        return n;
      } 
      else 
      {
        return gdcrecurs(n , r , steps1 );
      }
    
    }
    shouldn't the return statement be

    return gdcrecurs(n,r,&steps1) - mind the & -


    since steps1 is passed by reference ???? But it wont compile like that , it will compile without the & before the steps1 . Why is that ?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,303
    No, because steps1 is already a pointer to int.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    steps1 is of type int*
    &steps1 is of type int**

    what type the gdcrecurs expects?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    i think it shoud expect an int since the final outcome should be a greatest common divisor

  8. #8
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    sorry my mistake

  9. #9
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    you meant what it expects in steps1 right ?


    Well steps1 is supposed to count how many times the function is called ( by it self + 1 ) . So it should be an int passed by reference in order not to lose the value between recursive calls , right ?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,303
    Quote Originally Posted by johngav
    So it should be an int passed by reference in order not to lose the value between recursive calls , right ?
    Yes, but "it" refers to the int that steps1 points to.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    i'n not sure i get what you mean .

    steps1 points to an int that is initialised to zero

    steps1=0 in function main

    i

  12. #12
    Registered User
    Join Date
    Mar 2009
    Posts
    19
    i think i also have to correct my main() . Am i right ( mind the bold )

    Code:
    .....
    steps1 = 0;
      gdc1 = gcdrecurs(a1,a2,&steps1);
      printf("the gdc is %d and  %d steps were needed using recursion" ,gdc1,steps1);
      gdc2 = gdcwhile(a1,a2,&steps2);
      printf("the gdc is %d and %d steps were needed using while loop",gdc,steps2);
      return 0;

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Right. steps1 points to an int. Adding another & would add another "points to" to your description, which isn't what you want.

  14. #14
    Registered User
    Join Date
    Jan 2008
    Posts
    28
    yep. that's what you need since you're passing the address of the var to the function.

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. Euclid's algorithm
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-03-2001, 11:59 PM

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