最長的子數組，其最大公約數大於1

陣列是一組相似的資料集合，以連續的方式儲存在相鄰的記憶體位置上。透過將偏移值定義為資料庫的特定基值，可以更容易地評估每個元素的特定位置。此特定索引的基底值為零，偏移值是兩個特定索引之間的差值。子數組是特定數組的一部分，可以定義為一組變量，具有多個值的標籤。最長的子數組指的是數組中所有元素都大於K的數組。這裡最大和子數組的和為-

• 給定資料集中的少於

• 等於給定的資料集。

• 給定資料集中的少於

要找出最長子數組的長度，我們只需要找出特定子數組中1的總數。注意：計數應該大於零的計數。最大公約數是一種數學現象，在其中我們找到可以將輸入的整數中的每個整數除以零餘數的最大整數值。這裡的條件是，「最大公約數大於1」。這意味著，這裡的特定數字在給定輸入之間只有至少一個公共除數。

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.

今天在這篇文章中，我們將學習如何使用C 程式設計環境找到一個最長的子數組，其最大公約數大於1。

找到最長子數組的演算法，其GCD大於1

在這個特定的演算法中，我們可以找到包含大於1的最長子陣列的最大公約數值。

• 第一步 - 開始。

• 第二步 - 宣告進程的變數。

• 第三步驟 - 設定並將其初始化為零值。

• 第四步 - 建立一個函數來評估該子陣列的最大長度。

• 步驟 5 - 將其作為參數包含一個向量。

• 第6步- 建立一個變數來取得答案。

• 第7步 - 設定並將其初始化為零值。

• 步驟8 - 儲存具有GCD > 1值的最長子陣列的值。

• 第9步 - 迭代循環以找到每個子數組的最大公約數。

• 第10步 - 用子數組的長度值取代答案。

• 步驟11 - 若子陣列的最大公約數大於1，則儲存答案。

• 步驟12 - 回傳答案。

• 步驟13 - 否則，再次運行循環並迭代。

• 第14步 - 在進程完成後終止。

找出最長子數組的語法，其GCD大於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;

透過遵循上述演算法，我們在這裡編寫了可能的語法來找到具有大於1的最長子陣列的GCD值。

方法：

• 方法1−透過樸素方法找到最長的子數組，其最大公約數大於1的C 程式。

• 方法2 - C 程式找出陣列的最大公約數大於1。

使用樸素方法找出最長公約數大於1的子陣列的C 程式

在這段C 程式碼中，我們採用了樸素的方法，透過產生給定數組的所有可能子數組，來找到具有大於1的最長子數組的GCD值。

Example 1

的中文翻譯為：

範例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;
}

輸出

3

C 程式找出陣列的最大公約數大於1

在這段C 程式碼中，我們嘗試計算最大公約數，並且它具有檢查它是否大於1的能力。

Example 2

的翻譯為：

範例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);
}

輸出

5
2
1

結論

透過這個討論，我們可以找到如何找到最長的子數組，其GCD大於1。希望編寫的演算法和C 程式碼能夠清晰地展示給你，讓你了解這個過程在現實世界中是如何運作的。

以上是最長的子數組，其最大公約數大於1的詳細內容。更多資訊請關注PHP中文網其他相關文章！