algorithm - los - ¿Cuál es la forma más rápida de encontrar el gcd de n números?

como usar hashtag en instagram 2018

Question

¿Cuál es la forma más rápida de calcular el mayor divisor común de n números?

Answer 1

A continuación, se muestra el código fuente del programa C para encontrar HCF de N números utilizando matrices.

#include<stdio.h>

int main()
{
    int n,i,gcd;
    printf("Enter how many no.s u want to find gcd : ");
    scanf("%d",&n);
    int arr[n];
    printf("/nEnter your numbers below :- /n ");
    for(i=0;i<n;i++)
    {
        printf("/nEnter your %d number = ",i+1);
        scanf("%d",&arr[i]);
    }
    gcd=arr[0];
    int j=1;
    while(j<n)
    {
       if(arr[j]%gcd==0)
       {
           j++;
       }
       else
       {
           gcd=arr[j]%gcd;
           i++;
       }
    }
    printf("/nGCD of k no.s = %d ",gcd);
    return 0;
}

Para obtener más información, consulte este website para obtener más aclaraciones .......

Answer 2

Aquí estaba la respuesta que estaba buscando. La mejor manera de encontrar el gcd de n números es, de hecho, utilizando recursion.ie gcd (a, b, c) = gcd (gcd (a, b), c). Pero estaba obteniendo tiempos de espera en ciertos programas cuando hice esto.

La optimización que se necesitaba aquí era que la recursión se debía resolver usando un algoritmo de multiplicación de matriz rápida.

Answer 3

Aquí hay un método gcd que usa la propiedad que gcd (a, b, c) = gcd (a, gcd (b, c)).
Utiliza el método gcd de BigInteger porque ya está optimizado.

public static BigInteger gcd(BigInteger[] parts){
    BigInteger gcd = parts[0];
    for(int i = 1; i < parts.length; i++)
        gcd = parts[i].gcd(gcd);
    return gcd;
}

Answer 4

Deberías usar el algoritmo GCD de Lehmer .

Answer 5

Es posible que desee ordenar los números primero y calcular el gcd recursivamente a partir de los dos números más pequeños.

Answer 6

Puedes usar divide y vencerás. Para calcular gcdN ([]), divide la lista en primera mitad y segunda mitad. si solo tiene un num para cada lista. calcula usando gcd2 (n1, n2).

Acabo de escribir un código de muestra rápido. (asumiendo que todos los números en la lista son Ints positivos)

def gcdN(nums):
    n = len(nums)
    if n == 0: return "ERROR"
    if n == 1: return nums[0]
    if n >= 2: return gcd2(gcdN(nums[:n//2]), gcdN(nums[n//2:]))

def gcd2(n1, n2):
    for num in xrange(min(n1, n2), 0, -1):
        if n1 % num == 0 and n2 % num == 0:
            return num

Answer 7

Si tiene muchos números pequeños , la factorización puede ser realmente más rápida.

//Java
int[] array = {60, 90, 45};
int gcd = 1;
outer: for (int d = 2; true; d += 1 + (d % 2)) {
    boolean any = false;
    do {
        boolean all = true;
        any = false;
        boolean ready = true;
        for (int i = 0; i < array.length; i++) {
            ready &= (array[i] == 1);
            if (array[i] % d == 0) {
                any = true;
                array[i] /= d;
            } else all = false;
        }
        if (all) gcd *= d;
        if (ready) break outer;
    } while (any);
}
System.out.println(gcd);

(funciona para algunos ejemplos, pero no realmente probado)

Answer 8

Sin recursión:

int result = numbers[0];
for(int i = 1; i < numbers.length; i++){
    result = gcd(result, numbers[i]);
}
return result;

Para matrices muy grandes, podría ser más rápido utilizar el patrón de unión de horquilla, donde se divide la matriz y se calculan gcds en paralelo. Aquí hay un pseudocódigo:

int calculateGCD(int[] numbers){
    if(numbers.length <= 2){
        return gcd(numbers);    
    }
    else {
        INVOKE-IN-PARALLEL {
            left = calculateGCD(extractLeftHalf(numbers));
            right = calculateGCD(extractRightHalf(numbers));
        }
        return gcd(left,right);
    }
}

Answer 9

Un JavaScript recursivo (ES6) de una sola línea para cualquier cantidad de dígitos.

const gcd = (a, b, ...c) => b ? gcd(b, a % b, ...c) : c.length ? gcd(a, ...c) : Math.abs(a);

Answer 10

Usa el algoritmo euclidiano :

function gcd(a, b)
while b ≠ 0
   t := b; 
   b := a mod b; 
   a := t; 
return a;

Lo aplicas para los primeros dos números, luego el resultado con el tercer número, etc ...:

read(a);
read(b);

result := gcd(a, b);
i := 3;
while(i <= n){
    read(a)
    result := gcd(result, a);
}
print(result);

Answer 11

C ++ 17

He escrito esta función para calcular gcd de n números usando C ++ en la función __gcd (int a, int b).

int gcd(vector<int> vec, int vsize)
{
    int gcd = vec[0];
    for (int i = 1; i < vsize; i++)
    {
        gcd = __gcd(gcd, vec[i]);
    }
    return gcd;
}

Para saber más sobre esta función, visite este enlace .

También consulte el algoritmo GCD de Dijkstra desde el siguiente enlace. Funciona sin división. Por lo tanto, podría ser un poco más rápido (Corrígeme si estoy equivocado).

Answer 12

//Recursive solution to get the GCD of Two Numbers

long long int gcd(long long int a,long long int b)<br>
{
   return b==0 ? a : gcd(b,a%b);
}
int main(){
  long long int a,b;
  cin>>a>>b;
  if(a>b) cout<<gcd(a,b);
  else cout<<gcd(b,a);
return 0;
}

Answer 13

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class GCDArray{
    public static int [] extractLeftHalf(int [] numbers)
    {
        int l =numbers.length/2;
        int arr[] = Arrays.copyOf(numbers, l+1);
        return arr;
    }

    public static int [] extractRightHalf(int [] numbers)
    {
        int l =numbers.length/2;
        int arr[] = Arrays.copyOfRange(numbers,l+1, numbers.length);
        return arr;
    }

    public static int gcd(int[] numbers)
    {
        if(numbers.length==1)
            return numbers[0];
        else {
            int x = numbers[0];
            int y = numbers[1];
            while(y%x!=0)
            {
                int rem = y%x;
                y = x;
                x = rem;
            }
            return x;
        }
    }
    public static int gcd(int x,int y)
    {
            while(y%x!=0)
            {
                int rem = y%x;
                y = x;
                x = rem;
            }
            return x;

    }
    public static int calculateGCD(int[] numbers){
        if(numbers.length <= 2){
            return gcd(numbers);    
        }
        else {

                    int left = calculateGCD(extractLeftHalf(numbers));
                    int right = calculateGCD(extractRightHalf(numbers));

            return gcd(left,right);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        System.out.println(calculateGCD(arr));
    }
}

**

Arriba está el código de trabajo de Java ..... el pseudo código del cual ya se menciona por

**