在本文中，我们将讨论分而治之技术的作用以及如何使用 DAC 技术方法解决问题。在本节中，我们将讨论以下主题。
- DAC简介。
- DAC技术下的算法。
- DAC算法的递归关系。
- 使用DAC技术的问题。
分而治之 这种技术可以分为以下三个部分：
- 划分：这涉及将问题划分为更小的子问题。
- 征服：通过递归调用解决子问题，直至解决。
- 组合：将子问题组合起来，得到整个问题的最终解决方案。
- 快速排序是一种排序算法。该算法选择一个主元元素并重新排列数组元素，以便所有小于所选主元元素的元素都移动到主元的左侧，而所有大于的元素都移动到右侧。最后，算法对主元元素左右两侧的子数组进行递归排序。
- 归并排序也是一种排序算法。该算法将数组分为两半，对它们进行递归排序，最后合并已排序的两半。
- 最近的点对问题是在 xy 平面上的一组点中找到最近的点对。通过计算每对点的距离并比较距离以找到最小值，可以在 O(n^2) 时间内解决该问题。分而治之算法可以在 O(N log N) 时间内解决问题。
- 施特拉森算法是一种有效的两个矩阵相乘算法。两个矩阵相乘的简单方法需要 3 个嵌套循环，时间复杂度为 O(n^3)。Strassen 的算法在 O(n^2.8974) 时间内将两个矩阵相乘。
- Cooley-Tukey 快速傅立叶变换 (FFT) 算法是最常见的 FFT 算法。它是一种分而治之的算法，运行时间为 O(N log N)。
- Karasuba 快速乘法算法最多可以完成两个n位数字的乘法
什么不符合分而治之的条件： 二分查找是一种搜索算法。在每个步骤中，算法都会将输入元素 x 与数组中中间元素的值进行比较。如果值匹配，则返回中间的索引。否则，如果 x 小于中间元素，则该算法针对中间元素的左侧递归，否则针对中间元素的右侧递归。
与普遍的看法相反，这不是分而治之的例子，因为每一步只有一个子问题（分而治之要求必须有两个或更多子问题），因此这是一种减少和解决的情况征服。
分而治之算法 ：
DAC(a, i, j)
{
if(small(a, i, j))
return(Solution(a, i, j))
else
mid = divide(a, i, j) // f1(n)
b = DAC(a, i, mid) // T(n/2)
c = DAC(a, mid+1, j) // T(n/2)
d = combine(b, c) // f2(n)
return(d)
}
|
DAC 算法的递归关系： 这是上述程序的递归关系。
O(1) if n is small T(n) = f1(n) + 2T(n/2) + f2(n) |
示例： 查找给定数组中的最大和最小元素。 输入： { 70, 250, 50, 80, 140, 12, 14 } 输出：给定数组中的最小数字为：12 给定数组中的最大数字为：250
方法：从给定数组中查找最大和最小元素是分而治之的应用。在这个问题中，我们将找到给定数组中的最大和最小元素。在这个问题中，我们使用分而治之的方法（DAC），它具有分治、分治和组合三个步骤。
对于最大值： 在这个问题中，我们使用递归方法来查找最大值，我们将看到只剩下两个元素，然后我们可以轻松使用条件，即 if(a[index]>a[index+1].) 在程序行中，a[index]和a[index+1])条件将确保左侧只有两个元素。
if(index >= l-2)
{
if(a[index]>a[index+1])
{
// (a[index]
// 现在，我们可以说最后一个元素将是给定数组中的最大值.
}
else
{
//(a[index+1]
// 现在，我们可以说最后一个元素将是给定数组中的最大值。
}
}
|
在上述条件中，我们检查了左侧条件以找出最大值。现在，我们将看到右侧条件来找到最大值。 用于检查数组当前索引右侧的递归函数。
max = DAC_Max(a, 索引+1, l); // 递归调用 |
现在，我们将比较条件并检查给定数组当前索引处的右侧。 在给定的程序中，我们将实现此逻辑来检查当前索引右侧的条件。
// 右边的元素将是最大的。 if(a[index]>max) 返回 a[index]; // max 将是给定数组中的最大元素。 否则 返回最大值； } |
对于最小值： 在这个问题中，我们将实现递归方法来找到最小值。在给定的数组中。
int DAC_Min(int a, int index, int l)
//递归调用函数求最小值。在给定的数组中。
if(index >= l-2)
// 检查左侧是否有两个元素，
然后我们可以轻松找到给定数组中的最小元素。
{
// 这里我们将检查条件
if(a[index]<a[index+1])
return a[index];
否则
返回a[索引+1]；
}
|
现在，我们将检查给定数组右侧的条件。
// 递归调用给定数组的右侧。 min = DAC_Min(a, 索引+1, l); |
现在，我们将检查条件以找到右侧的最小值。
// 右侧元素为最小值 if(a[index]<min) return a[index]; // 这里 min 将是给定数组中的最小值。 否则 返回min ； |
Java代码
// 演示除法和
//征服算法的 Java 代码
class GFG{
// 函数用于查找给定数组中的最大数
//。
static int DAC_Max(int a, int index, int l)
{
int max;
if(l - 1 == 0)
{
return a[index];
}
if (index >= l - 2)
{
if (a[index] > a[index + 1])
return a[index];
else
return a[index + 1];
}
// 在给定数组中查找最大元素的逻辑
//。
max = DAC_Max(a, index + 1, l);
if (a[index] > max)
return a[index];
else
return max;
}
// 函数用于查找给定数组中的最小数
//。
static int DAC_Min(int a, int index, int l)
{
int min;
if(l - 1 == 0)
{
return a[index];
}
if (index >= l - 2)
{
if (a[index] < a[index + 1])
return a[index];
else
return a[index + 1];
}
// 在给定数组中查找最小元素
// 的逻辑。
min = DAC_Min(a, index + 1, l);
if (a[index] < min)
return a[index];
else
return min;
}
// Driver Code
public static void main(String args)
{
// Defining the variables
int min, max;
// Initializing the array
int a = { 70, 250, 50, 80, 140, 12, 14 };
// Recursion - DAC_Max function called
max = DAC_Max(a, 0, 7);
// Recursion - DAC_Max function called
min = DAC_Min(a, 0, 7);
System.out.printf("The minimum number in " +
"a given array is : %d\n", min);
System.out.printf("The maximum number in " +
"a given array is : %d", max);
}
}
|
Python代码
# Python3 code to demonstrate Divide and
# Conquer Algorithm
# Function to find the maximum no.
# in a given array.
def DAC_Max(a, index, l):
max = -1
if(l - 1 == 0):
return arr[index]
if (index >= l - 2):
if (a[index] > a[index + 1]):
return a[index]
else:
return a[index + 1]
# Logic to find the Maximum element
# in the given array.
max = DAC_Max(a, index + 1, l)
if (a[index] > max):
return a[index]
else:
return max
# Function to find the minimum no.
# in a given array.
def DAC_Min(a, index, l):
min = 0
if(l - 1 == 0):
return arr[index]
if (index >= l - 2):
if (a[index] < a[index + 1]):
return a[index]
else:
return a[index + 1]
# Logic to find the Minimum element
# in the given array.
min = DAC_Min(a, index + 1, l)
if (a[index] < min):
return a[index]
else:
return min
# Driver Code
if name == 'main':
# Defining the variables
min, max = 0, -1
# Initializing the array
a = [70, 250, 50, 80, 140, 12, 14]
# Recursion - DAC_Max function called
max = DAC_Max(a, 0, 7)
# Recursion - DAC_Max function called
min = DAC_Min(a, 0, 7)
print("The minimum number in a given array is : ", min)
print("The maximum number in a given array is : ", max)
|
Java中用Fork-Join查找给定数组中的最大和最小元素
在Java中，可以使用Fork-Join框架来并行地查找给定数组中的最大和最小元素。Fork-Join框架提供了一种方便的方式来执行递归任务，并通过分治的方式将任务拆分成子任务，从而实现并行计算。
以下是一个使用Fork-Join框架查找数组中最大和最小元素的示例代码：
import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;
public class MaxMinFinder extends RecursiveTask<MinMaxResult> {
private static final int THRESHOLD = 500; // 阈值，控制任务拆分的大小
private int array;
private int start;
private int end;
public MaxMinFinder(int array, int start, int end) {
this.array = array;
this.start = start;
this.end = end;
}
@Override
protected MinMaxResult compute() {
int length = end - start + 1;
if (length <= THRESHOLD) {
// 如果任务足够小，直接计算最大和最小值
int min = array[start];
int max = array[start];
for (int i = start + 1; i <= end; i++) {
if (array[i] [/i]< min) {
min = array;
}
if (array > max) {
max = array;
}
}
return new MinMaxResult(min, max);
} else {
// 如果任务太大，拆分为两个子任务并递归地执行
int mid = start + (end - start) / 2;
MaxMinFinder leftTask = new MaxMinFinder(array, start, mid);
MaxMinFinder rightTask = new MaxMinFinder(array, mid + 1, end);
// 并行执行子任务
invokeAll(leftTask, rightTask);
// 合并子任务的结果
MinMaxResult leftResult = leftTask.join();
MinMaxResult rightResult = rightTask.join();
// 合并最小和最大值
int min = Math.min(leftResult.getMin(), rightResult.getMin());
int max = Math.max(leftResult.getMax(), rightResult.getMax());
return new MinMaxResult(min, max);
}
}
public static void main(String args) {
int array = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
ForkJoinPool forkJoinPool = new ForkJoinPool();
MaxMinFinder task = new MaxMinFinder(array, 0, array.length - 1);
MinMaxResult result = forkJoinPool.invoke(task);
System.out.println("Min: " + result.getMin());
System.out.println("Max: " + result.getMax());
}
}
class MinMaxResult {
private final int min;
private final int max;
public MinMaxResult(int min, int max) {
this.min = min;
this.max = max;
}
public int getMin() {
return min;
}
public int getMax() {
return max;
}
}
|
在这个示例中，MaxMinFinder类是一个RecursiveTask，它负责查找数组中的最大和最小值。在compute方法中，如果任务足够小（小于等于阈值），则直接计算最大和最小值；否则，将任务拆分为两个子任务，并通过invokeAll并行执行这两个子任务。然后，通过join方法等待子任务完成并获取其结果，最终合并子任务的结果得到整体的最小和最大值。在main方法中，创建一个ForkJoinPool实例，并通过invoke方法启动任务并获取结果。