C++程序：在数组中找到最大的可整除子集

本教程将讨论一个问题，其中给定一个不同的正整数数组。我们需要找到最大的子集，使得每对较大的元素除以较小的元素，例如 -

Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.

Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1

寻找解决方案的方法

我们将在本教程中解释两种不同的方法。

简单方法

在简单方法中，我们可以应用递归来解决这个问题。我们将获取每个元素并检查它是否应将其包含在子集中。假设我们从第一个元素开始。我们将有两个选择，要么包含在子集中，要么不包含在第一个元素中。让我们包括第一个元素。然后，对于要包含在子集中的第二个元素，它应该可以被子字符串中的元素（即第一个元素）整除或除以。这就是我们遍历数组的方式。因此，将有 2^n 条可能的路径，其时间复杂度为 O(2^n)。让我们看看解决这个问题的可行方法。

有效的方法

可以通过使用动态规划来解决这个问题。

立即学习“C++免费学习笔记（深入）”；

• 对数组进行排序，使左侧元素能被正确元素整除。我们必须检查一次整除性。

  

  易通cmseasy免费的企业建站程序2.0 UTF-8 build 201000510 中文版

  易通(企业网站管理系统)是一款小巧,高效,人性化的企业建站程序.易通企业网站程序是国内首款免费提供模板的企业网站系统.§ 简约的界面及小巧的体积：后台菜单完全可以修改成自己最需要最高效的形式；大部分操作都集中在下拉列表框中，以节省更多版面来显示更有价值的数据；数据的显示以Javascript数组类型来输出，减少数据的传输量，加快传输速度。 § 灵活的模板标签及模

  下载

• 我们将采用最长递增子序列，即我们的 dp[ ] 数组，来存储直到第 i 个索引的最大可整除子集。我们将用 1 来初始化每个索引，因为每个元素都会划分自身。

• 现在我们将从第二个索引开始迭代，并检查每个元素是否存在以当前索引结尾的最大可整除子集。这样，我们就找到了每个索引的最大子集。

• 现在遍历数组，对于每个元素，找到可整除次数最大的除数。并将当前索引的可整除计数值更改为该元素的可整除计数 + 1。

示例

C++ 代码以上方法

#include
using namespace std;
int main(){
    int nums[] = {1, 2, 3, 6};
    int n = sizeof(nums)/sizeof(int);
    // sorting the array to exclude one condition for division.
    sort(nums, nums+n);
    vector  prev_res(n, -1);
    // vector to store divisors of all the elements
    vector  dp(n, 1);
    int max = 1;
    for (int i=1; i= 0){
        cout << nums[k] << " ";
        k = prev_res[k];
    }
    return 0;
}

输出

Largest divisible subset in the array: 6 2 1

结论

在本教程中，我们讨论了一个问题：我们需要找到给定数组中每对整数可整除的最大可整子集。我们讨论了一种产生指数时间复杂度的递归方法，因此我们讨论了动态编程解决方案。我们还讨论了解决此问题的 C++ 程序，我们可以使用 C、Java、Python 等编程语言来实现。我们希望本教程对您有所帮助。