Suchen Sie nach der GCD (größter gemeinsamer Teiler) von mehr als 2 ganzen Zahlen?

Question

Ich habe bereits eine Funktion, die den GCD von 2 Nummern findet.

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

Aber jetzt möchte ich diese Funktion erweitern, um die GCD von N Punkten zu finden. Irgendein Vorschlag ?

Answer 1

Es ist ein eleganter Weg, dies zu tun:

// 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 

Wenn Sie mit floating Punkte arbeiten, verwenden Annäherung:

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 

Sie können eine Schließung i n PHP 5.3:

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

Answer 2

Sie können versuchen,

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

ich eine Lösung gefunden, aber es sieht ein bisschen hässlich:

1) für jeden Divisor jeder Integer-Überprüfung

2) finden die größere ganze Zahl in jeder Arrays

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 

Eine bessere Idee?

Answer 4

Sie können die Zahlen in einem Array und/oder einer Datenbank speichern und von dort lesen. Und dann können Sie innerhalb einer Schleife die Array-Elemente modular teilen.

Answer 5

Nehmen Sie die GCD der Nummern 1 und 2, und dann die GCD dieser und Nummer 3, und so weiter.

Answer 6

Musste ein bisschen graben, aber this is what I found.

Die GCD von drei Zahlen können durch Anwendung commutativity und Assoziativität als ggT (a, b, c) = gcd (ggT (a, b), c), oder in irgendeiner anderen Weise berechnet werden. Dies kann auf beliebig viele Nummern erweitert werden.

Sie so etwas wie die folgende verwenden:

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

Sie können auch die gmp Bibliothek verwenden:

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