分治算法不起作用

Question

我试图用“分而治之”算法来求解数字的平均值，但我编写的程序仅在元素数为二的幂（2，4，8等）时才有效

代码是用python编写的，如下所示

def averageDyC(ini, end, notes):
    if (ini == end):
        return notes[ini]

    mid = int((ini + end) / 2)

    x = averageDyC(ini, mid, notes)
    y = averageDyC(mid + 1, end, notes)
    
    return float((x + y) / 2)
    
notes = [1, 4, 7, 8, 9, 2, 4]
average = averageDyC(0, len(notas) - 1, notes)

此代码显示3,75，但正确的平均值为3,5

如何更改此代码以允许元素数为2的不同幂

Answer 1

实际上，我不认为这种方法能找到列表的平均值

让我们看一个由三个数字组成的列表：[1,2,3]

显然，平均值是2

但是，如果我们将列表一分为二，则得到[1,2]和[3]。它们各自的平均数分别为1.5和3

如果我们把这两个加起来，然后把结果除以2，我们得到2.25

这是因为1.5是两个数字的平均值，3是一个数字的平均值，所以我们真的应该用2加权1.5，用1加权3

所以正确的总和应该是(2(1.5) + 1(3)) / 3

当您尝试将奇数列表分成两半，然后给两个平均值相等的权重时，就会出现同样的问题

出于这个原因，我不认为你可以使用这种方法，除非你有一个两倍长度的列表

编辑：还值得注意的是，有许多好方法可以获得列表的平均值（请参见此previous question）。我没有把重点放在这些问题上，因为我相信你的问题主要是问你所使用的具体算法，而不是实际找到平均值