问题标签 [divide-and-conquer]

我得到了一块 2^k * 2^k 大小的木板，其中一块瓷砖被随机移除，使其成为一块有缺陷的木板。任务是用“trominos”填充，这是一个由 3 个瓷砖组成的 L 形图形。

解决它的过程并不太难。如果棋盘是 2x2，那么只需要一个 tromino 就可以填满它。对于任何更大的尺寸，它必须被分成四等分（制作四块 2^(k-1) 大小的木板），在中心点放置一个 tromino，因此每个象限都有一个填充瓷砖。之后，可以递归地填充棋盘，直到每个图块都填充有随机颜色的 tromino。

我的主要问题实际上是实现代码。我的 Java 编程技能通常很薄弱，而且我常常很难找到一个开始的地方。唯一要做的工作是在 tiling 类中的 tile 方法中，该方法将有缺陷的板作为输入进行平铺，开始平铺的行和列，以及要填充的瓷砖数量。这是一个家庭作业问题，所以我只是在寻找一些指导或开始的地方 - 任何帮助将不胜感激。

}

}

}

我正在尝试为我学校编程团队的在线评委制作一个 Pascal 程序。程序必须输出 a^b mod c，其中 a、b 和 c 作为输入给出。您不能使用蛮力，因为测试用例都有非常大的数字。

经过一番研究，事实证明我可以使用分而治之的策略。这是我想出的代码：

但是，在线法官返回了错误的答案。有人能指出代码有什么问题吗？

我正在尝试在 Java 中实现 Coreman 的 MergeSort 算法。但它总是给我错误的输出。

排序前：[86, 8, 60, 9, 49, 73, 37, 59, 98, 69]

排序后：[8, 8, 9, 37, 37, 49, 49, 59, 69, 69]

以下是我的代码：

我尝试打印值并调试代码，但无法找出这里出了什么问题。请在这里提出什么问题。

我试图从这个练习中解决第二个问题 b 和 d 子问题：http: //courses.engr.illinois.edu/cs473/sp2010/homework/hw1.pdf

我通过以下方式解决了b：

我的第一个问题是：我的解决方案对问题 2/b 是否正确？我的第二个问题是：我应该在问题 2/d 中做什么？这对我来说有点奇怪。

感谢您的时间和帮助。

首先让我解释一下我要解决的问题。我正在将我的代码与 3rd 方库集成，该库可以进行相当复杂的财务预测。就这个问题而言，假设我有一个黑盒，当我传入 x 时它会返回 y。现在，我需要做的是为给定的输出 (y) 找到输入 (x)。因为我知道最低和最高可能的输入值，所以我编写了以下算法：

1. 定义起始输入范围（最小输入值到最大输入值）
2. 将范围分成两个相等的部分并找到中间值的输出
3. 找出哪一半输出落入
4. 重复步骤 2 和 3，直到范围太小而无法进一步划分

这个算法很好地完成了这项工作，我认为它没有任何问题。但是，有没有更快的方法来解决这个问题？

我知道像mergesort和quicksort这样的算法使用分而治之的范式，但我想知道为什么它可以降低时间复杂度......

为什么通常“分而治之”的算法比非分而治之的算法效果更好？

对于硕士定理T(n) = a*T(n/b) + f(n)，我使用了 3 种情况：

1. 如果a*f(n/b) = c*f(n)对于某个常数c > 1那么T(n) = (n^log(b) a)
2. 如果a*f(n/b) = f(n)那时T(n) = (f(n) log(b) n)
3. 如果a*f(n/b) = c*f(n)对于某个常数c < 1那么T(n) = (f(n))

但是当f(n) = log n或时n*log n， 的值c取决于 n 的值。如何使用大师定理解决递归函数？

我正在尝试用伪代码编写一个分而治之的算法，以找出在给定的 n 个字母字符串中出现了多少个 3 字母模式。

在伪代码中是这样的：

图案固定：XXY

或者

谢谢大家的时间！

给定形式为 的二维平面上的一组 n 个点(x,y)，目标是找到所有点的对数，(xi,yi)并且(xj, yj)使连接两个点的线具有负斜率。

假设没有两个xi具有相同的值。假设所有点都在[-100,100]或某个其他范围内。

我使用贪心算法和回溯算法实现了回溯算法。回溯算法如下：

贪心算法是迭代地选择度数最小的节点，将其放入MIS中，然后将其及其邻居从G中删除。

在边存在的概率为 0.5 的不同图形大小上运行算法后，我凭经验发现与贪心算法相比，反向跟踪算法总是找到更小的最大独立集。这是预期的吗？