我正在嘗試制作“一維最短距離演算法”。
但是，我對遞回情況感到困惑。我不知道如何在遞回呼叫后取回值（第 14 和 15 行）。如何修復以下代碼？
def recCPairDist(points):
if len(points) == 1:
return 0
elif len(points)== 2:
abs(points[1]-points[0])
#how do i assign the result final value back to "leftDist rightDist"
#since its a recurisive, the result can be more than 1, should i store all the result in a list first?
#then get the min(list)?
else:
mid = len(points) // 2
first_half = points[:mid]
second_half = points[mid:]
leftDist = recCPairDist(first_half)
rightDist = recCPairDist(second_half)
midDist = abs(second_half[0] - first_half[1]) #i dont think this is correct since i didnt consider the recursion
return min(leftDist,rightDist,midDist)
def cPairDist(points):
points.sort()
return recCPairDist(points)
P1 = [7, 4, 12, 14, 2, 10, 16, 6]
cPairDist(P1)
P1 的預期結果應該是 1，因為最短距離在 7 到 6 之間。
uj5u.com熱心網友回復：
你真的很親近！你必須做三件事：
- 對于只有一點需要考慮的情況，你不應該回傳
0。例如，對于陣列[3, 6, 9]，答案是 3，但您給定的基本情況將回傳0。這是因為對于奇數長度的陣列，其中一個結果子陣列的長度為 1，并且當您從每個遞回呼叫回傳時，零回傳值將傳播。 - 您需要使用關鍵字顯式回傳基本情況
abs(points[1]-points[0])中的值。len == 2return - 對于您的遞回情況，最小差異必須在左半部分的兩個連續元素之間，右半部分的兩個連續元素之間，或者前半部分的最后一個元素和后半部分的第一個元素之間（兩個連續元素在原始陣列，但沒有包含在兩個遞回案例中）。所以，你
midDist應該計算這個值。
這是解決所有這三個問題的代碼片段：
def recCPairDist(points):
if len(points) == 1:
return float('inf')
elif len(points)== 2:
return abs(points[1]-points[0])
else:
mid = len(points) // 2
first_half = points[:mid]
second_half = points[mid:]
leftDist = recCPairDist(first_half)
rightDist = recCPairDist(second_half)
midDist = abs(first_half[-1] - second_half[0])
return min(leftDist,rightDist,midDist)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/461003.html