分而治之算法

我们开始在我的数据结构类中使用除法和征服算法，并且我很难完全理解我应该做什么。下面是基本要求我写一个总结一个数组的程序，但它必须划分并征服它，直到基数为4，我假设意味着将数组以4的块为单位添加，然后添加全部大块在一起。我甚至不知道从哪里开始。我只需要一点解释和理解。老师没有太多帮助。该数组包含一行数字，其中2的幂数小于1000分而治之算法

问题编写一个分而治之的算法，用于求和n个数组中的数组。此算法的基本情况是当子问题的子尺寸小于或等于4时，在这种情况下，您将使用迭代循环来求和子问题的整数。你需要做以下几点：

来源

2013-02-18 shinjuo

我猜你打算写一个递归方法，将数组A分成两个（或多个）每个数组一半的子数组，然后将结果数组按顺序传递给它自己继续分裂，直到你有一个大小为4的数组;那么你可以执行你的总和并返回这4个单位的总和。

来源

2013-02-18 04:30:42 Joe

这就是我的想法，但我不知道如何跟踪所有被拆分的数组。如果我递归地调用120个数字，我最终会得到30个基本大小的数组群 – shinjuo 2013-02-18 04:34:19

这就是递归的要点：你不跟踪。所有的方法都是传递它，然后等待返回值。例如，在'结束'时，当你有4个项目时，说他们的总和为9，然后返回到调用方法。其他4个项目的方法将总和分为13. OK，9 + 13 = 22。这是传递到早期的呼叫。好吧，现在我们沿着另一棵树走下去。它有5个和8个，所以13.22 + 13 = 35。好的，这已经过去了。等等。 – Joe 2013-02-18 04:37:06

哦，我现在明白了。我觉得应该在学校早些时候教这种课。它 – shinjuo 2013-02-18 04:40:32

让我们暂时不要考虑编程语言，想想这个方法是抽象的。

试想一下，如果你是在具有二十叠纸，每个与他们单号的房间。你愿意将所有数字的总和汇总在一起，但你意识到逐一进行是永恒的。所以，你打电话给一个朋友，你们每个人都会拿到十个筹码。你必须做的工作量致电你的朋友下降了一半。

你们都意识到你不会拿着十叠纸来到任何地方，所以你们每个人都会打电话给另一个朋友伸出一只手，让你们四个人一个一个地堆满五堆。合理，但仍然压倒一切。所以每个人都会再次打电话给另一位朋友，并与其他朋友一起将他们的筹码减半 - 让每个人都拥有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-18 04:38:42 Makoto

这是一个好方法。我的书应该真的这样说。 – shinjuo 2013-02-18 04:47:54

分而治之算法

回答

相关问题