Le sous-tableau le plus long dont le plus grand diviseur commun est supérieur à 1

Un tableau est une collection de données similaires stockées dans des emplacements de mémoire adjacents de manière contiguë. En définissant la valeur de décalage comme valeur de base spécifique pour la base de données, il est plus facile d'évaluer la position spécifique de chaque élément. La valeur de base de cet index particulier est zéro et la valeur de décalage est la différence entre les deux indices particuliers. Un sous-tableau fait partie d'un tableau spécifique et peut être défini comme un ensemble de variables, étiquetées avec plusieurs valeurs. Le sous-tableau le plus long fait référence à un tableau dans lequel tous les éléments du tableau sont supérieurs à K. La somme du sous-tableau de somme maximale ici est -

• Moins de

dans un ensemble de données donné

• est égal à l'ensemble de données donné.

• Moins de

dans un ensemble de données donné

Pour trouver la longueur du sous-tableau le plus long, il nous suffit de trouver le nombre total de 1 dans le sous-tableau spécifique. REMARQUE : Le nombre doit être supérieur au nombre de zéro. Le plus grand diviseur commun est un phénomène mathématique dans lequel on trouve la plus grande valeur entière pouvant diviser chacun des entiers d'entrée avec un reste nul. La condition ici est que « le plus grand diviseur commun soit supérieur à 1 ». Cela signifie que ce nombre particulier n'a ici qu'au moins un diviseur commun entre les entrées données.

Input (array) : arr[] = {4, 3, 2, 2}
Output (after the process with sub-array operation) : 2
If we consider the subarray as {2, 2}, then we will get 2 as GCD. Which is > 1, is of maximum length.

Aujourd'hui, dans cet article, nous allons apprendre à trouver le sous-tableau le plus long dont le plus grand diviseur commun est supérieur à 1 à l'aide de l'environnement de programmation C++.

Algorithme pour trouver le sous-tableau le plus long avec un GCD supérieur à 1

Dans cet algorithme particulier, nous pouvons trouver la plus grande valeur commune du sous-tableau le plus long contenant supérieur à 1.

• Première étape : commencez.

• Étape 2 - Déclarez les variables du processus.

• Étape 3 - Réglez et initialisez-le à la valeur zéro.

• Étape 4 - Créez une fonction pour évaluer la longueur maximale de ce sous-tableau.

• Étape 5 - Incluez un vecteur comme argument.

• Étape 6 - Créez une variable pour obtenir la réponse.

• Étape 7 - Réglez et initialisez-le à la valeur zéro.

• Étape 8 - Stockez la valeur du sous-tableau le plus long avec GCD > 1 valeur.

• Étape 9 - Parcourez la boucle pour trouver le plus grand diviseur commun de chaque sous-tableau.

• Étape 10 - Remplacez la réponse par la valeur de longueur du sous-tableau.

• Étape 11 - Si le plus grand diviseur commun des sous-tableaux est supérieur à 1, enregistrez la réponse.

• Étape 12 - Renvoyez la réponse.

• Étape 13 - Sinon, exécutez à nouveau la boucle et itérez.

• Étape 14 - Terminez une fois le processus terminé.

Syntaxe pour trouver le sous-tableau le plus long dont le GCD est supérieur à 1

int n;
cin >> n;

const int MAX_NUM = 100 * 1000;
static int dp[MAX_NUM];

for(int i = 0; i < n; ++i){
   int x;
   cin >> x;

   int cur = 1;
   vector<int> d;
   for(int i = 2; i * i <= x; ++i){
      if(x % i == 0){
         cur = max(cur, dp[i] + 1);
         cur = max(cur, dp[x / i] + 1);
         d.push_back(i);
         d.push_back(x / i);
      }
   }
   if(x > 1){
      cur = max(cur, dp[x] + 1);
      d.push_back(x);
   }

    for(int j : d){
      dp[j] = cur;
   }
}
cout << *max_element(dp, dp + MAX_NUM) << endl;

En suivant l'algorithme ci-dessus, nous avons écrit ici la syntaxe possible pour trouver la valeur GCD avec le sous-tableau le plus long supérieur à 1.

Méthode :

• Méthode 1−Programme C++ pour trouver le sous-tableau le plus long dont le plus grand diviseur commun est supérieur à 1 grâce à la méthode naïve.

• Méthode 2 - Programme C++ pour trouver le plus grand diviseur commun d'un tableau supérieur à 1.

Programme C++ pour trouver des sous-tableaux avec le diviseur commun le plus long supérieur à 1 en utilisant la méthode naïve

Dans ce code C++, nous adoptons une approche naïve pour trouver la valeur GCD du sous-tableau le plus long supérieur à 1 en générant tous les sous-tableaux possibles du tableau donné.

La traduction chinoise de

Exemple 1

est :

Exemple 1

#include <bits/stdc++.h>
using namespace std;
void maxSubarrayLen(int arr[], int n) {
	int maxLen = 0;
	for (int i = 0; i < n; i++) {
		int gcd = 0;
		for (int j = i; j < n; j++) {
			gcd = __gcd(gcd, arr[j]);
			if (gcd > 1)
				maxLen = max(maxLen, j - i + 1);
			else
			   break;
		}
	}
	cout << maxLen;
}
int main() {
	int arr[] = { 410, 16, 7, 180, 222, 10, 33 };
	int N = sizeof(arr) / sizeof(int);
	maxSubarrayLen(arr, N);

	return 0;
}

Sortie

3

Programme C++ pour trouver le plus grand diviseur commun d'un tableau supérieur à 1

Dans ce code C++, nous essayons de calculer le plus grand diviseur commun et il a la capacité de vérifier s'il est supérieur à 1.

Exemple 2

se traduit par :

Exemple 2

#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
   if (a == 0)
      return b;
   return gcd(b%a, a);
}
void bestArray(int arr[], int n){
   bool even[n] = {false};
   int ans = 0;
   for(int i = 0; i < n; i++){
      ans = gcd(ans, arr[i]);
      if(arr[i] % 2 == 0)
         even[i] = true;
   }
   if(ans > 1)
      cout << 0 << endl;
   else {
      ans = 0;
      for(int i = 0; i < n-1; i++){
         if(!even[i]){
            even[i] = true;
            even[i+1] = true;
            if(arr[i+1]%2 != 0){
               ans+=1;
            }
            else
               ans+=2;
         }
      }
      if(!even[n-1]){
         ans+=2;
      }
      cout << ans << endl;
   }
}
int main(){
   int arr[] = {16, 10, 07, 81, 88, 32, 3, 42, 25};
   int n = 9;
   bestArray(arr, n);

   int arr1[] = {16, 7};
   n = 2;
   bestArray(arr1, n);

   int arr2[] = {10, 97, 2001};
   n = 3;
   bestArray(arr2, n);
}

Sortie

5
2
1

Conclusion

Grâce à cette discussion, nous pouvons découvrir comment trouver le sous-tableau le plus long dont le GCD est supérieur à 1. Espérons que l'algorithme et le code C++ écrits vous montreront clairement comment ce processus fonctionne dans le monde réel.

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!