algorithm - 递归升序检查

Answer 1

还有基本情况，为什么当我从基本情况中删除相等时我会被堆栈溢出，即 h<l？

假设c=[3, 5]。如果您替换h<=l为h<l, 那么当您计算co(a, 1, 1), 然后mid = 1+0... 然后rl = co (a, 1+1, 1)并a[2]为您提供 stackoverflow。

是怎么a[mid] <= a[mid+1]设计的？？

• 您需要将 subproblem1 的最右侧元素与 subproblem2 的最左侧元素进行比较。在 subproblem1 和 subproblem2 中没有考虑这两个元素的顺序。

• 小心 Python 索引。1）当您将列表拆分为a[l:mid-1]anda[mid+1,h]时，您会省略a[mid-1]and a[mid]。2）当你写的时候，co(c, 0, len(c) - 1)你省略了c（见评论4）的最后一个元素。

您的代码中有一些错误，请参阅我的评论。

def co(a, l, h):
  if h <= l:
    return True
  mid = l + ((h-l)//2)
  cl = co(a, l, mid-1)
  rl = co(a, mid+1, h)
  return rl and cl and a[mid] < a[mid+1] ### Comment1: this misses checking a[mid-1] <= a[mid]

    # how  is a[mid] < a[mid+1] devised ??  ### Comment2: you should use <= rather than <
    # why not a[mid-1] < a[mid] ??
 

#c = [12, 3, 5, 7, 9, 11,12]  ### Comment3: your code returns True for this unordered list!
#c = [3, 5, 7, 9, 11,12]
c = [3, 5]


print(co(c, 0, len(c) - 1))  ### Comment4: len(c)-1 should be len(c) otherwise it's not the whole list

下面，我修复了代码中的列表索引。请注意，测试变为h <= l+1因为在 Python 中列表a[mid:mid+1]包含一个元素。

def co(a, l, h):
  if h <= l+1:
    return True
  mid = l + ((h-l)//2)
  cl = co(a, l, mid)
  rl = co(a, mid, h)
  return rl and cl and a[mid-1] <= a[mid]