php 实现算法

PHP 是一种广泛使用的服务器端脚本语言，也可以用于实现各种算法。以下是一些常见的算法实现方法和示例：

排序算法

冒泡排序是一种简单的排序算法，通过重复地遍历要排序的列表，比较相邻的元素并交换它们的位置。

function bubbleSort($array) {
    $length = count($array);
    for ($i = 0; $i < $length - 1; $i++) {
        for ($j = 0; $j < $length - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

查找算法

二分查找是一种高效的查找算法，适用于已排序的数组。

function binarySearch($array, $target) {
    $left = 0;
    $right = count($array) - 1;
    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        if ($array[$mid] == $target) {
            return $mid;
        }
        if ($array[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return -1;
}

递归算法

递归是一种通过调用自身来解决问题的方法。斐波那契数列是一个经典的递归例子。

function fibonacci($n) {
    if ($n <= 1) {
        return $n;
    }
    return fibonacci($n - 1) + fibonacci($n - 2);
}

动态规划

动态规划是一种分阶段求解问题的方法，适用于具有重叠子问题和最优子结构性质的问题。背包问题是一个典型的动态规划问题。

function knapSack($W, $wt, $val, $n) {
    $dp = array_fill(0, $n + 1, array_fill(0, $W + 1, 0));
    for ($i = 1; $i <= $n; $i++) {
        for ($w = 1; $w <= $W; $w++) {
            if ($wt[$i - 1] <= $w) {
                $dp[$i][$w] = max($val[$i - 1] + $dp[$i - 1][$w - $wt[$i - 1]], $dp[$i - 1][$w]);
            } else {
                $dp[$i][$w] = $dp[$i - 1][$w];
            }
        }
    }
    return $dp[$n][$W];
}

图算法

Dijkstra 算法用于寻找图中两点之间的最短路径。

function dijkstra($graph, $start) {
    $dist = [];
    $visited = [];
    $vertices = array_keys($graph);
    foreach ($vertices as $vertex) {
        $dist[$vertex] = INF;
        $visited[$vertex] = false;
    }
    $dist[$start] = 0;
    for ($i = 0; $i < count($vertices); $i++) {
        $minDist = INF;
        $u = null;
        foreach ($vertices as $vertex) {
            if (!$visited[$vertex] && $dist[$vertex] < $minDist) {
                $minDist = $dist[$vertex];
                $u = $vertex;
            }
        }
        if ($u === null) break;
        $visited[$u] = true;
        foreach ($graph[$u] as $v => $weight) {
            if ($dist[$u] + $weight < $dist[$v]) {
                $dist[$v] = $dist[$u] + $weight;
            }
        }
    }
    return $dist;
}

字符串匹配算法

KMP 算法用于高效地查找字符串中的子串。

function computeLPS($pattern) {
    $lps = array_fill(0, strlen($pattern), 0);
    $len = 0;
    $i = 1;
    while ($i < strlen($pattern)) {
        if ($pattern[$i] == $pattern[$len]) {
            $len++;
            $lps[$i] = $len;
            $i++;
        } else {
            if ($len != 0) {
                $len = $lps[$len - 1];
            } else {
                $lps[$i] = 0;
                $i++;
            }
        }
    }
    return $lps;
}

function KMPSearch($text, $pattern) {
    $lps = computeLPS($pattern);
    $i = $j = 0;
    while ($i < strlen($text)) {
        if ($text[$i] == $pattern[$j]) {
            $i++;
            $j++;
            if ($j == strlen($pattern)) {
                return $i - $j;
            }
        } else {
            if ($j != 0) {
                $j = $lps[$j - 1];
            } else {
                $i++;
            }
        }
    }
    return -1;
}

数学算法

快速幂算法用于高效地计算大数的幂。

function fastPower($base, $exponent) {
    $result = 1;
    while ($exponent > 0) {
        if ($exponent % 2 == 1) {
            $result *= $base;
        }
        $base *= $base;
        $exponent = floor($exponent / 2);
    }
    return $result;
}

以上示例展示了 PHP 中常见算法的实现方式，可以根据具体需求进行修改和优化。