Cercare il GCD (massimo comun divisore) di più di 2 numeri interi?

Question

Ho già una funzione che trova il GCD di 2 numeri.

function getGCDBetween($a, $b) 
{ 
    while ($b != 0) 
    { 
     $m = $a % $b; 
     $a = $b; 
     $b = $m; 
    } 
    return $a; 
} 

Ma ora, vorrei estendere questa funzione per trovare il GCD di N punti. Qualche suggerimento ?

Answer 1

C'è una più elegante modo per farlo:

// Recursive function to compute gcd (euclidian method) 
function gcd ($a, $b) { 
    return $b ? gcd($b, $a % $b) : $a; 
} 
// Then reduce any list of integer 
echo array_reduce(array(42, 56, 28), 'gcd'); // === 14 

Se si desidera lavorare con Floating Points, uso approssimazione:

function fgcd ($a, $b) { 
    return $b > .01 ? fgcd($b, fmod($a, $b)) : $a; // using fmod 
} 
echo array_reduce(array(2.468, 3.7, 6.1699), 'fgcd'); // ~= 1.232 

È possibile utilizzare una chiusura i n PHP 5.3:

$gcd = function ($a, $b) use (&$gcd) { return $b ? $gcd($b, $a % $b) : $a; }; 

Answer 2

Si può provare

function gcd($a, $b) { 
    if ($a == 0 || $b == 0) 
     return abs(max(abs($a), abs($b))); 
    $r = $a % $b; 
    return ($r != 0) ? gcd($b, $r) : abs($b); 
} 

function gcd_array($array, $a = 0) { 
    $b = array_pop($array); 
    return ($b === null) ? (int) $a : gcd_array($array, gcd($a, $b)); 
} 

echo gcd_array(array(50, 100, 150, 200, 400, 800, 1000)); // output 50 

Answer 3

ho trovato una soluzione ma sembra un po 'brutto:

1) la verifica per ogni divisore di ogni intero

2) trovare il maggior numero intero in ogni array

function getAllDivisorsOf($n) 
{ 
    $sqrt = sqrt($n); 
    $divisors = array (1, $n); 
    for ($i = 2; ($i < $sqrt); $i++) 
    { 
     if (($n % $i) == 0) 
     { 
      $divisors[] = $i; 
      $divisors[] = ($n/$i); 
     } 
    } 
    if (($i * $i) == $n) 
    { 
     $divisors[] = $i; 
    } 
    sort($divisors); 
    return $divisors; 
} 

function getGCDFromNumberSet(array $nArray) 
{ 
    $allDivisors = array(); 
    foreach ($nArray as $n) 
    { 
     $allDivisors[] = getAllDivisorsOf($n); 
    } 
    $allValues = array_unique(call_user_func_array('array_merge', $allDivisors)); 
    array_unshift($allDivisors, $allValues); 
    $commons = call_user_func_array('array_intersect', $allDivisors); 
    sort($commons); 
    return end($commons); 
} 

echo getGCDFromNumberSet(array(50, 100, 150, 200, 400, 800, 1000)); // 50 

Qualche idea migliore?

Answer 4

È possibile memorizzare i numeri in un array e/o il database e leggere da lì. E poi all'interno di un loop puoi modulare gli elementi dell'array.

Answer 5

Prendere il MCD dei numeri 1 e 2, e quindi il MCD di questo e il numero 3, e così via.

Answer 6

aveva a che fare un po 'di scavo, ma this is what I found.

La gcd di tre numeri può essere calcolato come gcd (a, b, c) = gcd (gcd (a, b ), c), o in qualche altro modo, applicando commutativity e associatività. Questo può essere esteso a qualsiasi numero di numeri.

Si potrebbe usare qualcosa come il seguente:

function multiGCD($nums) 
{ 
    $gcd = getGCDBetween($nums[0], $nums[1]); 

    for ($i = 2; $i < count($nums); $i++) { $gcd = getGCDBetween($gcd, $nums[$i]); } 

    return $gcd; 
} 

Answer 7

È inoltre possibile utilizzare la libreria gmp:

<?php 
    $gcd = gmp_gcd('12', '21'); 
    echo gmp_strval($gcd); 
?>