微軟面試中的過橋問題

作者：林革

**：《學苑創造·c版》2023年第06期

這是世界著名的微軟公司招聘人才時的兩道面試題。其中蘊含的統籌優化的數學思想方法，應該引起我們的關注和重視。因為培養自身在生產生活實際中尋求合理方案和最優解答的能力，是現代人至關重要的必備素質。

【過橋問題1】小明一家過一座橋，過橋時是黑夜，所以必須有燈。現在小明過橋要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的媽媽要8秒，小明的爺爺要12秒。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點燃後30秒就會熄滅。

問：小明一家如何過橋？

【分析】首先必須明確的是，要節省時間，根據「每次此橋最多可過兩人」的條件限制，可以確定每次是兩人一起過橋。

其次因為有人必須返回照明，所以我們接著可以判斷的是，最好是讓用時最少的小明擔任返回任務，如果難以實現，那也應該讓用時較少的弟弟擔任返回任務。

再就是為了盡可能節省時間，我們應該讓用時較多的人一起過橋，這樣不至於讓這些人分散多增加耗時。比如小明的媽媽和爺爺一起過橋只用時12秒，而如果分開兩次過橋的話，用時8+12＝20秒就會大大增加。

有了這樣前提判斷，那麼接下來我們就不難得到以下優化配置：

（1）小明、弟弟過橋，用時3秒，緊接著小明持燈返回1秒；

（2）爺爺、媽媽過橋，用時12秒，緊接著弟弟持燈返回3秒；

（3）小明、爸爸過橋，用時6秒；緊接著小明持燈返回1秒；

（4）小明、弟弟過橋，用時3秒，一家五人匯合；

一家過橋總用時為3+1+12+

3+6+1+3=29秒，剛好在燈燃盡的範圍內。

【過橋問題2】 u2合唱團的4名成員伯納、艾吉、埃達姆、勞瑞趕往演唱會現場，他們在途中必須跨過一座橋。4個人到達橋的一端，準備過橋時，天已經黑了。他們只有乙隻手電筒，一次最多可以有兩人一起過橋，而且過橋的時候必須持有手電筒，所以，就得有人把手電筒帶來帶去，來回橋的兩端。

注意：手電筒是不能用扔的方式來傳遞的。4個人的步行速度各不同，若兩人同行，則以較慢者的速度為準。

伯納需花1分鐘過橋；艾吉需花2分鐘過橋；埃達姆需花5分鐘過橋；勞瑞需花10分鐘過橋。請問：他們能在17分鐘內過橋嗎？