A computing question about recursion functions and algorithms

[Shmee150]

Ok, complete n00b here I know..... BUT.....

I am trying to make an iterative algorithm to find the highest common factor of two
numbers; X and Y, and where I'm at is the following:


INPUT (X, Y)
DO (X, X MOD Y) WHILE Y>0
END DO WHEN Y=0
OUTPUT X


I am sure this is along the right lines, but that the format is wrong, anybody able to spare a few seconds to help me make it right? It would be very appreciated!!!

Thanks guys!

ShMeE

[luap.h]

i found this on a newsgroup

int hcf(int x, int y) 
{   
 // Make sure y is bigger   
 if (y > x) 
 {     std::swap(x, y);   } 

 // If the remainder is 0, then y is the HCF of y and x   
 // Otherwise, recurse to find the HCF of x and the remainder (x % y)   

 if (x % y == 0) 
 {     return y;   }
  else {     return hcf(x, x % y);   } 

}

[SourceQuench]

Obligatory quote: "To understand recursion, we must first understand recursion."

[mr_anderson187]

im not big on maths things but if you explain better what the maths is your trying to do, im pretty sure i can sort the code for it

[Shmee150]

What I am trying to do is:

Create an algorithm to take two integers as inputs and return an integer value. n the algorithm, it uses MOD operations, in order to find the highest common factor of the two original integers.

Thank you very much for any help!

ShMeE

[mr_anderson187]

not entirely sure what your trying to do still, im a bit hungover yet but:

#include <iostream>
using namespace std;

int main()
{

int num1;
int num2;
int result;

cout << " please input the first number, the larger of the two" endl;
cin >> num1;
cout << "please input the second number, the smaller of the two" endl;
cin >> num2;

result = num1 % num2;

cout << " the modulus of the two numbers is" << result << endl;
return 0;
}

totally not sure if thats what your after but tis a frame for doing anything

you could use loops for your function for finding the modulus, i have a clue about factors and Highest common factors, and multiples, but with an example i coudl probably sort it

while (y > 0 || y == 0)
{
//do your stuff in here
}

another thing you could do would be to have a counter, in these HCF and LCM thigsn we did at school it was usefull to fidn out how many times one divided into another then multiply it by somethign else to find some pointless number, so you could encorporate:

while (y > 0 || y == 0)
{
int count = 0;
//do your stuff in here
count++
}

that would get you a number of how many tiems it did whatever you wanbt before the number got down to one.

still not totally sure i know what your after, but with a little more info it should be easy

[Shmee150]

Thanks for being so helpful.

What I have to do is turn this recursive function into an iterative algorithm:


FUNCTION Curiosity(X:Integer;Y:Integer):Integer;
IF Y = 0 THEN Curiosity = X
ELSE Output Y and (X MOD Y)
Curiosity = Curiosity(Y, X MOD Y)
ENDIF
END Curiosity


When the solution is written out it looks something like:


Curiosity (120, 42)
42 into 120 goes twice with r. 36
Curiosity (42, 36)
36 into 42 goes once with r. 6
Curiosity (36, 6)
6 into 36 goes six times with r. 0
hence y=0 => Curiosity = 6
The answer is 6


So I was thinking of using a DO WHILE loop function to keep trying to divide Y into X until Y was no longer > than 0, and when it becomes 0, the function needs to end and make the Curiosity = X at that time.

Thanks again for the help!

ShMeE