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