php实现欧几里得算法实现

欧几里得算法简介

欧几里得算法（辗转相除法）用于计算两个非负整数的最大公约数（GCD）。其核心思想是通过反复用较小数除较大数取余，直到余数为0，此时的除数即为最大公约数。

PHP实现方法

以下是用PHP实现欧几里得算法的几种方式：

递归实现

通过函数递归调用自身，直到满足终止条件（余数为0）：

function gcd_recursive($a, $b) {
    if ($b == 0) {
        return $a;
    }
    return gcd_recursive($b, $a % $b);
}

迭代实现

使用循环代替递归，避免递归可能导致的栈溢出问题：

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

扩展欧几里得算法

计算GCD的同时，找到满足贝祖等式（ax + by = gcd(a,b)）的整数x和y：

function extended_gcd($a, $b) {
    if ($b == 0) {
        return ['gcd' => $a, 'x' => 1, 'y' => 0];
    }
    $result = extended_gcd($b, $a % $b);
    return [
        'gcd' => $result['gcd'],
        'x' => $result['y'],
        'y' => $result['x'] - floor($a / $b) * $result['y']
    ];
}

使用示例

调用上述函数并输出结果：

$a = 48;
$b = 18;

echo "递归GCD: " . gcd_recursive($a, $b) . "\n";
echo "迭代GCD: " . gcd_iterative($a, $b) . "\n";

$extended = extended_gcd($a, $b);
echo "扩展GCD: {$extended['gcd']}, x={$extended['x']}, y={$extended['y']}";

注意事项

• 输入参数应为非负整数，负数需先取绝对值。
• 递归实现简洁但可能受限于调用栈深度，大数计算建议使用迭代方式。
• 扩展欧几里得算法在密码学（如RSA）中有重要应用。