0

我们开始在我的数据结构课程中使用分而治之的算法，我在完全理解我应该做什么时遇到了很多麻烦。下面是基本上要求我编写一个对数组求和的程序，但它必须划分并征服它，直到基数为 4，我认为这意味着将数组以 4 的块加在一起，然后将所有块在一起。我什至不知道从哪里开始。我只需要一点解释和理解。老师帮不上什么忙。该数组包含一行数字，其数量为 2 的次方，小于 1000

问题 编写一个分治算法，对一个包含 n 个整数的数组求和。该算法的基本情况是子问题的大小小于或等于 4，在这种情况下，您将使用迭代循环来对子问题的整数求和。您需要执行以下操作：

4

2 回答 2

3

我猜您打算编写一个递归方法，将数组 A 拆分为两个（或更多）子数组，每个子数组的一半，然后将生成的数组传递给自身以继续拆分，直到您拥有一个大小为 4 的数组；然后您可以执行求和并返回这 4 个单位的总和。

于 2013-02-18T04:30:42.540 回答
3

让我们暂时不要考虑编程语言，而是考虑抽象的方法是什么。

想象一下，如果你在一个有二十叠纸的房间里，每叠纸上都有一个数字。你愿意做将所有数字的总数汇总在一起的工作，但你意识到逐个计算将花费很长时间。所以，你打电话给一个朋友，你们每个人都得到了十个堆栈来工作。打电话给朋友的工作量减少了一半。

你们都意识到十叠纸是无用的，所以你们每个人都打电话给另一个朋友伸出援助之手，让你们四个人每人拿着五叠纸。有道理，但还是压倒性的。因此，每个人再一次将另一个朋友叫过来并与其他朋友减半 - 让每个人都有 2.5 叠带有数字的纸。

你们都同意这是由一个人完成的合理数量的工作，因此您可以将这些数字加在一起。从最后一组进入你自己的人开始工作，每个人都会返回他们所拥有的数字的总和，直到你得到其他人的总和，而你拥有自己的总和。您将这两者相加并得出结果。

这就是分而治之的原则：您的工作堆栈被划分为一部分工作，然后您可以调用其他方法来完成这些工作。

这是 Python 中的一个伪示例。

def sum(*args):
    if len(args) == 0:  # Nothing in my list, so I'm done
        return 0
    elif len(args) == 1:  # One thing in my list, return that
        return args[0]
    else:  # Too much for me to handle; call in the Calvary!
        return args[0] + sum(args[1:])
于 2013-02-18T04:38:42.780 回答