Какой самый быстрый способ найти gcd из n чисел?
Какой самый быстрый способ вычислить наибольший общий делитель n чисел?
13 ответов
Без рекурсии:
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);
}
}
Вы можете сначала отсортировать числа и рекурсивно вычислить gcd, начиная с двух самых маленьких.
C++17
Я написал эту функцию для вычисления gcd из n чисел, используя встроенные в 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;
}
Чтобы узнать больше об этой функции, перейдите по этой ссылке.
Также обратитесь к алгоритму GCD Дейкстры по следующей ссылке. Работает без деления. Так что это может быть немного быстрее (пожалуйста, поправьте меня, если я ошибаюсь.)
Как насчет следующего, используя евклидов алгоритм по вычитанию:
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]))Вышеуказанная реализация занимает O(n^2) времени. Существуют улучшения, которые могут быть реализованы, но я не смог их опробовать для n чисел.
Здесь ниже приведен исходный код программы на 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;
}Для получения дополнительной информации обратитесь к этому сайту для дальнейшего уточнения.......
Если у вас много небольших чисел, факторизация может быть на самом деле быстрее.
//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);
(работает для некоторых примеров, но не проверено)
Вы можете использовать разделяй и властвуй. Чтобы вычислить gcdN([]), вы делите список на первую половину и вторую половину. если он имеет только один номер для каждого списка. Вы рассчитываете, используя gcd2(n1, n2).
Я только что написал быстрый пример кода. (при условии, что все числа в списке являются положительными значениями)
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
Используйте евклидов алгоритм
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);
//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;
}
Вот метод gcd, который использует свойство gcd(a, b, c) = gcd(a, gcd(b, c)).
Он использует метод gcd BigInteger, так как он уже оптимизирован.
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;
}
Рекурсивный однострочный JavaScript (ES6) для любого количества цифр.
const gcd = (a, b, ...c) => b ? gcd(b, a % b, ...c) : c.length ? gcd(a, ...c) : Math.abs(a);
Это то, что приходит мне в голову в Javascript.
function calculateGCD(arrSize, arr) {
if(!arrSize)
return 0;
var n = Math.min(...arr);
for (let i = n; i > 0; i--) {
let j = 0;
while(j < arrSize) {
if(arr[j] % i === 0) {
j++;
}else {
break;
}
if(j === arrSize) {
return i;
}
}
}
}
console.log(generalizedGCD(4, [2, 6, 4, 8]));
// Output => 2
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... псевдокод которого уже упоминается на dogbane
**
Вот ответ, который я искал. Самый лучший способ найти gcd из n чисел - это использовать recursion.ie gcd(a,b,c)=gcd(gcd(a,b),c). Но я получал тайм-ауты в определенных программах, когда я делал это.
Оптимизация, которая была здесь необходима, заключалась в том, что рекурсия должна решаться с использованием алгоритма быстрого умножения матриц.