数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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) 的时间复杂度。让我们来看一下解决这个问题的可行方法。
高效方法
可以使用动态规划来高效地解决这个问题。
对数组进行排序，以便左侧元素可以被右侧元素整除。我们只需要检查一次整除性。
我们将使用最长递增子序列，即我们的 dp[] 数组，来存储到第 i 个索引为止的最大可整除子集。我们将每个索引初始化为 1，因为每个元素都能被自身整除。
现在我们将从第二个索引迭代，并检查每个元素以查找以当前索引结尾的最大可整除子集。通过这种方式，我们将找到每个索引的最大子集。
现在遍历数组，对于每个元素，找到除数，其可整除计数最大。并将当前索引的可整除计数值更改为该元素的可整除计数 + 1。
示例
上述方法的 C++ 代码
#include<bits/stdc++.h>
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 <int> prev_res(n, -1);
// vector to store divisors of all the elements
vector <int> dp(n, 1);
int max = 1;
for (int i=1; i<n; i++){ // Check if there's a divisor of ith element present at jth index.
for (int j=0; j<i; j++){
if (nums[i]%nums[j] == 0){
// check If adding that increases the number of elements in subsequence.
if (dp[i] < dp[j] + 1){
dp[i] = dp[j]+1;
prev_res[i] = j;
}
}
}
// finding index having a maximum number of subsets.
if(max<dp[i])
max = dp[i];
}
cout << "Largest divisible subset in the array: ";
// printing the maximum subset
int k = max;
while (k >= 0){
cout << nums[k] << " ";
k = prev_res[k];
}
return 0;
}输出
Largest divisible subset in the array: 6 2 1
结论
在本教程中，我们讨论了一个问题：我们需要在给定的数组中找到最大的可整除子集，其中每一对整数都是可整除的。我们讨论了一种递归方法，它会产生指数时间复杂度，因此我们讨论了一种动态规划解决方案。我们还讨论了这个问题的 C++ 程序，我们也可以使用 C、Java、Python 等编程语言来实现。希望本教程对您有所帮助。
更新于：2021年11月25日
218 次浏览
广告