PHP经典算法练习题（二）：路口通行费、九九乘法表、百钱买百鸡、百内素数筛选

PHP经典算法练习题（二）：路口通行费、九九乘法表、百钱买百鸡、百内素数筛选

四道进阶练习，涉及循环累积、嵌套循环、不定方程求整解、素数判定优化。

题目1：路口通行费（动态扣费模拟）

题目：初始10万现金。现金>5万时每次扣5%，≤5万时每次扣5000。问能通过多少次路口。
模拟循环，直到余额<5000无法支付。

<?php
$money = 100000;
$count = 0;
while ($money >= 5000) {
    if ($money > 50000) {
        $money *= 0.95; // 扣5%
    } else {
        $money -= 5000; // 扣固定额
    }
    $count++;
}
echo "可通过 $count 次路口，剩余金额: $money\n";
?>

注意：浮点数累积误差，金融系统建议用整数(分)或bcmath。

题目2：九九乘法表（嵌套循环控制行列）

<?php
for ($i = 1; $i <= 9; $i++) {
    for ($j = 1; $j <= $i; $j++) {
        echo "$j×$i=" . ($i*$j) . "\t";
    }
    echo "\n";
}
?>

内层循环$j <= $i实现左下三角。Web输出用<br>和 替换换行制表。

题目3：百钱买百鸡（不定方程整数解）

题目：公鸡5文，母鸡3文，雏鸡3只1文。100文买100只，各几只？
方程组：
x + y + z = 100
5x + 3y + z/3 = 100 → 15x + 9y + z = 300
消元得：7x + 4y = 100，x,y,z为非负整数。

<?php
for ($x = 0; $x <= 20; $x++) { // 公鸡最多20只
    for ($y = 0; $y <= 33; $y++) { // 母鸡最多33只
        $z = 100 - $x - $y;
        if ($z % 3 === 0 && 5*$x + 3*$y + $z/3 === 100) {
            echo "公鸡:$x 母鸡:$y 雏鸡:$z\n";
        }
    }
}
?>

四组解：(0,25,75) (4,18,78) (8,11,81) (12,4,84)。可进一步用数论直接求解7x+4y=100。

题目4：100以内素数（试除法优化）

试除法：只需试除到sqrt(n)，且跳过偶数。

<?php
echo "2 "; // 2是唯一偶素数
for ($n = 3; $n <= 100; $n += 2) { // 只遍历奇数
    $isPrime = true;
    for ($j = 3; $j*$j <= $n; $j += 2) { // 试除到sqrt(n)
        if ($n % $j === 0) {
            $isPrime = false;
            break;
        }
    }
    if ($isPrime) echo "$n ";
}
?>

输出：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
进阶：埃拉托斯特尼筛法（O(n log log n)）适合大范围素数生成。

算法复杂度对比