php实现欧几里得算法实现

欧几里得算法简介

欧几里得算法（Euclidean Algorithm）用于计算两个非负整数的最大公约数（GCD）。其基本原理是通过反复的除法运算，将问题逐步简化，直到余数为0，此时的除数即为最大公约数。

PHP实现欧几里得算法

以下是一个基础的PHP实现示例，包含递归和非递归两种方式：

递归实现

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

非递归实现

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

使用示例

$num1 = 48;
$num2 = 18;

echo "递归方式计算GCD: " . gcd_recursive($num1, $num2) . "\n";
echo "非递归方式计算GCD: " . gcd_iterative($num1, $num2) . "\n";

算法优化

对于较大的整数，可以加入输入验证和优化处理，例如确保输入为非负整数，并在运算前比较大小以减少循环次数：

function gcd_optimized($a, $b) {
    $a = abs($a);
    $b = abs($b);
    if ($a < $b) {
        list($a, $b) = array($b, $a);
    }
    while ($b != 0) {
        list($a, $b) = array($b, $a % $b);
    }
    return $a;
}

注意事项

• 输入应为非负整数，否则需通过abs()函数处理。
• 递归方式在极端情况下可能导致栈溢出，非递归方式更安全。
• 时间复杂度为O(log min(a, b))，效率较高。