Subarray terpanjang yang pembahagi sepunya terbesar adalah lebih besar daripada 1

Susun atur ialah himpunan data serupa yang disimpan di lokasi memori bersebelahan dengan cara yang bersebelahan. Dengan mentakrifkan nilai offset sebagai nilai asas khusus untuk pangkalan data, lebih mudah untuk menilai kedudukan khusus setiap elemen. Nilai asas untuk indeks tertentu itu ialah sifar, dan nilai offset ialah perbezaan antara dua indeks tertentu. Subarray ialah sebahagian daripada tatasusunan tertentu dan boleh ditakrifkan sebagai satu set pembolehubah, dilabelkan dengan berbilang nilai. Subarray terpanjang merujuk kepada tatasusunan di mana semua elemen dalam tatasusunan lebih besar daripada K. Jumlah subarray jumlah maksimum di sini ialah -

• Kurang daripada

dalam set data yang diberikan

• adalah sama dengan set data yang diberikan.

• Kurang daripada

dalam set data yang diberikan

Untuk mencari panjang subarray terpanjang, kita hanya perlu mencari jumlah nombor 1 dalam subarray tertentu. NOTA: Kiraan hendaklah lebih besar daripada kiraan sifar. Pembahagi sepunya terbesar ialah fenomena matematik di mana kita dapati nilai integer terbesar yang boleh membahagikan setiap integer dalam input dengan baki sifar. Syarat di sini ialah "pembahagi sepunya terbesar adalah lebih besar daripada 1". Ini bermakna nombor tertentu di sini hanya mempunyai sekurang-kurangnya satu pembahagi sepunya antara input yang diberikan.

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.

Hari ini dalam artikel ini, kita akan belajar cara mencari subarray terpanjang yang pembahagi sepunya terbesar adalah lebih besar daripada 1 menggunakan persekitaran pengaturcaraan C++.

Algoritma untuk mencari subarray terpanjang dengan GCD lebih daripada 1

Dalam algoritma khusus ini, kita boleh mencari nilai sepunya terbesar bagi subarray terpanjang yang mengandungi lebih daripada 1.

• Langkah pertama - mulakan.

• Langkah 2 - Isytiharkan pembolehubah proses.

• Langkah 3 - Tetapkan dan mulakannya kepada nilai sifar.

• Langkah 4 - Buat fungsi untuk menilai panjang maksimum subarray ini.

• Langkah 5 - Sertakan vektor sebagai hujah.

• Langkah 6 - Buat pembolehubah untuk mendapatkan jawapan.

• Langkah 7 - Tetapkan dan mulakannya kepada nilai sifar.

• Langkah 8 - Simpan nilai subarray terpanjang dengan nilai GCD > 1.

• Langkah 9 - Ulangi gelung untuk mencari pembahagi sepunya terbesar bagi setiap sub-tatasusunan.

• Langkah 10 - Gantikan jawapan dengan nilai panjang subarray.

• Langkah 11 - Jika pembahagi sepunya terbesar bagi subarray adalah lebih besar daripada 1, simpan jawapannya.

• Langkah 12 - Kembalikan jawapan.

• Langkah 13 - Jika tidak, jalankan gelung sekali lagi dan ulangi.

• Langkah 14 - Tamatkan selepas proses selesai.

Sintaks untuk mencari subarray terpanjang yang GCDnya lebih besar daripada 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;

Dengan mengikuti algoritma di atas, di sini kami telah menulis sintaks yang mungkin untuk mencari nilai GCD dengan subarray terpanjang lebih besar daripada 1.

Kaedah:

• Kaedah 1−Program C++ untuk mencari subarray terpanjang yang pembahagi sepunya terbesar adalah lebih besar daripada 1 melalui kaedah naif.

• Kaedah 2 - Program C++ untuk mencari pembahagi sepunya terbesar bagi tatasusunan yang lebih besar daripada 1.

Program C++ untuk mencari subarray dengan pembahagi sepunya terpanjang lebih besar daripada 1 menggunakan kaedah naif

Dalam kod C++ ini, kami mengambil pendekatan naif untuk mencari nilai GCD bagi subarray terpanjang dengan lebih daripada 1 dengan menjana semua subarray yang mungkin bagi tatasusunan yang diberikan.

Contoh 1

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

Output

3

Atur cara C++ untuk mencari pembahagi sepunya terbesar bagi tatasusunan yang lebih besar daripada 1

Dalam kod C++ ini kami cuba mengira pembahagi sepunya terbesar dan ia mempunyai keupayaan untuk menyemak sama ada ia lebih besar daripada 1.

Contoh 2

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

Output

5
2
1

Kesimpulan

Melalui perbincangan ini, kita boleh mengetahui cara mencari subarray terpanjang yang GCDnya lebih besar daripada 1. Mudah-mudahan algoritma dan kod C++ yang ditulis akan menunjukkan dengan jelas kepada anda bagaimana proses ini berfungsi di dunia nyata.

Atas ialah kandungan terperinci Subarray terpanjang yang pembahagi sepunya terbesar adalah lebih besar daripada 1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!