406. Guessing Game http://projecteuler.net/problem=406 我們要試著藉由問問題來找出一個包含在 { 1 , 2 , 3 , ... , n } 中的隱藏的正整數， 每當我們問一個數字（問題），我們可能會得到三種不同的結果： ‧你猜的數字比隱藏數字還要低（花費 a 點），或 ‧你猜的數字比隱藏數字還要高（花費 b 點），或 ‧完全正確！（遊戲就結束了） 給定 n, a, b 的值，最佳策略將會把最糟情況的花費降低。 舉個例子，如果 n = 5, a = 2, b = 3, 我們第一次猜測為 2 如果我們被告知 2 高於隱藏數字（花費 3 點），我們便會知道隱藏數字為 1。 如果我們被告知 2 低於隱藏數字（花費 2 點），下一次猜測我們就猜 4。 如果我們被告知 4 高於隱藏數字（花費 3 點），我們便會知道隱藏數字為 3，並花費了 2 + 3 = 5 點。 如果我們被告知 4 低於隱藏數字（花費 2 點），我們便會知道隱藏數字為 5，並花費了 2 + 2 = 4 點。 因此用這招，最糟的情況就是花費 5 點，我們可以發現這是最糟情況中花費最低的策略。 使 C(n,a,b) 為使用最佳策略中最糟情況的花費值，當給定 n, a, b。 這兒有幾個例子： C(5, 2, 3) = 5 C(500, √2, √3) = 13.22073197 ... C(20000, 5, 7) = 82 C(2000000, √5, √7) = 49.63755955 ... 使 F_k 為費氏數列：F_k = F_(k-1) + F_(k-2) 當 F_1 = F_2 = 1。 求Σ_1≦k≦30 C(10^12, √k, √F_k) , 給出答案到小數點後 8 位。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.224.1.35