[中譯] ProjectEuler 460 An ant on the move

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者tml (流刑人形)時間12年前 (2014/02/25 08:10)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/1

460. An ant on the move http://projecteuler.net/problem=460 一隻螞蟻想從歐氏平面上的點A(0, 1)移動到點B(d, 1)。在每次移動，螞蟻從(x_0, y_0)直線移動到格子點(x_1, y_1)的速率由y_0和y_1決定。（其中x_1≧0且y_1≧1） ‧如果y_0 = y_1則速率v即為y_0。 ‧如果y_0 ≠ y_1則速率v則為(y_1 - y_0) / (ln(y_1) - ln(y_0))。下圖的左圖是d = 4的一種可能的移動方式。 http://projecteuler.net/project/images/p_460_ant.jpg

螞蟻從A(0, 1)到P_1(1, 3)的速率是(3 - 1) / (ln(3) - ln(1)) ≒ 1.8205，所需的時間則為√5 / 1.8205 ≒ 1.2283。以此類推，從P_1(1, 3)到P_2(3, 3)的速率為3，時間為2 / 3 ≒ 0.6667。從P_2(3, 3) 到B(4, 1)的速率為(1 - 3) / (ln(1) - ln(3)) ≒ 1.8205，時間為 √5 / 1.8205 ≒ 1.2283。故總共花費的時間為1.2283 + 0.6667 + 1.2283 = 3.1233。右圖是另一種移動方式，總共花費的時間是0.98026 + 1 + 0.98026 = 2.96052。可以證明這是d = 4時的最短時間路線。令F(d)為螞蟻選擇最短時間路線所花費的總移動時間。例如，F(4) ≒ 2.960516287。同時亦可驗證F(10) ≒ 4.668187834以及F(100) ≒ 9.217221972。請求出F(10000)，並給出答案至小數後九位。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 129.2.129.154 ※ 編輯: tml 來自: 129.2.129.154 (02/27 09:14)