您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 綜合知識

PHP 經典算法實戰集錦：猴子分蘋果、約瑟夫環、漢諾塔、排序與查找

編輯：PHP 綜合知識

一、五人分蘋果問題（遞歸/迭代數學建模）

題目：5 人偷蘋果，夜間依次醒來將蘋果分 5 份多 1 個扔給猴子，藏走 1/5。次日再分仍多 1 個。求最少蘋果數。

核心邏輯：每輪操作 剩餘 = 當前 - 當前/5 - 1，且每輪前蘋果數模 5 餘 1。逆向思維或暴力遞增搜尋均可。

function findApples() {
    for ($i = 1; ; $i++) {
        $remaining = $i;
        $valid = true;
        // 5 人夜間操作 + 翌日清晨第 6 次驗證
        for ($round = 0; $round < 6; $round++) {
            if ($remaining % 5 !== 1) { $valid = false; break; }
            $remaining = $remaining - ($remaining / 5) - 1;
        }
        if ($valid) return $i;
    }
}
echo findApples(); // 輸出 15621

數學優化：第 n 輪前蘋果數滿足 N ≡ 1 (mod 5)，可推導通項公式 N = 5^6 * k - 4，最小正整數解為 15621。

二、約瑟夫環（猴子大王選拔）

題目：n 只猴子圍圈，從 1 開始報數，報到 m 的出列，循環至剩 1 只為大王。

模擬法（陣列隊列）：

function josephus($n, $m) {
    $monkeys = range(1, $n);
    $index = 0;
    while (count($monkeys) > 1) {
        $index = ($index + $m - 1) % count($monkeys);
        array_splice($monkeys, $index, 1);
    }
    return $monkeys[0];
}
var_dump(josephus(5, 2)); // 輸出 3

數學遞推法（O(n) 時間 O(1) 空間）：

function josephusMath($n, $m) {
    $pos = 0; // 0-based 索引
    for ($i = 2; $i <= $n; $i++) {
        $pos = ($pos + $m) % $i;
    }
    return $pos + 1; // 轉 1-based 編號
}

三、漢諾塔（遞歸經典）

規則：三柱 A/B/C，A 柱 n 個盤（大底小頂），借助 B 移至 C，每次移 1 個，大盤不可壓小盤。

遞歸策略：

將 n-1 個盤從 A 借助 C 移至 B
將第 n 個盤從 A 移至 C
將 n-1 個盤從 B 借助 A 移至 C

function hanoi($n, $src, $aux, $dst) {
    if ($n === 1) {
        echo "Move disk 1 from $src to $dst\n";
        return;
    }
    hanoi($n - 1, $src, $dst, $aux);
    echo "Move disk $n from $src to $dst\n";
    hanoi($n - 1, $aux, $src, $dst);
}
hanoi(3, 'A', 'B', 'C');
// 移動次數 = 2^n - 1，64 層需 1.84e19 次，遠超宇宙壽命

四、排序算法

冒泡排序

function bubbleSort(array $arr): array {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $len - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // 提前終止優化
    }
    return $arr;
}

快速排序

function quickSort(array $arr): array {
    if (count($arr) <= 1) return $arr;
    $pivot = $arr[0];
    $left = $right = [];
    for ($i = 1; $i < count($arr); $i++) {
        $arr[$i] <= $pivot ? $left[] = $arr[$i] : $right[] = $arr[$i];
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}
// 平均 O(n log n)，最壞 O(n²)，非穩定排序

五、查找算法

二分查找（前提：有序陣列）

function binarySearch(array $arr, $target): int {
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $mid = (($low + $high) >> 1); // 位運算避免溢出
        if ($arr[$mid] === $target) return $mid;
        $arr[$mid] < $target ? $low = $mid + 1 : $high = $mid - 1;
    }
    return -1; // 未找到
}

順序查找優化

function linearSearch(array $arr, $target): int {
    foreach ($arr as $i => $val) {
        if ($val === $target) return $i;
    }
    return -1;
}
// 適用於小數據量或無序數據，可結合哨兵優化

六、二維陣列多鍵值排序

function arrayMultiSort(array $data, string $key, int $order = SORT_ASC): array {
    $keys = array_column($data, $key);
    array_multisort($keys, $order, $data);
    return $data;
}
// 使用範例
$users = [
    ['name' => 'A', 'age' => 25],
    ['name' => 'B', 'age' => 20],
];
$sorted = arrayMultiSort($users, 'age', SORT_DESC);