ACM PKU 2244 Eeny Meeny Moo 約瑟夫問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2244在沒有明白約瑟夫問題之前,只能用模擬來做.
約瑟夫問題是這樣的:
假設n個人,編號為1到n,排成一個圈,順時針從1開始數字m,數到m的人殺了,剩下的人繼續游戲.活到最后的一個人是勝利者.一般來說需要編程求解最后一個人的編號.
思路是這樣的:
假設當前剩下i個人(i<=n),顯然這一輪m要掛(因為總是從1開始數).經過這一輪,剩下的人是:1 2 3 ... m- 1 m + 1 ... i, 我們將從m+1開始的數映射成1, 則m+2對應2, n對應i - m, 1對應成i - m + 1 m - 1對應i - 1,那么現在的問題變成了已知i - 1個人進行循環報數m,求出去的人的序號。假設已經求出了i- 1個人循環報數下最后一個出去的人的序號X0,那么它在n個人中的序號X1=(X0+ m - 1) % n + 1, 最初的X0=1 ,反復迭代X0和X1可以求出.
簡單約瑟夫問題的解法:










這倒題其實不是完全的約瑟夫問題,而是稍微變了形.呵呵,聰明的讀者自己發現!這一點費了我很久的時間,還害我逃了課被點名...
這道題的我解法是這樣的.






































讀一個數處理一個數, Memory 68K,時間31MS,如果覺得效率不高. 優化的辦法是打表~