分而治之的连续值的最小和

2024-05-15 • 问答

给出一个随机整数数组

N = [1,...,n]

我需要使用分治法来找到两个连续值的最小和。什么不是我的智商在这里工作？

def minSum(array):
    if len(array) < 2:
        return array[0]+array[1]

    if (len(a)%2) != 0:
        mid = int(len(array)/2)
        leftArray = array[:mid]
        rightArray = array[mid+1:]
        return min(minSum(leftArray),minSum(rightArray),crossSum(array,mid))
    else:
        mid = int(len(array)/2)
        leftArray = array[:mid]
        rightArray = array[mid:]
        return min(minSum(leftArray),array[mid]+array[mid+1])


def crossSum(array,mid):
    return min(array[mid-1]+array[mid],array[mid]+array[mid+1])

主要问题似乎是第一个条件是错误的：如果len(array) < 2，则以下行势必会引发IndexError。另外，未定义a。我假设那是外部作用域中数组的名称，因此这不会引发异常，而只是默默地使用了错误的数组。除此之外，该功能似乎或多或少地起作用（不过，并未对其进行全面的测试。

但是，您实际上并不需要检查数组的长度是奇数还是偶数，您只需在两种情况下使用相同的代码即可，而无需使用crossSum函数。同样，将返回最小和的函数称为maxSum有点令人困惑。如果您确实想要分而治之的方法，请尝试以下操作：

def minSum(array):
    if len(array) < 2:
        return 10**100
    elif len(array) == 2:
        return array[0]+array[1]
    else:
        # len >= 3 -> both halves guaranteed non-empty
        mid = len(array) // 2
        leftArray = array[:mid]
        rightArray = array[mid:]
        return min(minSum(leftArray),minSum(rightArray),leftArray[-1] + rightArray[0])

import random
lst = [random.randint(1,10) for _ in range(20)]
r = minSum(lst)
print(lst)
print(r)

随机示例输出：

[1,5,6,4,1,2,10,7,8,9,9]
3

但是，简单的循环会更适合于该问题：

def minSum(array):
    return min(array[i-1] + array[i] for i in range(1,len(array)))

分而治之的连续值的最小和

yanhua0801 回答：分而治之的连续值的最小和

大家都在问