資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學最大公約數大於1的最長子陣列
陣列是由儲存在連續記憶體位置的相似資料集組成的集合。透過為資料庫的特定基值定義一個偏移值，可以更輕鬆地評估每個元素的特定位置。該特定索引的基值為零，偏移值是兩個特定索引之差的值。子陣列是特定陣列的一部分，可以定義為一組變數，這些變數共同具有多個值的標籤。最長子陣列是指所有元素都大於 K 的陣列。這裡最大和子陣列的和為：
小於給定資料集。
等於給定資料集。
小於給定資料集。
要找到最長子陣列的長度，我們只需要找出特定子陣列中 1 的總數。注意：計數應該大於零的計數。最大公約數 (GCD) 是一種數學現象，我們找到可以將每個輸入整數除以零餘數的最大的整數值。這裡的條件是，“GCD 大於 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 的最長子陣列。
查詢最大公約數大於 1 的最長子陣列的演算法
在這個特定演算法中，我們可以找出包含大於 1 的最大公約數的子陣列。
步驟 1 - 開始。
步驟 2 - 宣告用於該過程的變數。
步驟 3 - 設定並將其初始化為零值。
步驟 4 - 建立一個函式來評估該子陣列的最大長度。
步驟 5 - 包含一個向量作為引數。
步驟 6 - 建立一個變數來獲取答案。
步驟 7 - 設定並將其初始化為零值。
步驟 8 - 儲存最大公約數大於 1 的最長子陣列的值。
步驟 9 - 迭代迴圈以查詢每個子陣列的最大公約數。
步驟 10 - 用子陣列的長度值替換答案。
步驟 11 - 如果子陣列的最大公約數大於 1，則儲存答案。
步驟 12 - 返回答案。
步驟 13 - 否則，再次執行迴圈並迭代它。
步驟 14 - 過程完成後終止。
查詢最大公約數大於 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 的最長子陣列。
方法：-
方法 1 - 使用樸素方法查詢最大公約數大於 1 的最長子陣列的 C++ 程式。
方法 2 - 查詢陣列的最大公約數是否大於 1 的 C++ 程式。
使用樸素方法查詢最大公約數大於 1 的最長子陣列的 C++ 程式
在這個 C++ 程式碼中，我們應用了樸素方法，透過生成給定陣列的所有可能的子陣列來查詢存在最大公約數大於 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
查詢陣列的最大公約數是否大於 1 的 C++ 程式
在這個 C++ 程式碼中，我們嘗試計算最大公約數，並且它能夠檢查它是否大於 1。
示例 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
結論
透過本次討論，我們可以瞭解如何找到最大公約數大於 1 的最長子陣列。希望所寫的演算法和 C++ 程式碼能夠清晰地讓你瞭解這個過程在現實世界中的運作方式。
394 次瀏覽
