提问者:小点点

分治法不起作用


我试图用“分而治之”的算法来求数的平均值,但我编写的程序只在元素数为2的幂(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的幂?


共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

每当你试图将一个奇数列表分成两半,然后给两个平均数赋予相等的权重时,都会出现同样的问题。

出于这个原因,我不认为您可以使用这种方法,除非您有一个二次方长度的列表。

编辑:同样值得注意的是,有很多好的方法来获得一个列表的平均值(见前面的这个问题)。 我没有集中讨论这些,因为我相信你的问题主要是问你所使用的特定算法,而不是求平均值。