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

經典面試題深度解析：27cm 木桿上 5 隻螞蟻的最短/最長離開時間

編輯：PHP 相關知識

題目重述

27cm 細木桿，位置 3、7、11、17、23cm 各有一螞蟻。初始朝向隨機，速度 1cm/s。相遇即掉頭。求所有螞蟻離開木桿的最小時間和最大時間。

核心洞察：接力棒等價原理

螞蟻相遇掉頭 = 交換身份繼續前進。
每隻螞蟻攜帶一根接力棒，碰頭時交換接力棒。
接力棒始終保持原方向勻速前進，最後一根接力棒落地 = 最後一隻螞蟻離開。
與螞蟻身份無關，只取決於初始位置和方向。

數學建模

位置集合：P = {3, 7, 11, 17, 23}
每隻螞蟻到左端(0)距離：L = {3, 7, 11, 17, 23}
到右端(27)距離：R = {24, 20, 16, 10, 4}
每隻螞蟻兩個可能時間：min(L[i], R[i]) 或 max(L[i], R[i])

最小時間：所有螞蟻朝最近端走

每隻螞蟻選擇距離較小的端點：

min(3,24)=3
min(7,20)=7
min(11,16)=11
min(17,10)=10
min(23,4)=4
最大值 = 11 秒

答案：11 秒（位置 11cm 的螞蟻向左走 11cm，或向右走 16cm，取較小者 11s，但受限於木桶效應，全體最快需 11s）

最大時間：所有螞蟻朝最遠端走

max(3,24)=24
max(7,20)=20
max(11,16)=16
max(17,10)=17
max(23,4)=23
最大值 = 24 秒

答案：24 秒（位置 3cm 的螞蟻向右走 24cm）

PHP 完整驗證程序（三種實現）

版本一：暴力模擬（教學理解）

<?php
function simulate(int $rodLen, array $positions, array $directions): int
{
    // directions: -1=左, 1=右
    $ants = array_map(fn($pos, $dir) => ['pos' => $pos, 'dir' => $dir], $positions, $directions);
    $time = 0;
    
    while (!empty($ants)) {
        $time++;
        // 移動
        foreach ($ants as &$ant) {
            $ant['pos'] += $ant['dir'];
        }
        // 碰撞檢測（位置相同 -> 掉頭）
        $posMap = [];
        foreach ($ants as $i => $ant) {
            $posMap[$ant['pos']] ??= [];
            $posMap[$ant['pos']][] = $i;
        }
        foreach ($posMap as $indices) {
            if (count($indices) > 1) {
                foreach ($indices as $i) $ants[$i]['dir'] *= -1;
            }
        }
        // 移除離開的
        $ants = array_filter($ants, fn($a) => $a['pos'] > 0 && $a['pos'] < $rodLen);
    }
    return $time;
}

// 枚舉所有 2^5=32 種初始方向組合
$positions = [3, 7, 11, 17, 23];
$minTime = PHP_INT_MAX;
$maxTime = 0;

for ($mask = 0; $mask < 32; $mask++) {
    $dirs = [];
    for ($i = 0; $i < 5; $i++) {
        $dirs[] = ($mask & (1 << $i)) ? 1 : -1;
    }
    $t = simulate(27, $positions, $dirs);
    $minTime = min($minTime, $t);
    $maxTime = max($maxTime, $t);
}

echo "Min: $minTime, Max: $maxTime\n"; // Min: 11, Max: 24

版本二：接力棒原理 O(n) 直接計算

function calculateTimes(int $rodLen, array $positions): array
{
    $minTime = 0;
    $maxTime = 0;
    foreach ($positions as $pos) {
        $left = $pos;
        $right = $rodLen - $pos;
        $minTime = max($minTime, min($left, $right));
        $maxTime = max($maxTime, max($left, $right));
    }
    return ['min' => $minTime, 'max' => $maxTime];
}

print_r(calculateTimes(27, [3, 7, 11, 17, 23]));
// Array ( [min] => 11 [max] => 24 )

版本三：通用化擴展（任意數量螞蟻、任意長度）

class AntRodSolver
{
    public function solve(int $length, array $positions): array
    {
        // 驗證
        if (count($positions) !== count(array_unique($positions))) {
            throw new InvalidArgumentException('Positions must be unique');
        }
        
        $min = 0;
        $max = 0;
        foreach ($positions as $pos) {
            if ($pos < 0 || $pos > $length) {
                throw new InvalidArgumentException("Position $pos out of range");
            }
            $min = max($min, min($pos, $length - $pos));
            $max = max($max, max($pos, $length - $pos));
        }
        return ['min_time' => $min, 'max_time' => $max];
    }
    
    // 獲取具體最優/最劣方向組合
    public function getOptimalDirections(int $length, array $positions, bool $maximize): array
    {
        $dirs = [];
        foreach ($positions as $pos) {
            $left = $pos;
            $right = $length - $pos;
            if ($maximize) {
                $dirs[] = $left > $right ? -1 : 1; // 朝遠端
            } else {
                $dirs[] = $left < $right ? -1 : 1; // 朝近端
            }
        }
        return $dirs;
    }
}