ProjectEuler 460 An ant on the move - 拼圖

Una avatar
By Una
at 2014-02-25T08:10

Table of Contents

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),並給出答案至小數後九位。

--
Tags: 拼圖

All Comments

ProjectEuler 459 Flipping game

Emma avatar
By Emma
at 2014-02-25T07:49
459. Flipping game http://projecteuler.net/problem=459 翻棋遊戲是一種兩個人玩的遊戲,需要一塊N乘N的棋盤。 每個格子上都有一面黑一面白的黑白棋一枚。 開始時每一枚棋子都是白色朝上。 一個回合代表將一個符合條件的長方形內的所有棋子都翻轉一次,其條 ...

ProjectEuler 458 Permutations of Project

Hedwig avatar
By Hedwig
at 2014-02-25T07:26
458. Permutations of Project http://projecteuler.net/problem=458 令A為組成project這個單字的字母的集合,亦即A = {c,e,j,o,p,r,t}。 令T(n)由A裡面的元素組成長度為n的字串、並且不包含由project這個單字的5 ...

ProjectEuler 457 A polynomial modulo the squa

Daniel avatar
By Daniel
at 2014-02-25T07:20
457. A polynomial modulo the square of a prime http://projecteuler.net/problem=457 令f(n) = n^2 - 3n - 1。 令p為質數。 令R(p)為符合f(n) mod p^2 = 0的最小正整數n、或是0如果n不 ...

ProjectEuler 456 Triangles containing the ori

Zanna avatar
By Zanna
at 2014-02-25T07:16
456. Triangles containing the origin II http://projecteuler.net/problem=456 定義: x_n = (1248^n mod 32323) - 16161 y_n = (8421^n mod 30103) - 15051 P_n = { ...

ProjectEuler 455 Powers With Trailing Digits

Iris avatar
By Iris
at 2014-02-25T07:11
455. Powers With Trailing Digits http://projecteuler.net/problem=455 令f(n)為比10^9小的最大的正整數x使得n^x的最後9位數亦為x(包含補位的0),或是0 如果這個x不存在。 例如 ‧f(4) = 411728896 (4^ ...