Question

can somebody help me with this exercise

5 Euclidean algorithm

The largest common divisor (gcd) of two positive integers p and q can be given by the

Euclid's algorithm explained in the lecture will be determined.

· Write a function gcdIterative that uses the largest common divisor of p and q

Calculates loop structure and returns. Use the pseudocode given in the lecture

as a starting point and implement it as directly as possible into a C ++ program. Use as a variable name

in your program the corresponding designations from the pseudocode.

· Write a function gcdRecursive that recursively uses the largest common divisor of p and q

calculates and returns the Euclidean algorithm. Replace the while loop with the iterative one

Variant by recursive function calls and the assignments from the iterative variant by corresponding ones

Arguments for the function parameters of the recursive function.

· Test your functions by reading values ​​for p and q and their associated largest common

Output divider.

Answer 1

Output:

/*------------------------------------------------------------code-------------------------------------*/

#include<iostream>
using namespace std;

int gcdIterative(int p, int q)
{
while (p != q)
   {
       if (p > q) //If p is greater than q
       p = p - q;
       else //If q is greater than p
       q = q - p;
   }
   return p;
}

int gcdIterativeEfficient(int p, int q)
{
int rem;
while(q > 0)
{
rem = p%q;
p = q;
q = rem;
}
return p;
}

int gcdRecursive(int p, int q)
{
if(p == 0)
return q;
if (q == 0)
return p;
//Base case
if (p == q)
return p;

if (p > q) //If p is greater than q
return gcdRecursive(p-q, q);
else //If q is greater than p
return gcdRecursive(p, q-p);

}

int gcdRecursiveEfficient(int p, int q)
{
if (q == 0)
return p;
return gcdRecursiveEfficient(q, p % q);
}

int main()
{
int num1,num2;
cout<<"Enter Number1: ";
cin>>num1;
cout<<"Enter Number2: ";
cin>>num2;
cout<<"Result from Iterative Method: "<<gcdIterative(num1, num2)<<endl;

cout<<"Result from Efficient Iterative Method: "<<gcdIterativeEfficient(num1, num2)<<endl;

cout<<"Result from Recursive Method: "<<gcdRecursive(num1, num2)<<endl;

cout<<"Result from Efficient Recursive Method: "<<gcdRecursiveEfficient(num1, num2)<<endl;

return 0;
}

/*
Let see all above method using example
p = 15, q = 25;

First function: gcdIterative

check p != q =>true enter in while loop
iteration 1
Here q>p then
q = q-p => 25-15 = 10

Now p = 15, q = 10
check p != q =>true enter in while loop
iteration 2
Here p>q then
p = p-q => 15-10 = 5

Now p = 5, q = 10
check p != q =>true enter in while loop
iteration 3
Here p<q then
q = q-p => 10-5 = 5

Now p = 5, q = 5
check p != q => false so get out from while loop

Now return p => 5

Second Function gcdIterativeEfficient

p = 15, q = 25;

check q >0 => true
Enter to while loop:
1st Iteration
rem = p%q; => 15%25 => 15
p=q => p =25
q=rem => q = 15

check q >0 => true
Enter to while loop:
2nd Iteration
rem = p%q; => 25%15 => 10
p=q => p =15
q=rem => q = 10

check q >0 => true
Enter to while loop:
3rd Iteration
rem = p%q; => 15%10 => 5
p=q => p = 10
q=rem => q = 5

check q >0 => true
Enter to while loop:
4th Iteration
rem = p%q; => 10%5 => 0
p=q => p = 5
q=rem => q = 0

check q >0 => false

then return p => 5;

Third function gcdRecursive

gcdRecursive(15,25)
||
gcdRecursive(15,10) = > gcdRecursive(p,q-p)

||
gcdRecursive(5,10) => gcdRecursive(p-q,q)
||
gcdRecursive(5,5) => gcdRecursive(p, q-p)

Now p == q =>true
return p => 5

Note: Name your variable as your pseudo code

*/