У меня уже есть функция, которая находит GCD из 2 чисел.
function getGCDBetween($a, $b) { while ($b != 0) { $m = $a % $b; $a = $b; $b = $m; } return $a; } Но теперь я хотел бы расширить эту функцию, чтобы найти GCD из N точек. Любое предложение ?
Существует более элегантный способ сделать это:
// 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
Если вы хотите работать с плавающими точками, используйте аппроксимацию:
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
Вы можете использовать закрытие в PHP 5.3:
$gcd = function ($a, $b) use (&$gcd) { return $b ? $gcd($b, $a % $b) : $a; };
Придется немного копать, но это то, что я нашел .
Gcd из трех чисел можно вычислить как gcd (a, b, c) = gcd (gcd (a, b), c) или каким-либо другим способом, применяя коммутативность и ассоциативность. Это можно расширить до любого числа чисел.
Вы можете использовать что-то вроде следующего:
function multiGCD($nums) { $gcd = getGCDBetween($nums[0], $nums[1]); for ($i = 2; $i < count($nums); $i++) { $gcd = getGCDBetween($gcd, $nums[$i]); } return $gcd; }
Возьмите GCD чисел 1 и 2, а затем GCD этого и числа 3 и т. Д.
Можешь попробовать
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
Я нашел решение, но выглядит немного уродливо:
1) проверка каждого делителя каждого целого числа
2) найти большее целое число в каждом массиве
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
Любая лучшая идея?
Вы можете хранить номера в массиве и / или базе данных и читать оттуда. А затем в цикле вы можете модульно разделить элементы массива.
Вы также можете использовать библиотеку gmp :
<?php $gcd = gmp_gcd( '12', '21' ); echo gmp_strval( $gcd ); ?>