有N顆石頭排成一圈。一只青蛙坐在第一塊石頭上。青蛙不斷地從石頭到石頭順時針方向跳躍。每次跳躍時，它會以 1 的增量跳過石頭。即，第一次跳躍跳過 0 塊石頭，第二次跳躍跳過 1 塊石頭，第三次跳躍跳過 2 塊石頭，依此類推。任務是，給定石頭的數量 N，找出青蛙是否會到達所有的石頭。
例如：
N=1 ---> 真
N=2 ---> 真 --> 跳躍=(1,2)
N=3 ---> false --> jumps=(1,2,1,1,2,1,1,2,1.....)
N=4 ---> 真 --> 跳躍=(1,2,4,3)
我已經嘗試了 N 的不同值。我所看到的是，如果 N 是 2 的冪，那么所有的石頭都可以到達。此外，如果在訪問所有石頭之前多次訪問任何石頭，那么答案是錯誤的。我找不到觀察結果的理由，因此無法證明。
uj5u.com熱心網友回復：
我認為你正在以錯誤的方式思考這個問題。不要誤會我的意思，做數學分析并得出一個簡單的結果很酷，例如，“當且僅當N是 2 的冪時，所有石頭都可以到達。” （事實上??，我相信那個結果是正確的。）但是你不需要找到那種結果來撰寫一個可以回答這個問題的演算法。
相反，您的演算法可以只模擬青蛙的跳躍（您顯然已經想出了如何去做），并查看它是否擊中了每一塊石頭。唯一棘手的部分是青蛙計劃永遠繼續跳躍，顯然您希望您的演算法在有限的時間內完成。關鍵的見解是青蛙的跳躍序列總是會在一個回圈中結束，所以你只需要繼續模擬這個序列足夠長的時間，以確保你已經進入了回圈并完成了一次通過它。
我們怎么知道呢？
要了解原因，假設我們知道青蛙剛剛從 #i 石跳到#j石。這足以告訴我們青蛙接下來會跳到哪里嗎？答案是“是”；我們不知道青蛙是否認為它跳過了j - i -1 塊石頭 vs. N j - i -1 塊石頭 vs. 2 N j - i -1 塊石頭或諸如此類的東西，但這沒關系，因為它落在的下一個石頭不取決于下一個跳躍是否跳過j - i個石頭 vs. N j - i個石頭 vs. 2N j - i個石頭——這些都是等價的。因此，如果我們知道它的最后一跳，那么我們就知道它的下一跳，如果我們知道它的下一跳，那么我們就知道它之后的一跳，依此類推：所以這一跳足以確定整個其余的石頭序列。
這意味著序列最多可以有N 2 個可能的“狀態”，總是由前一個石頭和下一個石頭決定，其中每個狀態完全決定所有后續狀態。因此，如果您通過至少N 2個狀態來模擬序列，那么您要么只訪問過每個狀態一次，要么至少訪問過某個狀態兩次（根據鴿巢原理），因此您一定已經達到了所有狀態're going to，這意味著你必須降落在你要去的所有石頭上。
這為您提供了O ( N 2 ) 時間和O ( N ) 空間的演算法。
您可以通過以下方式改善這一點
- 跟蹤您已經訪問過哪些狀態，并在發現您已回傳某個狀態時立即終止。
- 跟蹤你已經落在了多少石頭上，一旦你發現你已經落在了所有石頭上，就立即終止。
如果你是對的，這將在O ( N ) 時間內完成，“如果在訪問所有石頭之前多次訪問任何石頭，那么答案是錯誤的”，同時仍然表現正確（并且仍在O ( N 2）時間）如果該理論是錯誤的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/464744.html
標籤：算法
上一篇：Python串列理解優化