0

一只青蛙想过河。

河里有3块石头她可以跳过去。

她想在所有可能的路径中选择导致最小最长跳跃的路径。

IE。每条可能的路径都会有一个最长的跳跃。她需要找到最长跳跃最小的路径。

2 个海岸相距 10 并且平行于 y 轴。

每个石头位置由 x 位置的列表 x=[x1,x2,x3] 和 y 位置的列表 y=[y1,y2,y3] 给出。

通过路径中石头列表 x 和 y 中的索引列表返回此路径中最长的跳跃（四舍五入到最接近的整数）和路径本身。

这是我找到最长跳跃的python代码。

我将如何跟踪路径本身？

而且我的代码看起来很笨拙，有 3 个嵌套循环有没有更好/更优雅的方式来编写这段代码？

def longestJump(x, y):
        best = 10
        for i in range(0,3):           
            for j in range(0,3):  
                for k in range(0,3):                
                   # first jump from shore to a stone
                   dist = x[i] 
                   # second jump between stones
                   dist = max(dist, round(math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2))) 
                   # third jump between stones
                   dist = max(dist, round(math.sqrt((x[i]-x[k])**2 + (y[i]-y[k])**2))) 
                   dist = max(dist, round(math.sqrt((x[j]-x[k])**2 + (y[j]-y[k])**2)))
                   # last jump from a stone to the opposite shore 
                   dist = max(dist, 10 - x[j])
                   best = min(dist, best)
        return best
4

2 回答 2

0

除了最终结果外，您不需要取平方根。只需计算“距离平方”并与之进行比较。

也不确定您所说的“圆形”是什么。这可能会产生一个错误。

另外，您不需要从内部循环中跳过所有“i == j”的情况吗？

def longestJump(x, y):
        best = 10
        for i in range(0,3):           
            for j in range(0,3):  
                for k in range(0,3):                
                   # first jump from shore to a stone
                   dist = x[i] 
                   # second jump between stones
                   dist = max(dist, (x[i]-x[j])**2 + (y[i]-y[j])**2)
                   # third jump between stones
                   dist = max(dist, (x[i]-x[k])**2 + (y[i]-y[k])**2) 
                   dist = max(dist, x[j]-x[k])**2 + (y[j]-y[k])**2)
                   # last jump from a stone to the opposite shore 
                   dist = max(dist, 10 - x[j])
                   best = min(dist, best)
        return math.sqrt(best)
于 2015-04-06T00:53:17.383 回答
0

itertools.permutations您可以通过使用on a来简化这三个循环range。range如果您传递长度为 3的 a，它将返回一个三元组。

至于跟踪路径，我认为如果您使用实际if语句将每条路径的最大跳跃长度与您迄今为止看到的最佳长度进行比较会容易得多，而不是使用min. 在 中if，您还可以在保存跳跃长度的同时保存其他信息（例如具有最小最大跳跃的路径）。

def longestJump(x, y):
    best_jump = 10 # infinity
    best_path = ()
    for i, j, k in itertools.permutations(range(3)):           
        jump0 = x[i]                                      # shore to i
        jump1 = sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)     # i to j
        jump2 = sqrt((x[j]-x[k])**2 + (y[i]-y[j])**2)     # j to k
        jump3 = 10 - x[k]                                 # k to far shore
        longest = max(jump0, jump1, jump2, jump3)
        if longest < best_jump:
            best_jump = longest
            best_path = (i, j, k)
    return best_jump, best_path

这总是期望路径使用所有三个石头。如果这不是必需的，您可能需要迭代每个石头子集的排列。我不确定是否有特别简单的方法可以做到这一点，但您可以尝试结合上面itertools.combinations的permutations代码。

于 2015-04-06T01:11:07.663 回答