Das längste Subarray, dessen größter gemeinsamer Teiler größer als 1 ist

Ein Array ist eine Sammlung ähnlicher Daten, die zusammenhängend an benachbarten Speicherorten gespeichert sind. Durch die Definition des Offset-Werts als spezifischer Basiswert für die Datenbank ist es einfacher, die spezifische Position jedes Elements zu bewerten. Der Basiswert für diesen bestimmten Index ist Null und der Offsetwert ist die Differenz zwischen den beiden bestimmten Indizes. Ein Subarray ist Teil eines bestimmten Arrays und kann als eine Reihe von Variablen definiert werden, die mit mehreren Werten gekennzeichnet sind. Das längste Subarray bezieht sich auf ein Array, in dem alle Elemente im Array größer als K sind. Die Summe des maximalen Summen-Subarrays beträgt hier -

• Weniger als

in einem bestimmten Datensatz

• entspricht dem angegebenen Datensatz.

• Weniger als

in einem bestimmten Datensatz

Um die Länge des längsten Subarrays zu ermitteln, müssen wir lediglich die Gesamtzahl der Einsen im jeweiligen Subarray ermitteln. HINWEIS: Die Anzahl sollte größer als die Anzahl Null sein. Der größte gemeinsame Teiler ist ein mathematisches Phänomen, bei dem wir den größten ganzzahligen Wert finden, der jede der eingegebenen ganzen Zahlen mit einem Rest von Null teilen kann. Dabei gilt die Bedingung, dass „der größte gemeinsame Teiler größer als 1“ ist. Dies bedeutet, dass diese bestimmte Zahl hier nur mindestens einen gemeinsamen Teiler zwischen den angegebenen Eingaben hat.

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.

Heute erfahren Sie in diesem Artikel, wie Sie mithilfe der C++-Programmierumgebung das längste Subarray finden, dessen größter gemeinsamer Teiler größer als 1 ist.

Algorithmus zum Finden des längsten Subarrays mit GCD größer als 1

In diesem speziellen Algorithmus können wir den größten gemeinsamen Wert des längsten Subarrays ermitteln, das größer als 1 enthält.

• Schritt eins – loslegen.

• Schritt 2 – Deklarieren Sie die Variablen des Prozesses.

• Schritt 3 – Stellen Sie den Wert auf Null ein und initialisieren Sie ihn.

• Schritt 4 – Erstellen Sie eine Funktion, um die maximale Länge dieses Subarrays auszuwerten.

• Schritt 5 – Fügen Sie einen Vektor als Argument ein.

• Schritt 6 – Erstellen Sie eine Variable, um die Antwort zu erhalten.

• Schritt 7 – Stellen Sie den Wert auf Null ein und initialisieren Sie ihn.

• Schritt 8 – Speichern Sie den Wert des längsten Subarrays mit einem GCD-Wert > 1.

• Schritt 9 – Wiederholen Sie die Schleife, um den größten gemeinsamen Teiler jedes Unterarrays zu finden.

• Schritt 10 – Ersetzen Sie die Antwort durch den Längenwert des Subarrays.

• Schritt 11 – Wenn der größte gemeinsame Teiler der Subarrays größer als 1 ist, speichern Sie die Antwort.

• Schritt 12 – Antwort zurückgeben.

• Schritt 13 – Andernfalls führen Sie die Schleife erneut aus und wiederholen Sie den Vorgang.

• Schritt 14 – Beenden Sie den Vorgang, nachdem der Vorgang abgeschlossen ist.

Syntax zum Finden des längsten Subarrays, dessen GCD größer als 1 ist

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;

Indem wir dem obigen Algorithmus folgen, haben wir hier die mögliche Syntax geschrieben, um den GCD-Wert mit dem längsten Subarray größer als 1 zu finden.

Methode:

• Methode 1 − C++-Programm zum Finden des längsten Subarrays, dessen größter gemeinsamer Teiler größer als 1 ist, mithilfe der naiven Methode.

• Methode 2 – C++-Programm zum Ermitteln des größten gemeinsamen Teilers eines Arrays größer als 1.

C++-Programm zum Finden von Unterarrays mit dem längsten gemeinsamen Teiler größer als 1 mithilfe der naiven Methode

In diesem C++-Code verfolgen wir einen naiven Ansatz, um den GCD-Wert des längsten Subarrays mit mehr als 1 zu ermitteln, indem wir alle möglichen Subarrays des gegebenen Arrays generieren.

Die chinesische Übersetzung von

Beispiel 1

lautet:

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

Ausgabe

3

C++-Programm zum Ermitteln des größten gemeinsamen Teilers eines Arrays größer als 1

In diesem C++-Code versuchen wir, den größten gemeinsamen Teiler zu berechnen, und er bietet die Möglichkeit zu prüfen, ob er größer als 1 ist.

Beispiel 2

wird übersetzt als:

Beispiel 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);
}

Ausgabe

5
2
1

Fazit

Durch diese Diskussion können wir herausfinden, wie wir das längste Subarray finden, dessen GCD größer als 1 ist. Hoffentlich zeigen Ihnen der Algorithmus und der geschriebene C++-Code deutlich, wie dieser Prozess in der realen Welt funktioniert.

Das obige ist der detaillierte Inhalt vonDas längste Subarray, dessen größter gemeinsamer Teiler größer als 1 ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!