Java >> Java tutorial >  >> Java

GCD af N-numre i Java

Java

GCD af N-numre i Java | Array-programmer i Java – 17 | I det tidligere Java-program udviklede vi programmer til at sortere array-elementer og finde det omvendte af et array.

Programbeskrivelse:- Skriv et Java-program for at finde GCD af N numre eller mere end to numre. GCD af tre eller flere tal kan beregnes ved gentagne gange at tage GCD af par af tal.

gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b)

GCD for N tal beregnes også ved at finde primtalsfaktorerne, GCD for N tal er lig med primtalsfaktorerne fælles for alle tallene.

For en matrix af tal kan GCD beregnes som ,

// initialize result with first number in the array
result = arr[0];
// loop
for i = 1 to n-1
result = findHCF(result, arr[i])

Procedure for at finde GCD eller HCF med to tal ,

1) Tag to tal
2) Find det største og mindste tal blandt dem
3) Træk den mindste talværdi fra det største tal
4) Gentag denne proces, indtil begge tal bliver ens

GCD eller HCF for to tal i Java kan beregnes som ,

// Java method to find GCD or HCF of two numbers
public static int findHCF(int num1, int num2) {
  while(num1 != num2) {
    if(num1 > num2) 
       num1 = num1 - num2;
    else
       num2 = num2 - num1;
  }
  return num1;
}

Java-program til at finde GCD af N-numre

public class GCD {
  public static void main(String[] args) {

    // variables
    int size = 0;
    int arr[] = null;
    int result = 0;
    
    // create Scanner class object to read input
    Scanner scan = new Scanner(System.in);
    
    // read size
    System.out.print("Enter total numbers: ");
    size = scan.nextInt();
    
    // declare array
    arr = new int[size];
    
    // read numbers
    System.out.println("Enter numbers: ");
    for(int i=0; i<size; i++) {
      arr[i] = scan.nextInt();
    }
    
    // assign first number to result
    result = arr[0];
    
    // loop
    for(int i=1; i<size; i++) {
      result = findHCF(result, arr[i]);
    }
    
    // display result
    System.out.println("GCD = " + result);

    // close Scanner
    scan.close();
  }

  // recursive method
  public static int findHCF(int num1, int num2) {
    while (num1 != num2) {
      if (num1 > num2)
        num1 = num1 - num2;
      else
        num2 = num2 - num1;
    }
    return num1;
  }
}

Output for de forskellige test-cases:-

Indtast samlede tal:3
Indtast tal:
10 15 25
GCD =5

Indtast samlede tal:5
Indtast tal:
9 36 25 5 12
GCD =1

I dette program har vi først taget de nødvendige variabler:størrelse, arr og resultat. Størrelsesvariablen vil indeholde antallet af elementer i arrayet, arr-variablen repræsenterer arrayet, og resultatvariablen vil holde det endelige resultat.

Derefter oprettede vi et objekt af Scanner-klassen til at læse inputværdier fra slutbrugeren. For at læse input fra slutbrugeren kan du også bruge BufferedReader-klassen. Array-størrelsen skal tages, før arrayet erklæres. Efter at have erklæret arrayet, tag tal, dvs. elementer i arrayet. Det første tal vil blive tildelt resultatvariablen. Brug nu løkken til at gentage processen, og beregnede resultatet ved gentagne gange at tage GCD af par af tal.


Java tag