我是遞回的新手，任務是使用遞回找到陣列中最大元素的位置。這是我的代碼：
def calc(low , high):
print(low, high)
if low == high:
return low
max_1 = calc(low , low high//2)
max_2 = calc(low high//2 , high)
if a[max_1] > a[max_2]:
return max_1
a = [4,3,6,1,9]
print(calc(0 , len(a)))
我究竟做錯了什么？雖然谷歌為我提供了在陣列中查找最大元素的解決方案，但他們都沒有找到最大元素位置的解決方案。提前致謝。
uj5u.com熱心網友回復：
你快到了。兩個小錯誤是：
- 基本情況應該是
low 1 == high - 中點應該是
(low high) // 2
def calc(low , high):
if low 1 == high:
return low
max_1 = calc(low , (low high) // 2)
max_2 = calc((low high) // 2 , high)
if a[max_1] > a[max_2]:
return max_1
else:
return max_2
a = [4,3,6,1,9]
print(calc(0 , len(a)))
## 4
由于錯誤的基本情況和中點，您的解決方案會產生無限遞回。
Whenlow == 0和high == 1, 因為low != high你觸發了兩個呼叫
max_1 = calc(low , low high // 2)
max_2 = calc(low high // 2 , high)
被評估為
max_1 = calc(0, 0) ## This got returned to 0, because low == high
max_2 = calc(0, 1) ## Notice here again low == 0 and high == 1
第二個呼叫max_2 = calc(0, 1)再次觸發另外兩個呼叫，其中一個是再次max_2 = calc(0, 1)。這會觸發無限遞回，這些遞回永遠不會回傳max_2，max_2也永遠不會被評估，因此它后面的行 ( if a[max_1] > a[max_2]: ... ) 也不會。
這就是為什么您應該檢查基本情況low 1 == high而不是low == high. 現在您可以測驗自己并猜測以下代碼是否會生成無限遞回。這次max_2是否會獲得分配給它的回傳值以及它被評估后的行？
def calc(low , high):
if low 1 == high: # Here is changed from your solution
return low
max_1 = calc(low , low high // 2) # Here is same to your solution
max_2 = calc(low high // 2 , high) # Here is same as well
if a[max_1] > a[max_2]:
return max_1
else:
return max_2
如果你得到正確的答案，你就理解了你的錯誤的一半。然后，您可以使用不同的中點并在每個遞回級別列印，以查看它如何影響結果并獲得全面的理解。
uj5u.com熱心網友回復：
我認為這就是你想要做的。您應該將串列切片傳遞給函式 - 這比嘗試傳遞低和高索引要簡單得多，并避免將串列作為全域變數訪問 - 并將中點添加到來自右側的結果索引串列。
def idxmax(l):
if len(l) == 1:
return 0
midpoint = len(l) // 2
a = idxmax(l[:midpoint])
b = idxmax(l[midpoint:]) midpoint
if l[a] >= l[b]:
return a
else:
return b
print(idxmax([4,3,6,1,9]))
這將回傳最大值第一次出現的索引，例如idxmax([4,9,3,6,1,9]) == 1
如果您想通過傳遞索引而不是切片來實作它（通過不制作串列的多個副本可能更有效），您可以這樣做：
def idxmax(l, start=0, end=None):
if end is None:
end = len(l) - 1
if end == start:
return start
midpoint = (start end) // 2
a = idxmax(l, start, midpoint)
b = idxmax(l, midpoint 1, end)
if l[a] >= l[b]:
return a
else:
return b
print(idxmax([4,3,6,1,9]))
uj5u.com熱心網友回復：
我相信任務是只找到最大數量的位置（而不是值本身）。
因此，該函式首先將最后一個值與串列的最大值進行比較，如果為 True，則回傳串列的長度（減一）作為位置。然后它被遞回呼叫到一個較短的串列并再次比較，直到它在串列中只剩下一個值
def calc(lst):
if lst[len(lst) - 1] == max(lst):
return len(lst) - 1
if len(lst) > 1:
return calc(lst[:-1])
print(calc([0, 1, 2, 3, 4, 5, 6])) # 6
print(calc([7, 1, 2, 3, 4, 5, 6])) # 0
print(calc([0, 1, 8, 3, 4, 5, 6])) # 2
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/473273.html
標籤：Python python-3.x 递归 最大限度