← 完整题目索引

PROJECT EULER · #0406

猜谜游戏

Guessing Game

仅题目 · 待解原题 ↗

我们试图通过提问来找到从整数集合 {1,2,,n} 中选出的隐藏数字。 我们询问的每个数字(问题)都会得到三个可能的答案之一:

  • "您的猜测低于隐藏的数字"(并且您会产生 a 的成本),或
  • "您的猜测高于隐藏的数字"(您将承担 b 的成本),或者
  • "是的,就是这样!" (游戏结束)。

给定 nab 的值,最佳策略可以最大限度地降低最坏情况下的总成本

例如,如果 n=5a=2b=3,那么我们可以首先问"2"作为我们的第一个问题。

如果我们被告知 2 高于隐藏数字(成本为 b=3),那么我们确定"1"是隐藏数字(总成本为 3)。
如果我们被告知 2 低于隐藏数字(成本为 a=2),那么我们的下一个问题将是"4"。
如果我们被告知 4 高于隐藏数字(成本为 b=3),那么我们确定"3"是隐藏数字(总成本为 2+3=5)。
如果我们被告知 4 低于隐藏数字(成本为 a=2),那么我们确定"5"是隐藏数字(总成本为 2+2=4)。
因此,此策略实现的最坏情况成本为 5。还可以证明,这是可以实现的最低最坏情况成本。 因此,事实上,我们刚刚描述了给定 nab 值的最优策略。

C(n,a,b) 为给定 nab 值的最佳策略实现的最坏情况成本。

以下是一些示例:
C(5,2,3)=5
C(500,2,3)=13.22073197
C(20000,5,7)=82
C(2000000,5,7)=49.63755955

Fk 为斐波那契数列:Fk=Fk1+Fk2,基本情况为 F1=F2=1
k=130C(1012,k,Fk),并将您的答案四舍五入到小数点后 8 位小数。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。