[問題] 3n+1

看板C_and_CPP作者 (人間失格)時間13年前 (2011/08/23 22:18), 編輯推噓3(3推 0噓 12→)
留言15則, 7人參與, 最新討論串1/1
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) GCC 問題(Question)： http://acm.twbbs.org/problem.php?pid=9043 3n+1 跟uva的那堤大同小異 基本上我輸出的結果都是對的 可是超時了 原本只是照他的algo做 後來改成用一個表存所有我會經過的數字 跟他到最後變成1的時候是多少步 用的是DFS 不過數字大了會當掉後 改成普通的迴圈去紀錄 請問有更好的加速法嗎?? 謝謝^^ 之前的文章有提到可以建表作弊> < 可是我沒用過不太了解見出來的表怎麼弄道我要上船的程式碼裡面 希望高手指點> < -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.200.13
→
08/23 22:56, , 1F
方便放 code ?
08/23 22:56, 1F
剛剛code改掉了 改成迴圈暴力建表 但是 134379這一個數字我跑到幾十萬還沒停下來耶.. 不是應該一定有解嗎? ※ 編輯: flere 來自: 140.114.200.13 (08/23 23:05)
→
08/23 23:12, , 2F
那個數字要用 unsigned long long 去接..
08/23 23:12, 2F
→
08/23 23:21, , 3F
http://codepad.org/RuLgUs5H 至少,大概像這樣.
08/23 23:21, 3F
→
08/23 23:21, , 4F
我要把所有存數字的改成unsigned long long囉?我試試
08/23 23:21, 4F
→
08/23 23:22, , 5F
說不定你不用 table, 改過 ull 就過了,因為 ov 問題.
08/23 23:22, 5F
可以算出來了!! 謝謝幫忙^^ ※ 編輯: flere 來自: 140.114.200.13 (08/23 23:23)
→
08/23 23:32, , 6F
dfs...
08/23 23:32, 6F
推
08/24 09:29, , 7F
我覺得用個表格很對 可以避免重複計算及直接查詢
08/24 09:29, 7F
→
08/24 09:30, , 8F
當然表格開不了那麼大,存不了那麼多數字,那只好超出表格範
08/24 09:30, 8F
→
08/24 09:30, , 9F
圍乖乖重算
08/24 09:30, 9F
→
08/24 09:31, , 10F
另外,UVa 100太容易過的一點就是詢問太弱,1<=[L,R]<=10^6
08/24 09:31, 10F
→
08/24 09:32, , 11F
每筆詢問都掃過一次還會過想起來都覺得很神奇
08/24 09:32, 11F
→
08/24 09:32, , 12F
當然這題是沒有這個困擾XD
08/24 09:32, 12F
→
08/24 10:07, , 13F
建表是正確手段，哪算什麼作弊。 |(
08/24 10:07, 13F
推
08/24 10:19, , 14F
你可以去看看dynamic programming
08/24 10:19, 14F
推
08/24 12:09, , 15F
表不需要太大 原本的algo很快就會收斂到很小的數字了
08/24 12:09, 15F
‣ 更多 flere 的文章
文章代碼(AID): #1EKxRGOf (C_and_CPP)