каков самый быстрый способ вычисления наибольшего общего делителя n чисел?
Каков самый быстрый способ найти gcd из n чисел?
Ответ 1
Вы должны использовать алгоритм Lehmer GCD.
Ответ 2
Без рекурсии:
int result = numbers[0];
for(int i = 1; i < numbers.length; i++){
result = gcd(result, numbers[i]);
}
return result;
Для очень больших массивов может быть быстрее использовать шаблон fork-join, где вы разбиваете свой массив и вычисляете gcds параллельно. Вот несколько псевдокодов:
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);
}
}
Ответ 3
Вы можете сначала отсортировать номера и вычислить gcd рекурсивно, начиная с наименьших двух чисел.
Ответ 4
C++ 17
Я написал эту функцию для вычисления gcd из n чисел, используя встроенную __gcd(int a, int b) C++ __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;
}
Чтобы узнать больше об этой функции, перейдите по этой ссылке.
Также см. Алгоритм Dijkstra GCD по следующей ссылке. Работает без деления. Так что это может быть немного быстрее (пожалуйста, поправьте меня, если я ошибаюсь.)
Ответ 5
Если у вас много чисел small, факторизация может быть на самом деле быстрее.
//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);
(работает для некоторых примеров, но не проверен)
Ответ 6
Используйте Евклидовой алгоритм:
function gcd(a, b)
while b ≠ 0
t := b;
b := a mod b;
a := t;
return a;
Вы применяете его для первых двух чисел, затем результат с третьим номером и т.д.:
read(a);
read(b);
result := gcd(a, b);
i := 3;
while(i <= n){
read(a)
result := gcd(result, a);
}
print(result);
Ответ 7
Вы можете использовать divide и побеждать. Для вычисления gcdN ([]) вы разделите список на первую половину и вторую половину. если для каждого списка есть только одно число. вы вычисляете с помощью gcd2 (n1, n2).
Я только что написал быстрый пример кода. (при условии, что все число в списке являются положительными Ints)
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
Ответ 8
Как насчет следующего, используя евклидов алгоритм по вычитанию:
function getGCD(arr){
let min = Math.min(...arr);
let max= Math.max(...arr);
if(min==max){
return min;
}else{
for(let i in arr){
if(arr[i]>min){
arr[i]=arr[i]-min;
}
}
return getGCD(arr);
}
}
console.log(getGCD([2,3,4,5,6]))Ответ 9
Здесь gcd-метод, который использует свойство gcd (a, b, c) = gcd (a, gcd (b, c)). Он использует метод BigInteger gcd, поскольку он уже оптимизирован.
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;
}
Ответ 10
//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;
}
Ответ 11
Ниже приведен исходный код программы C для поиска HCF из N чисел с использованием массивов.
#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;
}Ответ 12
Рекурсивный JavaScript (ES6) однострочный для любого количества цифр.
const gcd = (a, b, ...c) => b ? gcd(b, a % b, ...c) : c.length ? gcd(a, ...c) : Math.abs(a);
Ответ 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));
}
}
**
Выше приведен рабочий код java..... псевдокод которого является уже упоминаем https://stackoverflow.com/users/7412/dogbane
**
Ответ 14
Вот был ответ, который я искал. Лучший способ найти gcd из n чисел действительно использует recursion.ie gcd (a, b, c) = gcd (gcd (a, b), c). Но когда я это делал, я получал таймауты в определенных программах.
Оптимизация, которая была необходима здесь, заключалась в том, что рекурсия должна быть решена с использованием алгоритма быстрого умножения матрицы.