我一直被 Coursera AlgorithmicBox 的那個問題所困擾。測驗的問題如下。我不知道如何解決這個問題:)
給你 20 個黑白單元格。最左邊的一個是白色的，最右邊的一個是黑色的，所有其他單元格的顏色都被隱藏了。您可以通過單擊來顯示單元格的顏色。您的目標是通過最多 5 次點擊找到兩個不同顏色的相鄰單元格。
uj5u.com熱心網友回復：
由于存在白細胞和黑細胞，我們知道在某個點存在過渡。我們可以點擊第 10 個單元格，如果它是白色的，我們丟棄它左邊的單元格，如果它是黑色的，它右邊的單元格，我們將剩下 11（或 10）個單元格，如果我們使用中間重復這個程序，或者在偶數瓷磚的情況下，中間的兩個單元格之一，我們最多有 6 個單元格。我們再次重復此程序以丟棄另外兩個單元格，剩下 3 個單元格，然后我們檢查最后一個單元格以查看所有 3 個單元格。由于我們知道左右單元格不同，因此前兩個或后兩個不同但相鄰。
我們使用了 4 次點擊。
一般來說，這是類似的二分搜索，具有類似的保證。我們總是檢查 floor[n/2] 個單元格（或 ceil，沒關系）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/478403.html