Programme C++ : trouver le plus grand sous-ensemble divisible dans un tableau

Ce tutoriel discutera d'un problème où un tableau différent d'entiers positifs est donné. Nous devons trouver le plus grand sous-ensemble de telle sorte que chaque paire d'éléments plus grands soit divisée par l'élément plus petit, par exemple -

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

Façons de trouver la solution

Nous expliquerons deux méthodes différentes dans ce tutoriel.

Méthode simple

Dans la méthode simple, nous pouvons appliquer la récursivité pour résoudre ce problème. Nous obtiendrons chaque élément et vérifierons s'il doit être inclus dans le sous-ensemble. Disons que nous commençons par le premier élément. Nous aurons deux choix, soit être inclus dans le sous-ensemble, soit ne pas être inclus dans le premier élément. Incluons le premier élément. Ensuite, pour que le deuxième élément soit inclus dans le sous-ensemble, il doit être divisible ou divisé par les éléments de la sous-chaîne (c'est-à-dire le premier élément). C'est ainsi que nous parcourons le tableau. Par conséquent, il y aura 2^n chemins possibles avec une complexité temporelle de O(2^n). Examinons les solutions possibles à ce problème.

Un moyen efficace

peut être résolu en utilisant la programmation dynamique.

• Triez le tableau pour que l'élément de gauche soit divisible par l'élément correct. Nous devons vérifier la divisibilité une fois.

• Nous prendrons la sous-séquence croissante la plus longue, notre tableau dp[ ], pour stocker le plus grand sous-ensemble divisible jusqu'au i-ème indice. Nous initialiserons chaque index à 1 puisque chaque élément se divisera.

• Maintenant, nous allons itérer à partir du deuxième index et vérifier pour chaque élément s'il existe un sous-ensemble maximum divisible se terminant à l'index actuel. De cette façon, nous trouvons le plus grand sous-ensemble pour chaque index.

• Parcourez maintenant le tableau et pour chaque élément, trouvez le diviseur ayant la plus grande divisibilité. Et change la valeur du nombre divisible de l'index actuel en le nombre divisible de cet élément + 1.

Exemple

Code C++ pour la méthode ci-dessus

#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;
}

Output

Largest divisible subset in the array: 6 2 1

Conclusion

Dans ce tutoriel, nous avons discuté d'un problème : nous devons trouver le plus grand nombre divisible de chaque paire d'entiers dans un tableau donné. sous-ensemble. Nous avons discuté d'une approche récursive qui génère une complexité temporelle exponentielle, nous avons donc discuté de solutions de programmation dynamique. Nous avons également discuté des programmes C++ pour résoudre ce problème, que nous pouvons implémenter à l'aide de langages de programmation comme C, Java, Python, etc. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!