GCF algorithm error

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*Revise the program so that it prints out all the steps involved in the
algorithm. Here is a sample output:
GCF (500, 300) =>
GCF (300, 200) =>
GCF (100, 0) =>
100*/

#include <iostream>
#include <cstdlib>
using namespace std;

int Gcf(int a, int b);
void Print_gcf(int a, int b);

int main ()
{
    int a = 0, b = 0;
    
    cout << "Enter a: ";
    cin >> a;
    cout << "Enter b: ";
    cin >> b;
    cout << Gcf(a, b) << endl;
    
    system ("PAUSE");
    return 0;
}

 int Gcf(int a, int b)
 {
     if (b == 0)
        return a;
     else
         {
               Print_gcf(a,b);
               Gcf(b, a%b);
         }
 }
 
 void Print_gcf(int a, int b)
 {
         cout << "GCF (" << a << ") " << "(" << b << ") => " << a%b <<endl;
 }

everything runs fine except i always get 0 as the final answer. ive been stuck on this since 12pm last night and i cant figure it out. i key in 300 for a and 500 for b.
this is how i think its suppose to work:
a = 500
b = 300

500 300 = 200

gcf( 300, 200)
300 200 = 100

gcf( 200, 100)
200 100 = 0

gcf( 100, 0)
b == 0
return 100

but it keeps returning 0
>O
I had to run your program to understand your question (I think). This is what I get when I run your code:

Enter a: 300
Enter b: 500
GCF (300) (500) => 300 
GCF (500) (300) => 200
GCF (300) (200) => 100
GCF (200) (100) => 0
100
Press any key to continue . . .

The program correctly identifies the GCF as 100, but I think you are concerned about the column of numbers to the right of the => signs?

You will notice that your output does not match the output your professor has suggested to you. What you should see is:

Enter a: 300
Enter b: 500
GCF (300) (500) => 
GCF (500) (300) =>
GCF (300) (200) =>
GCF (200) (100) =>
GCF (100) (0) =>
100

There are two issues here.

1) On line 42 you print a%b. Don't do that. (It is where you are getting that last zero from.)

2) You only call the Print_gcf() if there is more to do... You should call it no matter what, at the very beginning of your Gcf() function.

PS. Get rid of that system() thing before you turn the assignment in.

Hope this helps.
1
2
3
4
5
6
7
8
9
10
int Gcf(int a, int b)
{
     if (b == 0)
        return a;
     else
         {
               Print_gcf(a,b);
               Gcf(b, a%b); //¿return?
         } // control reaches end of non-void function
}
The last zero is garbage.
yea i changed it to return Gcf(b, a%b); and it worked. thx guys
Topic archived. No new replies allowed.