題目連結:
本題即是一個典型的「秘書問題」。每個人都有一個分數,「看過」一個人之後換到下一個就不能回來選擇此人。要試著讓選到分數最大的人之機率最大化。
有一個選擇的策略是:
忽略前 r 個人(假設總共有 n 個人),並假設前 r 個人裡面分數最大的為 C 。接著依序看剩下的 n - r 個人,一看到有比 C 大的分數,就選擇該人;如果都沒出現比 C 大的,就不會選到任何人。
本題會隨機生成 n = 9230000 個整數,並根據解題者輸出的 r 值去執行以上的策略。
(輸出一個能使選到最大的數字之機率最大化的 r 值)
雖然可以找到一個數字 r ≒ 3395527,可以使此策略挑到最大數的機率為最大。但是,實際上還是需要靠一些運氣,畢竟大約只有 36.787 % 的機率會成功挑中。
而這個神祕的數字 r 來自於 (n = 9230000) ÷ e 。詳情可以去
維基頁面看相關的公式推導。
(說真的,這題沒有必要放程式碼。真的只是輸出一個數字而已)
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。