Data Structures using java Your code must be well formatted and commented. While

Question

Data Structures using java

Your code must be well formatted and commented. While marks will not be assigned for properly formatting and commenting your code, All programs must include the “Essential Features of Program Documentation” (page 122). Details are included throughout Chapter 2 on best practices for documentation.

Q) Euclid's Algorithm is a well-known algorithm for computing the greatest common divisor (GCD) of two numbers. The algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are the same as the common divisors of b and r. Thus we can use the equation to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. GCD (a, b) = GCD (b, r) For example, GCD (36, 20) = GCD (20, 16) = GCD (16, 4) = GCD (4, 0) = 4 implies that the GCD of 36 and 20 is 4. It can be shown that for any two starting numbers, this repeated reduction eventually produces a pair where the second number is 0. Then the GCD is the other number in the pair. Now, Write a method named gcd that computes the greatest common divisor of two.

Comment

Explanation / Answer

This program asks for the user input of the numbers for which gcd is to be found and displays the output, If its not required then directly use function gcd and pass two Number though the function.

PROGRAM STARTS:

import java.io.BufferedReader; //method reads a single character from this buffered reader.
import java.io.IOException; //Declaration for exception handling
import java.io.InputStreamReader; // tells whether this stream is ready to be read.
public class Javagcd { //Define Class Name
public static void main(String args[]) throws // Specifying exceptions
NumberFormatException, IOException
{
System.out.println("Enter First number: "); //get input from the user
BufferedReader br=new BufferedReader(new
InputStreamReader(System.in));
int a = Integer.parseInt(br.readLine());
System.out.println("Enter Second number: "); //get input from the user
BufferedReader br=new BufferedReader(new
InputStreamReader(System.in));
int b = Integer.parseInt(br.readLine());

int result=gcd(a,b);
System.out.println("GCD of the numbers is: "+ result); // Printing Output
}
//Euclid's algorithm is based on the following property:
// if p>q then the gcd of p and q is the same as the gcd of a%b and b.
// a%b is the remainder of a which cannot be divided by b, e.g. 27 % 5 is 2.
static int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return gcd(b, a % b);
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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