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 つの選択肢があります。最初の要素を含めてみましょう。次に、2 番目の要素をサブセットに含めるには、部分文字列内の要素 (つまり、最初の要素) で割り切れるか、分割できる必要があります。これが配列を反復処理する方法です。したがって、時間計算量が O(2^n) の 2^n 個の可能なパスが存在します。この問題に対する考えられる解決策を見てみましょう。

効果的な方法

この問題は動的計画法を使用することで解決できます。

• 左側の要素が正しい要素で割り切れるように配列を並べ替えます。一度割り算を確認する必要があります。

• 最も長く増加するサブシーケンスである dp[ ] 配列を使用して、割り切れる最大のサブセットを i 番目のインデックスまで保存します。各要素はそれ自体を分割するため、各インデックスを 1 で初期化します。

• 次に、2 番目のインデックスから繰り返し、現在のインデックスで終わる最大の割り切れるサブセットがあるかどうかを各要素について確認します。このようにして、各インデックスの最大のサブセットを見つけます。

• 次に、配列を反復処理して、要素ごとに、割り切れる数が最大の約数を見つけます。そして、現在のインデックスの割り切れるカウント値を、その要素の割り切れるカウントの 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 中国語 Web サイトの他の関連記事を参照してください。