如何在 Python 中使用递归查找列表中的序列拆分

Question

我需要为学校完成这个代码。
该程序应该在列表中找到序列拆分的索引。例如，输入是这样的列表

[66, 81, 83, 96, 13, 19, 30, 41, 44, 57]

正确的输出应该是4（序列被中断的数字索引 - 96）

我的函数能够找到拆分，但我不知道如何 return 该拆分的索引。它总是 return 错误答案。

这是我的代码：

def findSplit( list ):

    if len(list)%2 == 0:
        if list[(len(list)//2)-1] == list[0]:
            return 1

        elif list[(len(list)//2)-1]<list[0]:
            return  findSplit(list[:(len(list)//2)]) - len(list)//2

        elif list[(len(list)//2)-1]>list[0]:
            return findSplit(list[(len(list)//2)-1:]) + len(list)//2

    elif len(list)%2 != 0:
        if list[(len(list)//2)]<list[0]:

            return  findSplit(list[:(len(list)//2)+1]) - len(list)//2

        elif list[(len(list)//2)]>list[0]:

            return findSplit(list[(len(list)//2):]) + len(list)//2  

if __name__ == "__main__":

    list = [ 66, 81, 83, 96, 13, 19, 30, 41, 44, 57 ]

    line = input().strip().split()
    if line != []:
        list = []
        for x in line:
            list.append( int( x ) )

    print(findSplit( list ))

Answer 1

首先，也是最重要的一点，不要命名任何变量 list，因为它们会覆盖内置函数。我在下面的代码中将名称更改为 lst。

你的代码很好，除了一个小错误，当你发现分割是前半部分时，你不需要减去另一半的长度。

return findSplit(lst[:(len(list)//2)+1])  # THIS MUCH IS ENOUGH!

这是因为您在前半部分返回索引，因此索引从这一半本身开始。如果你减去，你就会变成负数。在您的特定情况下，您将 4 （正确值）与 5 （另一个拆分的长度）相减，因此您得到错误的答案 -1 即 4-5.

编辑后的代码可以写成

def findSplit( lst ):
    if len(lst)%2 == 0:
        if lst[(len(lst)//2)-1] == lst[0]:
            return 1    
        elif lst[(len(lst)//2)-1]<lst[0]:
            return  findSplit(lst[:(len(lst)//2)])    
        elif lst[(len(lst)//2)-1]>lst[0]:
            return findSplit(lst[(len(lst)//2)-1:]) + len(lst)//2

    elif len(lst)%2 != 0:
        if lst[(len(lst)//2)]<lst[0]:    
            return  findSplit(lst[:(len(lst)//2)+1])     
        elif lst[(len(lst)//2)]>lst[0]:    
            return findSplit(lst[(len(lst)//2):]) + len(lst)//2

现在当我们打印输出时，我们得到了正确的值。

>>> findSplit([ 66, 81, 83, 96, 13, 19, 30, 41, 44, 57 ])
4

_{虽然我不明白你代码的第二部分 ;)}

如何在 Python 中使用递归查找列表中的序列拆分

How to find sequence split in list using recursion in Python

recursion

split

list

sequence

python-3.x