ProjectEuler 328 Lowest-cost Search - 拼圖

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

--