Python分而治之递归搜索

Question

我的任务很基本，但我还是不知道怎么做。 我收到一个列表，现在我必须检查该列表中是否有0。 基本上，我的职能是：

search(L,0,len(L)-1)

我现在如何将列表拆分为更小的部分，并找出该列表中是否有0

唯一的条件是：

• 递归地
• 以某种形式的分而治之

编辑：这样可以吗

# Name, Vorname:
# Matr.-Nr:


def teile_herrsche(L,startIndex,endIndex):
    if len(L) > 0:
        if L[endIndex] == 0:
            return True
        elif endIndex > -1:
            return teile_herrsche(L,startIndex,endIndex-1)
        else:
            return False
    else:
        return False


L=[1,2,3,4]
print(teile_herrsche(L,0,len(L)-1)) 

Answer 1

我不喜欢质疑这个问题的评论。首先，这显然是一个有特定条件的学校练习，其次，它根本没有回答这个问题。事实上，这个练习是一个如何不教授递归好处的例子。至于回答无序列表中是否有0，则必须在最坏的情况下检查每个元素

现在，给定尝试的问题是，它根本没有分裂。只需将最小索引减少1，即可按相反顺序进行线性搜索。 DAC的原理是将干草堆分成两个（几乎）相等大的干草堆，然后再次使用这些干草堆，直到我们只剩下1个元素（无法进一步分割）。然后将其检查为条件并返回结果。查找一棵二叉树，从根开始直到叶子，中间的每个节点都只是前一个列表的一部分

例如，一个可能的解决方案是这样做

#recursive DAC testing for needle
def findrec(haystack, needle=0):
    #print(haystack)
    return (len(haystack) == 1 and haystack[0] == needle) or \
        (len(haystack) > 1 and (findrec(haystack[:len(haystack)//2]) or \
        findrec(haystack[len(haystack)//2:]))) or False
    
    
L=[5,2,0,5,1,4,5,4,6]
findrec(L)

res:

[5, 2, 0, 5, 1, 4, 5, 4, 6]
[5, 2, 0, 5]
[5, 2]
[5]
[2]
[0, 5]
[0]

True

（要查看列表的划分方式，请取消对内部打印的注释）

如需解释，请返回第一条语句 (len(haystack) == 1 and haystack[0] == needle)仅当haystack正好是一个元素且该元素是针时才解析为True

如果haystack大于1，我们可以通过调用参数[:len(haystack)//2]=>；[0]到[列表的一半向下舍入]和[len(haystack)//2:]=>；[将列表的一半向下舍入]到[结束]

否则，最后一条语句返回False

因为所有3个语句在逻辑上都是or，所以一个True就足以使其他元素的所有False变得无关。由于首先评估针的测试，如果发现针，则不会在该分支中进行进一步细分

---

这是一个扩展版本，使用if/elif/else-

1. 如果输入t为空，则查询q不可能存在于其中。这是基本情况，返回false
2. （感应）t不是空的。如果t有一个元素，如果该元素与查询匹配，则返回true，q
3. （归纳）t不是空的，并且它有多个元素。划分列表以找到mid点，然后重复两个子问题t[0:mid]或t[:mid]

这很容易编码为-

def findrec (t, q):
  if len(t) == 0:
    return False        # (1)
  elif len(t) == 1:
    return t[0] == q    # (2)
  else:
    mid = len(t) // 2   # (3)
    return findrec(t[0:mid], q) or findrec(t[mid:], q)

t = [1,2,3,4,5,6]
print(findrec(t, 0)) # False
print(findrec(t, 3)) # True
print(findrec(t, 6)) # True
print(findrec(t, 9)) # False