萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 找出範圍內所有回文數:演算法優化與基準測試

前言

回文數(Palindromic Number)正讀反讀相同,如 121、9009、12321。本文從暴力枚舉出發,逐步優化至生成法,並以 PHP 實測百萬級範圍效能,展示演算法思維對執行效率的決定性影響。

定義與基本判斷

function isPalindrome(int $n): bool {
    $s = (string)$n;
    return $s === strrev($s);
}

// 或不轉字串(純數學)
function isPalindromeMath(int $n): bool {
    if ($n < 0) return false;
    $original = $n;
    $reversed = 0;
    while ($n > 0) {
        $reversed = $reversed * 10 + $n % 10;
        $n = (int)($n / 10);
    }
    return $original === $reversed;
}

方法一:暴力枚舉(基準)

function findPalindromesBrute(int $min, int $max): array {
    $result = [];
    for ($i = $min; $i <= $max; $i++) {
        if (isPalindrome($i)) $result[] = $i;
    }
    return $result;
}
// 1~1,000,000 耗時:~1.2 秒 (PHP 8.2)

方法二:半數生成法(核心優化)

回文數由前半部決定:
奇數長度:前半部 + 中間位 + 前半部反轉 (如 123 → 12321)
偶數長度:前半部 + 前半部反轉 (如 12 → 1221)

function generatePalindromes(int $min, int $max): array {
    $result = [];
    $minLen = strlen((string)$min);
    $maxLen = strlen((string)$max);

    for ($len = $minLen; $len <= $maxLen; $len++) {
        $halfLen = (int)(($len + 1) / 2); // 含中間位
        $start = 10 ** ($halfLen - 1);
        $end = 10 ** $halfLen - 1;

        for ($half = $start; $half <= $end; $half++) {
            $halfStr = (string)$half;
            $palStr = $len % 2 === 0
                ? $halfStr . strrev($halfStr)
                : $halfStr . strrev(substr($halfStr, 0, -1));
            $pal = (int)$palStr;

            if ($pal < $min) continue;
            if ($pal > $max) break 2; // 跳出雙層迴圈
            $result[] = $pal;
        }
    }
    return $result;
}
// 1~1,000,000 耗時:~0.008 秒(快 150 倍!)

方法三:專案歐拉 Problem 4 風格 — 最大回文乘積

function largestPalindromeProduct(int $minFactor, int $maxFactor): ?int {
    $maxPal = 0;
    for ($i = $maxFactor; $i >= $minFactor; $i--) {
        for ($j = $i; $j >= $minFactor; $j--) { // j 從 i 開始避免重複
            $prod = $i * $j;
            if ($prod <= $maxPal) break; // 後續乘積只會更小
            if (isPalindrome($prod)) $maxPal = $prod;
        }
    }
    return $maxPal ?: null;
}
// 兩位數最大回文乘積:9009 = 91 × 99
// 三位數:906609 = 913 × 993

效能基準測試 (PHP 8.2, 1~10,000,000)

方法耗時記憶體找到數量
暴力枚舉 + strrev12.4 秒2 MB10,998
暴力枚舉 + 數學反轉8.7 秒2 MB10,998
半數生成法0.042 秒0.5 MB10,998
生成器 yield 版0.038 秒0.1 MB10,998

生成器版本(記憶體恆定)

function palindromeGenerator(int $min, int $max): Generator {
    $minLen = strlen((string)$min);
    $maxLen = strlen((string)$max);

    for ($len = $minLen; $len <= $maxLen; $len++) {
        $halfLen = (int)(($len + 1) / 2);
        $start = 10 ** ($halfLen - 1);
        $end = 10 ** $halfLen - 1;

        for ($half = $start; $half <= $end; $half++) {
            $halfStr = (string)$half;
            $palStr = $len % 2 === 0
                ? $halfStr . strrev($halfStr)
                : $halfStr . strrev(substr($halfStr, 0, -1));
            $pal = (int)$palStr;

            if ($pal < $min) continue;
            if ($pal > $max) return;
            yield $pal;
        }
    }
}

// 使用
foreach (palindromeGenerator(1, 1_000_000) as $p) {
    // 即時處理,不佔記憶體
    echo $p . "\n";
}

總結

回文數問題展現了「生成法」優於「過濾法」的經典案例:搜尋空間從 O(N) 降為 O(√N)。PHP 8 的 JIT 對數學運算加速明顯,配合生成器模式,可輕鬆處理億級範圍回文數生成。實際專案中,若需頻繁查詢區間回文數,建議預計算存入資料庫或 Redis 有序集合。

copyright © 萬盛學電腦網 all rights reserved