C++ 减而治之

想象一下，当你遇到解决初始问题时困难重重。如果我告诉你，问题的一个小部分更容易解决，并且你可以利用这个答案来找到更大问题的答案呢？有趣吧？“减而治之”策略就能实现这一点。

“减而治之”是一种解决问题的策略，通过在解决过程的每个阶段减少输入的规模来解决问题。与分而治之类似，它将问题分解成较小的子问题，但是“减而治之”在每个阶段缩小输入数据的规模，而不是增加它。

用“减而治之”策略可以解决一些问题，比如找出数组中的最大或最小元素，找出一组点中最近的点对以及二分查找等。

由于每个阶段输入数据的数量都在减少，所以“减而治之”能减少解决方案的空间和时间复杂度，它常常能产生有效的算法。选择正确的技巧来减少输入数据的数量非常重要，否则可能会得到一个低效的算法。

减而治之方法的变化

“减而治之”策略有三种主要形式：

第一种 是“按特定值或常数减少”。

在这种变体中，算法的每一次重复或递归步骤都以相同的常数减少实例的总大小。虽然也可能有其他常数大小的减少，但这个常数通常等于1。许多算法都使用这种变体，比如下面的例子。

拓扑排序、图搜索算法DFS和BFS、插入排序以及生成子集或排列的各种算法等。

第二种 是“按常数因子减少”。

对于算法的每个迭代或递归步骤，这种策略会将问题实例减少一个常数量。这个常数因子通常为2。除了2以外，减少一个这样的因子非常罕见。当因子大于2时，如假币问题，按常数因子减少的技术尤其有效。这种策略的应用包括：

俄罗斯农民乘法、假币问题和二分查找等。

第三种也是最后一种是“减少变量大小”。

在这个修改中，算法的步骤或迭代的大小减少的模式会改变。虽然用于计算两个数字的最大公约数的问题中，第二个参数的值始终右边较小于左边，但它并不是按常数甚至按常数因子减少。以下是一些应用该策略的示例，比如：

欧几里得算法、插值搜索以及计算中位数和选择问题等。

示例 1

我们可以使用减而治之的方法创建排列的示例。

我们如何获得一个有n个元素的集合的n！个排列，比如a1，a2，a3，…，an？为了找到解决方案，我们先产生(n-1)!个排列。一旦解决了这个问题，我们就可以通过将n放入每个(n-1)个元素排列中的每个位置来解决更广泛的问题。

如果只有一个元素，则只有一个排列，这是递归的基本情况。

示例 2

让我们举一个二分查找方法的例子，我们应用减治法。在排序数组中查找元素的位置可以使用二分查找方法。

使用这种方法，总是在数组的中间搜索元素。

考虑一个排序的整数数组 a = {5, 10, 15, 20, 25}。我们要找到元素 10 的索引。

方法

例如，要获取 {1, 2, 3} 的排列

首先，我们找到 {1, 2} 的排列的解决方案

从 {1} 开始找到 {1} 的排列

现在将 2 插入到 {1} 中，得到：{2 1} 和 {1 2}

将 3 插入到 {2 1} 和 {1 2} 中，得到：{3 2 1} {2 3 1} {2 1 3} {3 1 2} {1 3 2} {1 2 3}

我们生成的排列总数是 n!，运行时间为 n!。对于除了最小的 n 值以外的所有值来说，这个速度是非常慢的，这不是算法的问题。问题在于生成的对象太少。

找到旅行推销员问题的所有路径就是这类问题，可以应用这个方法。

算法

步骤 1 ：开始

步骤 2 ：设置 p（要找到其位置的元素）

步骤 3 ：设置指针 first（在第一个位置）和 last（在最后一个位置）

步骤 4 ：找到中间元素（mid）

步骤 5 ：如果 pmid，则打印中间元素

步骤 6 ：如果 p>mid，则检查 p 与 mid 右边的元素

步骤 7 ：如果 p<mid，则检查 p 与 mid 左边的元素

步骤 8 ：重复步骤 4 到 7，直到 first 遇到 last

步骤 9 ：返回结果

步骤 10 ：停止

示例

// Binary Search in C
#include <stdio.h>
int binSearch(int a[], int p, int first, int last) {
   // Repeat till the low and high collide with each other
   while (first <= last) {
   int mid = first + (last - first) / 2;
   if (a[mid] == p)
      return mid;
   if (a[mid] < p)
      first = mid + 1;
   else
      last = mid - 1;
   }
   return -1;
}
int main(void) {
   int a[] = {5, 10, 15, 20, 25};
   int s = sizeof(a) / sizeof(a[0]);
   int p = 10;
   int res = binSearch(a, p, 0, s - 1);
   if (res == -1)
   printf(" Element not present");
   else
  //printing the position of the element
   printf("Element %d is found at index position %d of the array.",p ,res);  
  return 0;
}

输出

执行后，它将产生以下输出：

Element 10 is found at index position 1 of the array.

优点

“递减与征服”的一些优点包括：

简单性 ：与其他策略（如动态规划或分治法）相比，递减与征服通常更容易实践。

有效的算法 ：该技术经常产生高效的算法，因为每一步都会减少输入数据的大小，降低结果的时间和空间复杂度。

问题特定 ：该方法在特定问题上有效，其中问题的简化版本可以更快地解决。

缺点

“递减与征服”的一些缺点包括：

问题特定 ：该方法可能不适用于更复杂或所有难度的问题。

实现复杂性 ：与分治法等其他策略相比，该策略可能更难实施，并且可能需要更详细的计划。