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&#39;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 等程式語言來實作。我們希望本教學對您有所幫助。

以上是C++程式：在陣列中找到最大的可整除子集的詳細內容。更多資訊請關注PHP中文網其他相關文章！