C++ Data Structures Question Euclid’s Algorithm: function gcd(a, b) while b 0 t

Question

C++ Data Structures Question

Euclid’s Algorithm:

function gcd(a, b)

    while b 0

       t := b;

       b := a mod b;

       a := t;

    return a;

Remark : If a > 0 and b > 0, then a mod b = a%b. But if a < 0, then a mod b = a%b + b, because a%b < 0.

Question 1: Program Euclid’s algorithm. Given two numbers a and b, print out gcd(a,b).

Question 2: Implement a function

int Inverse(int a, int b){ }

that will print out a-1 mod b when a and b are entered. If gcd(a, b) > 1, then it should make a statement that there is an error.

function gcd(a, b)

    while b 0

       t := b;

       b := a mod b;

       a := t;

    return a;

Explanation / Answer

#include<iostream.h>
#include<conio.h>

int gcd(int a, int b) // code for gcd calculation
   {
       int t;
       while(b!=0)
           {
               t = b;
               b = a%b;
               a = t;
           }
       return t;
   }

void inverse(int a, int b) // definition of inverse method
   {
       int val = gcd(a,b); // calculate gcd initially
       if(val>1) // if gcd greater than 1, then display error
           cout<<"There is an error";
       else // if gcd is not greater than 1, then display (a-1) mod b
           cout<<" (a-1)mod b = " << (a-1)%b<<endl;
   }

void main()
   {
       int a,b;
       clrscr();

       cout<<"Enter the numbers";
       cin>>a>>b;
       int n = gcd(a,b);
       cout<<"GCD IS:"<<n<<endl;
       inverse(a,b);
       getch();
   }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.