树如下:
(1,1)
/ \
(2,1) (1,2)
/ \ / \
(3,1)(2,3) (3,2)(1,3)
and onward
根是(1,1),树中的所有值都是元组。
Where (x,y) is an element of the tree:
The leftChild will be (x+y,y)
The rightChild will be (x,x+y)
我正在构建一个函数来计算与根 (1,1) 的距离。我无法从头开始构建树,因为这太耗时了。
我发现距离要搜索的元组有 1 个距离,我们必须用最小值减去最大值。我们可以逆向工作。
1 2
(3,2)->(1,2)->(1,1)
(3,2)->(3-2,2) = (1,2)->(1,2-1) = (1,1)
given this is always true:
if x > y:
newtuple = (x-y,y)
distance += 1
else if y > x:
newtuple = (x,y-x)
distance += 1
然而,因为可能的测试用例甚至可以达到 x = 10^50,所以这甚至太慢了。
所以我找到了一个正式的方法来计算 x 与 y 的减法量,反之亦然,使 x > y 变为 y < x,反之亦然,直到 (x,y) = (1,1)。
所以 X - Y(一定次数,比如 z)将使 x 小于 y... X - Y*z = y 通过代数找到 z... z = (Y-X)/(-Y)
到目前为止,这是我的代码:
from decimal import Decimal
import math
def answer(M,F):
M = int(M)
F = int(F)
i = 0
while True:
if M == 1 and F == 1:
return str(i)
if M > F:
x = math.ceil((F-M)/(-F))
M -= F*x
elif F > M:
x = math.ceil((M-F)/(-M))
F -= M*x
else:
if F == M and F != 1:
return "impossible"
i += x
if M < 1 or F < 1:
return "impossible"
return str(i)
而且它没有通过一些未知的测试用例,而是通过了我能想到的所有测试用例。我可能会失败哪些测试用例?我的代码哪里错了?
附注使用 Decimal 模块,只是从代码中删除以提高可读性。
最佳答案
楼层划分允许没有损失,但我认为下面的代码可能有 -1 的错误。
def answer(M,F):
M = int(M)
F = int(F)
i = 0
while True:
if M == 1 and F == 1:
return str(i)
if M > F:
x = F-M
x = x//(-F)
if F < M-(F*x):
x += 1
M -= F*x
elif F > M:
x = M-F
x = x//(-M)
if M < F-(M*x):
x += 1
F -= M*x
else:
if F == M and F != 1:
return "impossible"
i += x
if M < 1 or F < 1:
return "impossible"
return str(i)
关于python - 距离树的根搜索失败,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39626562/