Re: [ACM ] 100 3n+1 problem 如何再改善？
我來分享一下這個最簡單的problem的解法好了
這個雖然是典型的喇賽題，不過對於初入ACM的人來講
是一個很好的磨練腦袋最佳化原理的機會，
因為很多人事實上在玩ACM以前都沒想過opt這碼子事情
我自己的code就不捏他了，我大略提一下我自己寫的這組code考慮到的地方
作者可以想辦法把他給實作出來 :3
1. 事實上你並不需要每次都做出完整的計算。你可以把算過的結果用map存起來
比方說當他餵給你n = 5 那你就被強迫得算出n = 16, 8, 4, 2, 1這些結果
所以事實上你就可以知道n = 5的時候cycle = 5, n = 16時cycle = 4....
所以我們可以把__當作key, __當作value建表，當下次被餵值的時候可以先查表
(__請自行填空 XD)
2. 有些人可能會問，為什麼用map而不是用vector + find，這又是一個最佳化議題
map實作上是用RB Tree作出來的perfect balanced binary tree
這個東西有個特點就是尋找值的時候是O(log n)，而插入值的時候是O(n)
vector的話則是插入值的時候是O(1)好像很棒，可是尋找值的時候卻是O(n)
考量這個case很明顯尋找會遠多於插入，尤其越到後面，尋找的cost會越高
所以我們會使用map(即使他有某方面不太方便的缺點...)而非vector
其實這個還是有更好的解法，就是priority queue，不過這個就先不提了
3. 事實上這個是可以作弊的，我們可以先在自己電腦上先把那張表跑出來
比方說我們可以先跑出一個n = [1, 1000]的時候的cycle表
如果說我們還要再考慮記憶體容量的話，那我們可以取出cycle > 100的n
再另外建一張表(很多不可思議的低記憶體用量+低cpu time就是這樣做出來的)
然後我們可以在考慮一點，我們預先分析(對，別忘了計算不只在ACM上，我們
local端也可以先算)哪些n被跑最多次然後cycle又比較高，那我們可以把他抓出來
然後自己寫一個小程式產生這個table灌到"給ACM吃的程式本體"內
其實除了第三點比較高階以外(事實上這也是很重要的一環)
1 2都是你可以現在就考慮的。
第三點的話基本上我會把他視為作弊 -_- 這個等於是把ACM上的CPU時間先在我們電
腦做掉了，這個說不是作弊有點說不過去 XD
但是事實上很多ACM題目都可以這樣作弊的，而且要作這種弊也是需要高技巧的 :3
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.208.83.250
→
03/20 20:10, , 1F
03/20 20:10, 1F
→
03/20 20:11, , 2F
03/20 20:11, 2F
推
03/20 20:55, , 3F
03/20 20:55, 3F
推
03/20 21:36, , 4F
03/20 21:36, 4F
→
03/20 22:19, , 5F
03/20 22:19, 5F
→
03/20 22:20, , 6F
03/20 22:20, 6F
推
03/20 22:29, , 7F
03/20 22:29, 7F
→
03/20 22:30, , 8F
03/20 22:30, 8F
推
03/20 23:40, , 9F
03/20 23:40, 9F
→
03/20 23:41, , 10F
03/20 23:41, 10F
討論串 (同標題文章)