Qualcuno può fornire un esempio per trovare il massimo algoritmo di divisore comune per più di due numeri?Massimo comune divisore euclideo per più di due numeri
Credo che il linguaggio di programmazione non contenga.
Qualcuno può fornire un esempio per trovare il massimo algoritmo di divisore comune per più di due numeri?Massimo comune divisore euclideo per più di due numeri
Credo che il linguaggio di programmazione non contenga.
Iniziare con la prima coppia e ottenere il proprio GCD, quindi prendere il GCD di quel risultato e il numero successivo. L'ovvia ottimizzazione è che puoi fermarti se il GCD in esecuzione raggiunge sempre 1. Sto guardando questo per vedere se ci sono altre ottimizzazioni. :)
Oh, e questo può essere facilmente parallelizzato poiché le operazioni sono commutative/associative.
Il codice GCD di 3 numeri può essere calcolato come gcd(a, b, c) = gcd(gcd(a, b), c)
. Puoi applicare l'algoritmo euclideo, l'euclideo esteso o l'algoritmo GCD binario in modo iterativo e ottenere la tua risposta. Sfortunatamente non conosco altri modi (più intelligenti?) Per trovare un GCD.
In Java (non ottimale):
public static int GCD(int[] a){
int j = 0;
boolean b=true;
for (int i = 1; i < a.length; i++) {
if(a[i]!=a[i-1]){
b=false;
break;
}
}
if(b)return a[0];
j=LeastNonZero(a);
System.out.println(j);
for (int i = 0; i < a.length; i++) {
if(a[i]!=j)a[i]=a[i]-j;
}
System.out.println(Arrays.toString(a));
return GCD(a);
}
public static int LeastNonZero(int[] a){
int b = 0;
for (int i : a) {
if(i!=0){
if(b==0||i<b)b=i;
}
}
return b;
}
Ho appena aggiornato una pagina Wiki su questo.
[https://en.wikipedia.org/wiki/Binary_GCD_algorithm#C.2B.2B_template_class]
Ciò richiederà un numero arbitrario di termini. usa GCD (5, 2, 30, 25, 90, 12);
template<typename AType> AType GCD(int nargs, ...)
{
va_list arglist;
va_start(arglist, nargs);
AType *terms = new AType[nargs];
// put values into an array
for (int i = 0; i < nargs; i++)
{
terms[i] = va_arg(arglist, AType);
if (terms[i] < 0)
{
va_end(arglist);
return (AType)0;
}
}
va_end(arglist);
int shift = 0;
int numEven = 0;
int numOdd = 0;
int smallindex = -1;
do
{
numEven = 0;
numOdd = 0;
smallindex = -1;
// count number of even and odd
for (int i = 0; i < nargs; i++)
{
if (terms[i] == 0)
continue;
if (terms[i] & 1)
numOdd++;
else
numEven++;
if ((smallindex < 0) || terms[i] < terms[smallindex])
{
smallindex = i;
}
}
// check for exit
if (numEven + numOdd == 1)
continue;
// If everything in S is even, divide everything in S by 2, and then multiply the final answer by 2 at the end.
if (numOdd == 0)
{
shift++;
for (int i = 0; i < nargs; i++)
{
if (terms[i] == 0)
continue;
terms[i] >>= 1;
}
}
// If some numbers in S are even and some are odd, divide all the even numbers by 2.
if (numEven > 0 && numOdd > 0)
{
for (int i = 0; i < nargs; i++)
{
if (terms[i] == 0)
continue;
if ((terms[i] & 1) == 0)
terms[i] >>= 1;
}
}
//If every number in S is odd, then choose an arbitrary element of S and call it k.
//Replace every other element, say n, with | n−k |/2.
if (numEven == 0)
{
for (int i = 0; i < nargs; i++)
{
if (i == smallindex || terms[i] == 0)
continue;
terms[i] = abs(terms[i] - terms[smallindex]) >> 1;
}
}
} while (numEven + numOdd > 1);
// only one remaining element multiply the final answer by 2s at the end.
for (int i = 0; i < nargs; i++)
{
if (terms[i] == 0)
continue;
return terms[i] << shift;
}
return 0;
};
Un po 'tardi alla festa lo so, ma una semplice implementazione JavaScript, utilizzando descrizione di Sam Harwell dell'algoritmo:
function euclideanAlgorithm(a, b) {
if(b === 0) {
return a;
}
const remainder = a % b;
return euclideanAlgorithm(b, remainder)
}
function gcdMultipleNumbers(...args) { //ES6 used here, change as appropriate
const gcd = args.reduce((memo, next) => {
return euclideanAlgorithm(memo, next)}
);
return gcd;
}
gcdMultipleNumbers(48,16,24,96) //8
Per golang, usando resto
func GetGCD(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func GetGCDFromList(numbers []int) int {
var gdc = numbers[0]
for i := 1; i < len(numbers); i++ {
number := numbers[i]
gdc = GetGCD(gdc, number)
}
return gdc
}
Mentre il la risposta è corretta ed è gentile da parte tua fornire una risposta per una domanda senza risposta, spiegando che la tua risposta sarebbe ottima. È importante che l'OP non solo riceva la risposta corretta ma anche la capisca! – ShellFish
@ShellFish Cosa intendi con una domanda senza risposta? Era originariamente parte di un'altra domanda che era (duplicata) unita a questa? Sono d'accordo che questa risposta deve avere più di una spiegazione. – Teepeemm
Oh scusa, ho trovato questa risposta nella coda di revisione e ho pensato che fosse senza risposta a causa della tua prima frase. Il mio errore, le altre risposte non hanno mostrato lì. - BTW la coda di revisione è una lista di domande che devono essere valutate da pari come le prime risposte (come la tua) o post che necessitano di editing. – ShellFish