问题标签 [divide-and-conquer]

我正在学习数据结构和算法。我参考的书（Sedgwick）使用“寻找最大元素”来说明分而治之的策略。该算法将一个数组中途分成两部分，找到两部分中的最大元素（递归），并返回两者中较大的一个作为整个数组的最大元素。

下面是一个练习题

修改用于查找数组中最大元素的分治程序（程序 5.6），将大小为 N 的数组分成大小为 k = 2^(lg N – 1) 的部分和大小为 N – k 的另一部分（使得至少一个部分的大小是 2 的幂）。

绘制与您的程序在数组大小为 11 时进行的递归调用相对应的树，类似于程序 5.6 中所示的树。

我看到这种二叉树的左子树是完美二叉树，因为第一个子集的大小是 2 的幂。作者希望我从中得到什么暗示？

如何将一个数组最优地划分为两个子数组，使两个子数组中的元素之和相同，否则会报错？

示例 1

给定数组

可以分为

和

每个子数组总和为 105。

示例 2

该数组不能分成两个等和的数组。

作为家庭作业，我应该使用低于 O(n) 的分治法对 1000 位数字实现整数乘法。我应该研究什么算法？

作为家庭作业，我应该对大整数求幂实施分而治之的方法。我知道 Karatsuba 的乘法算法，我可以应用什么分治算法来获得 x^y 的结果，两者都是大整数？

给定一个集合 M，找出是否有一对数 (a,b)，都属于 M，并且 a+b=x，其中 x 是先前指定的参数。该问题应使用 O(n * log n) 中的 Divide et Impera 来解决。可能问题应该分成两个半大小的子问题，然后在 O(n) 中重新组合结果。

我想要给定问题的伪代码或解决它的提示。

我正在为多项式方程寻找递归和非递归分治算法。设 a[0..n-1] 是一个实数数组，其中 n 是 2 的幂。计算 P(x)=a[0]+a[1]x+a[2]x^2+... +a[n-1]x^n-1 对于任何 x。

也许让我先用伪 C++ 代码说明我的情况：

其中 concat 只是连接返回的向量。基本上，我以一种方式对函数进行采样，使得两个保存的函数值之间只有很小的差异。

我对上述方式不满意，因为在每个递归步骤中似乎都有相当多的内存分配（分配两个子向量，然后连接这些子向量和另一个元素）。那段代码必须在我的算法的一部分中运行，这对性能至关重要。一旦upper - lower相当小，评估f将不会花费大量时间。

所以我的问题：

• 您是否看到在所有递归调用中使用相同数据结构并仅填充该向量的当前部分的巧妙方法？（请记住，所需的函数评估数量是未知的）。对此的想法：

  • 使用列表而不是向量。但我觉得内存大修不足以存储双打。
  • 在向量中保留孔并维护另一个向量，说明哪些条目已填充。递归调用的结束移动条目，以便subsamples 和newval. 但是现在我通过为第二个向量转移额外的工作来切换复制——这可能是个坏主意。

• 您是否看到完全摆脱递归的方法？但是，为了正确起见，我使用上述分而治之的模式很重要。该函数f大量使用了上限和下限，并由此获得了相当大的性能。

谢谢你的想法。

根据 Space_C0wb0y 的要求，让我尝试重新表述我的问题。也许第一个解释不是很清楚。

我有一些函数（在数学意义上）我想在给定的时间间隔内采样（例如在某些点进行评估）。

假设区间为 [0,100]。我知道函数值在 0 和 100。也许是f(0)=0和f(100) = 40。现在我在间隔中点（即 50）处评估函数。比如说，我的函数返回f(50)=10. 因为f(0)-f(50) <= 10，我不需要区间 [0,50] 中的更多样本。但是，我需要进一步计算区间 [50,100]。因此，在下一个（递归）步骤中，我评估f(75). 现在递归地重复上面的逻辑。

最后，我想（两个）向量给我带有相应参数的函数值，如下所示：

我正在寻找递归构建这些向量的最佳（性能最高）方法。

希望这可以澄清事情。

我试图从客户端向服务器发送一个 unix 命令，等待服务器执行它然后将结果返回给客户端。

我设法使连接正常工作，但我不知道如何继续。这甚至是我应该走的方向吗？

感谢帮助，ty bando

我们想在会议研讨会上展示新的 JDK7 Fork/Join 框架。为此，我们目前正在寻找一个有趣的例子，该框架可以做什么。

有一些很明显的，比如排序或矩阵计算，但还有更有趣的人们喜欢做的事情。例如，我们在 java 网站上发现了图像模糊，或者可能是天气预报或类似的东西？

如果域不太复杂，那么问题可以在几天内解决。

非常感谢任何输入。有什么想法或经验吗？

我想为给定的整数输入数组找到一个非空的连续子数组，它可以有重复的值。我尝试了分而治之的方法来找到一个数组的最大连续子数组，它按预期返回不同的结果。请在下面找到代码。

此代码将结果返回为2000005400。MCS 的非递归版本返回一个不同的结果，即2000010721，它是从 {1-94} 找到的。我无法弄清楚原因。请让我知道代码中是否存在错误。