資料結構
網路
關係資料庫管理系統(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 次瀏覽
廣告