私はすでに2つの数のGCDを見つける機能を持っています。
function getGCDBetween($a, $b)
{
while ($b != 0)
{
$m = $a % $b;
$a = $b;
$b = $m;
}
return $a;
}
しかし、ここで、この関数を拡張して、NポイントのGCDを見つけたいと思います。なにか提案を ?
私はすでに2つの数のGCDを見つける機能を持っています。
function getGCDBetween($a, $b)
{
while ($b != 0)
{
$m = $a % $b;
$a = $b;
$b = $m;
}
return $a;
}
しかし、ここで、この関数を拡張して、NポイントのGCDを見つけたいと思います。なにか提案を ?
これを行うためのよりエレガントな方法があります:
// 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
PHP5.3ではクロージャを使用できます。
$gcd = function ($a, $b) use (&$gcd) { return $b ? $gcd($b, $a % $b) : $a; };
少し掘り下げなければなりませんでしたが、これが私が見つけたものです。
3つの数値の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;
}
1と2のGCDを取得し、次にそのGCDと3のGCDを取得します。
あなたが試すことができます
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 );
?>
番号を配列やデータベースに保存して、そこから読み取ることができます。そして、ループ内で配列要素をモジュール式に分割できます。
これはどこかで再帰によってgcdを計算することがわかりました
function gcd(...$numbers) {
if (count($numbers) > 2) {
return array_reduce($numbers, 'gcd'); // use php's array reduce
}
$r = $numbers[0] % $numbers[1];
return $r === 0 ? abs($numbers[1]) : gcd($numbers[1], $r);
}