萬盛學電腦網

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

PHP 實現水仙花數(阿姆斯特朗數)完整算法與優化實踐

水仙花數(Narcissistic Number),又稱阿姆斯特朗數,是指一個 k 位數,其各位數字的 k 次冪之和等於該數本身。最經典的是三位數:153 = 1³ + 5³ + 3³。本文提供 PHP 完整實現、算法優化與擴展應用。

核心算法實現

<?php
/**
 * 阿姆斯特朗數判斷與枚舉
 * 支持任意位數,使用 BCMath 確保大整數精度
 */
class Armstrong {
    /**
     * 判斷指定數字是否為阿姆斯特朗數
     * @param int|string $num 待檢測數字
     * @return bool
     */
    public static function isArmstrong($num): bool {
        $str = (string)$num;
        $k = strlen($str);
        $sum = '0';
        
        foreach (str_split($str) as $digit) {
            // bcpow 支持大整數冪運算,避免浮點精度損失
            $sum = bcadd($sum, bcpow($digit, $k));
        }
        
        return bccomp($sum, $str) === 0;
    }

    /**
     * 枚舉指定範圍內的所有阿姆斯特朗數
     * @param int $min 下界 (含)
     * @param int $max 上界 (含)
     * @return array
     */
    public static function enumerate(int $min = 1, int $max = 100000): array {
        $result = [];
        for ($i = $min; $i <= $max; $i++) {
            if (self::isArmstrong($i)) {
                $result[] = $i;
            }
        }
        return $result;
    }
}

// 使用示例
$numbers = Armstrong::enumerate(1, 100000);
echo "1-100000 內的阿姆斯特朗數:\n";
echo implode(', ', $numbers) . "\n";
// 輸出:1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084

算法複雜度分析

指標複雜度說明
時間複雜度O(n × k)n 為範圍大小,k 為平均位數 (log₁₀n)
空間複雜度O(1) 輔助空間不計輸出陣列
BCMath 開銷O(k²) 乘法大整數運算開銷隨位數增長

優化策略

1. 預計算冪次表 (查表法)

<?php
class ArmstrongOptimized {
    private static $powCache = [];
    
    public static function isArmstrong($num): bool {
        $str = (string)$num;
        $k = strlen($str);
        $sum = 0;
        
        // 構建/復用 0-9 的 k 次冪緩存
        if (!isset(self::$powCache[$k])) {
            self::$powCache[$k] = [];
            for ($d = 0; $d <= 9; $d++) {
                self::$powCache[$k][$d] = (int)bcpow((string)$d, (string)$k);
            }
        }
        
        foreach (str_split($str) as $digit) {
            $sum += self::$powCache[$k][$digit];
        }
        
        return $sum == $num;
    }
}

將冪運算從 O(k²) 降為 O(1) 查表,大幅提升大範圍枚舉速度。

2. 數學剪枝:已知阿姆斯特朗數極稀疏

十進制下僅有 88 個阿姆斯特朗數,最大為 39 位數 (115,132,219,018,763,992,565,095,597,973,971,522,401)。實際應用中可直接硬編碼已知集合:

<?php
const ARMSTRONG_NUMBERS = [
    1,2,3,4,5,6,7,8,9,
    153,370,371,407,
    1634,8208,9474,
    54748,92727,93084,
    548834,
    1741725,4210818,9800817,9926315,
    24678050,24678051,88593477,
    146511208,472335975,534494836,912985153,
    // ... 共 88 個
];

function isArmstrongFast(int $num): bool {
    return in_array($num, ARMSTRONG_NUMBERS, true);
}

3. 並行枚舉 (Swoole/Parallel)

<?php
// Swoole 協程並行枚舉
use Swoole\Coroutine;
use Swoole\Coroutine\Channel;

function parallelEnumerate(int $min, int $max, int $workers = 8): array {
    $chan = new Channel($workers);
    $chunkSize = ceil(($max - $min + 1) / $workers);
    
    for ($w = 0; $w < $workers; $w++) {
        $start = $min + $w * $chunkSize;
        $end = min($start + $chunkSize - 1, $max);
        if ($start > $max) break;
        
        Coroutine::create(function () use ($start, $end, $chan) {
            $local = [];
            for ($i = $start; $i <= $end; $i++) {
                if (ArmstrongOptimized::isArmstrong($i)) $local[] = $i;
            }
            $chan->push($local);
        });
    }
    
    $result = [];
    for ($i = 0; $i < $workers; $i++) {
        $result = array_merge($result, $chan->pop());
    }
    sort($result);
    return $result;
}

擴展應用:廣義阿姆斯特朗數

支持不同進制、不同冪次權重的廣義定義:

<?php
function isGeneralizedArmstrong(string $num, int $base = 10, ?array $powers = null): bool {
    $digits = str_split($num);
    $k = count($digits);
    $powers = $powers ?? array_fill(0, $k, $k);  // 默認各位同冪次
    
    $sum = '0';
    foreach ($digits as $i => $d) {
        $val = (int)$d;  // 假設 base ≤ 10
        $sum = bcadd($sum, bcpow((string)$val, (string)$powers[$i]));
    }
    return bccomp($sum, $num) === 0;
}

總結

水仙花數是展示數字特徵、位運算、大整數處理、算法優化的優秀教學案例。PHP 通過 BCMath 擴展原生支持任意精度運算,結合查表緩存、並行計算、數學剪枝,可高效解決從教學演示到大數驗證的各類場景需求。

copyright © 萬盛學電腦網 all rights reserved