使用递归查找最大元素
Find max element using recursion
我是递归的新手,任务是使用递归找到数组中最大元素的位置。这是我的代码:
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)))
我做错了什么?
虽然 google 为我提供了在数组 none 中查找最大元素的解决方案,但其中有找到最大元素位置的解决方案。提前致谢。
我认为任务只是找到最大数量 的 POSITION(而不是值本身)。
因此,函数首先将最后一个值与列表的最大值进行比较,如果为真,则returns列表的长度(减一)作为位置。然后它被递归地调用到一个较短的列表并再次比较,直到它在列表中只剩下一个值
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
我想这就是你想要做的。您应该将列表切片传递给函数 - 这比尝试传递低索引和高索引要简单得多,并且避免将列表作为全局变量访问 - 并将中点添加到来自右侧的结果索引列表。
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]))
此returns 第一个 出现最大值的索引,例如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]))
你快到了。两个小错误是:
- 基本情况应为
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
由于错误的基本情况和 mid-point.
,您的解决方案会生成无限递归
当low == 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)
。这会触发无限递归,永远不会 returns 回到 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
如果您答对了,那么您就已经了解了错误的一半。然后你可以尝试不同的 mid-point 并在每个递归级别打印以查看它如何影响结果并获得全面的理解。
我是递归的新手,任务是使用递归找到数组中最大元素的位置。这是我的代码:
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)))
我做错了什么? 虽然 google 为我提供了在数组 none 中查找最大元素的解决方案,但其中有找到最大元素位置的解决方案。提前致谢。
我认为任务只是找到最大数量 的 POSITION(而不是值本身)。
因此,函数首先将最后一个值与列表的最大值进行比较,如果为真,则returns列表的长度(减一)作为位置。然后它被递归地调用到一个较短的列表并再次比较,直到它在列表中只剩下一个值
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
我想这就是你想要做的。您应该将列表切片传递给函数 - 这比尝试传递低索引和高索引要简单得多,并且避免将列表作为全局变量访问 - 并将中点添加到来自右侧的结果索引列表。
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]))
此returns 第一个 出现最大值的索引,例如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]))
你快到了。两个小错误是:
- 基本情况应为
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
由于错误的基本情况和 mid-point.
,您的解决方案会生成无限递归当low == 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)
。这会触发无限递归,永远不会 returns 回到 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
如果您答对了,那么您就已经了解了错误的一半。然后你可以尝试不同的 mid-point 并在每个递归级别打印以查看它如何影响结果并获得全面的理解。