PTT遊戲區 / puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)

[中譯] ProjectEuler 328 Lowest-cost Search

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (嗶嗶)時間15年前 (2011/03/13 12:32), 編輯推噓16(16推 0噓 36→)
留言52則, 6人參與, 最新討論串1/1
328. Lowest-cost Search http://projecteuler.net/index.php?section=problems&id=328 我們要嘗試用猜數字的方法找出一個從{1, 2,......, n}的集合中挑出來的某數 我們猜的每個數字會花費將與我們所猜的數字相同，然而我們可能得到三種情況： ‧你猜的數字比我所選的還要低　　或是 ‧哇！一模一樣！　　　　　　　　或是 ‧你猜的數字比我所選的還要高 給定一個 n，我們要考慮最佳的策略，也就是考慮在該策略中總和最高，但是所有策略中 總和最小的。 如果 n = 3，最佳策略就是我們猜 2，這樣答案就呼之欲出了，我們花費了 2。 如果 n = 8，我們可能想要一次砍半地猜，於是乎我們可能猜 4，如果某數比 4 大 我們就可能還要額外的一或兩次猜測，第二次我們猜 6，如果某數仍比 6 大 那某數就是 7 或 8，我們第三次就猜 7，最後的花費就是 4 + 6 + 7 = 17 但我們可以發現當 n = 8 時，5 才是最佳選擇。當某數比 5 大，我們只要猜 7 就有答案 然而我們花費 5 + 7 = 12。 如果某數比 5 小，我們第二次會猜 3，如果又比 3 還要小，我們就猜 1，這樣答案就一 定會出來，而總和是 5 + 3 + 1 = 9。 所以在 n = 8 且我們採取第一次猜 5 的策略中的所有情況，總和最多的是 12，但他比起 前一個策略總和 17 還要好，所以這才是 n = 8 的最佳策略。 使 C(n) 為 n 的最佳策略中花費最多的，就像上面所說。 因此 C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12。 100 同樣的，C(100) = 400 且 ΣC(n) = 17575 n=1 200000 請找出 Σ C(n)。 n=1 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.224.1.227
推
03/13 12:49, , 1F
我可以算出來n=1->100 C(n)=17575了
03/13 12:49, 1F
→
03/13 12:50, , 2F
不過 到20000要跑8個小時耶 怎麼要那麼久?
03/13 12:50, 2F
→
03/13 12:52, , 3F
寫錯 20000要5分鐘~~ 200000要八個小時
03/13 12:52, 3F
→
03/13 12:53, , 4F
這就是為何題目出來近7小時沒人解答出來的原因（？）
03/13 12:53, 4F
推
03/13 12:57, , 5F
應該是大家找不到1分鐘的解法吧
03/13 12:57, 5F
→
03/13 12:57, , 6F
應該是有1分鐘內的解法
03/13 12:57, 6F
→
03/13 12:58, , 7F
不過 我的電腦很慢 只有1.7GHz 換快一點的電腦應該可以
03/13 12:58, 7F
→
03/13 12:58, , 8F
3小時以內!
03/13 12:58, 8F
→
03/13 13:00, , 9F
如果跑耗時得程式的話 應該3小時以內就有第1個解答者才對?
03/13 13:00, 9F
推
03/13 13:26, , 10F
好久沒玩這個了0.0
03/13 13:26, 10F
推
03/13 19:23, , 11F
跑了6小時 結果答案是錯的 而題目所給的hint數字我都符合
03/13 19:23, 11F
→
03/13 19:24, , 12F
終於知道這題難在哪了? 難怪現在為止沒人做出來
03/13 19:24, 12F
→
03/13 19:25, , 13F
而且我確定不是溢位的問題 應該是演算法有錯
03/13 19:25, 13F
→
03/13 19:28, , 14F
正確答案應該有12位數 而且比我的答案略小(26359....)
03/13 19:28, 14F
→
03/14 02:44, , 15F
截至目前為止只有兩位做出來
03/14 02:44, 15F
推
03/14 02:44, , 16F
看來我在想的某個問題的答案應該是否定的了...
03/14 02:44, 16F
→
03/14 02:45, , 17F
果然這題不能單純 Divide & Conquer 呢
03/14 02:45, 17F
推
03/14 02:55, , 18F
也就是說大概只能用二維硬做 但這樣需要200K*200K的大表..
03/14 02:55, 18F
→
03/14 02:56, , 19F
以正解應是 12 位數來看 int 還不夠 要 long 的大小
03/14 02:56, 19F
→
03/14 02:56, , 20F
這等於是約 20G * 8 = 160G....= = 我再想想怎麼化簡好了
03/14 02:56, 20F
推
03/16 21:44, , 21F
lol 已經四天了才17人算出來
03/16 21:44, 21F
推
03/16 23:32, , 22F
請問因為worst case的條件較為優先，所以當N=11時"勝出
03/16 23:32, 22F
→
03/16 23:33, , 23F
的應該是 4+6+8=18這個策略對吧。因此11是第一個必須
03/16 23:33, 23F
→
03/16 23:33, , 24F
動用到三步猜測的N。
03/16 23:33, 24F
推
03/17 09:46, , 25F
三步猜測? 如果你是想說最多猜三次的話範例的 N=8 就是啦
03/17 09:46, 25F
推
03/17 09:53, , 26F
另外最多猜測次數的增加不是很穩定
03/17 09:53, 26F
→
03/17 09:54, , 27F
像 N=82 的最佳解最多是 11 次 (最多花費 305, 第一猜是 67)
03/17 09:54, 27F
→
03/17 09:54, , 28F
但 N=83 的最佳解最多只要 9 次 (最多花費310, 第一猜 68)
03/17 09:54, 28F
推
03/17 10:02, , 29F
有做的看要不要對一下小的答案...我的C(1000)=6753
03/17 10:02, 29F
→
03/17 10:02, , 30F
然後 \sum n=1~1000 C(n) = 3120345
03/17 10:02, 30F
→
03/17 10:02, , 31F
這個沒錯的話我就要來想想怎麼把這個大玩意搞小一點了
03/17 10:02, 31F
→
03/17 10:03, , 32F
(我目前的做法是 O(N^3)..這在N=二十萬時會久到我想殺人..)
03/17 10:03, 32F
→
03/17 13:47, , 33F
我也是求出 C(1000)=6753 能再提供大一點的測資嗎，感謝
03/17 13:47, 33F
→
03/17 15:37, , 34F
也對啦，以讓一堆高手苦戰的題目來說divide&conquer
03/17 15:37, 34F
→
03/17 15:38, , 35F
顯得太清純可愛了。仍不瞭問題出在哪 ~攤~
03/17 15:38, 35F
推
03/18 17:37, , 36F
想到之前的最短加法練問題，也是OOXX裝清純。
03/18 17:37, 36F
推
03/19 13:58, , 37F
我也得出了sum n=1~1000 C(n) = 3120345
03/19 13:58, 37F
→
03/19 13:59, , 38F
不過Euler拒絕了我的答案!
03/19 13:59, 38F
推
03/19 14:03, , 39F
現在收斂到了260568268429 不過似乎還不是最佳解
03/19 14:03, 39F
→
03/19 14:29, , 40F
這大概是Euler有史以來最難的題目 比第289題還要難!
03/19 14:29, 40F
推
03/19 23:58, , 41F
解掉了 令人崩潰的題目!!
03/19 23:58, 41F
→
03/19 23:59, , 42F
sum n=1~1000 C(n) = 3120345 是正確的
03/19 23:59, 42F
→
03/20 00:04, , 43F
跑了16秒 果然是有一分鐘內的解法 記憶體也不需要太多
03/20 00:04, 43F
→
03/20 00:09, , 44F
之前錯的答案 開頭4碼竟是正確的!! 差了那麼一點
03/20 00:09, 44F
→
03/20 02:05, , 45F
恭喜
03/20 02:05, 45F
→
03/24 20:14, , 46F
3秒鐘!! 不過論壇裡有人跑到0.25秒
03/24 20:14, 46F
→
03/24 20:15, , 47F
有人需要大一點的測資嗎? sum n=1~5000 C(n) = 103047288
03/24 20:15, 47F
→
03/24 20:15, , 48F
單看一個不準 要看總和才準...
03/24 20:15, 48F
→
03/24 20:16, , 49F
我之前錯的答案 C(5000)是對的 但C(4000)卻錯了
03/24 20:16, 49F
推
03/31 00:43, , 50F
0.046秒!!! 天啊~ 我比它還快了 現在是論壇裡最快的!
03/31 00:43, 50F
→
03/31 00:44, , 51F
可以跑到5億:C(5*10^8) 花了19分鐘又20秒
03/31 00:44, 51F
→
03/31 00:45, , 52F
但我的電腦很慢，如果用新型的電腦 應該可以6分鐘內
03/31 00:45, 52F
‣ 更多 babufong 的文章
文章代碼(AID): #1DV4Zdci (puzzle)
puzzle 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 babufong 的文章
文章代碼(AID): #1DV4Zdci (puzzle)