← 完整题目索引

PROJECT EULER · #0460

行进中的蚂蚁

An Ant on the Move

仅题目 · 待解原题 ↗

在欧几里得平面上,蚂蚁从点 A(0,1) 移动到点 B(d,1),行程为整数 d

每一步,(x0,y0) 点的蚂蚁都会选择满足 x10y11 的格点 (x1,y1) 之一,并以恒定速度 v 直奔 (x1,y1)v 的值取决于 y0y1,如下所示:

  • 如果y0=y1,则v的值等于y0
  • 如果 y0y1,则 v 的值等于 (y1y0)/(ln(y1)ln(y0))

左图是 d=4 的可能路径之一。首先,蚂蚁以 (31)/(ln(3)ln(1))1.8205 的速度从 A(0,1)P1(1,3)。那么所需时间为 5/1.82051.2283
P1(1,3)P2(3,3),蚂蚁以 3 的速度行进,因此所需时间为 2/30.6667。从 P2(3,3)B(4,1),蚂蚁以 (13)/(ln(1)ln(3))1.8205 的速度行进,因此所需时间为 5/1.82051.2283
因此,所需的总时间为 1.2283+0.6667+1.2283=3.1233

右图是另一条路。所需总时间计算如下:0.98026+1+0.98026=2.96052。可以证明,这是 d=4 的最快路径。

0460_ant.jpg

如果蚂蚁选择最快路径,则令 F(d) 为所需的总时间。例如,F(4)2.960516287
我们可以验证 F(10)4.668187834F(100)9.217221972

F(10000)。将您的答案四舍五入到小数点后九位。

题解待补充

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