Semak sama ada pembahagi sepunya terbesar dalam tatasusunan boleh dibuat lebih besar daripada 1 dengan menggantikan pasangan dengan produk mereka

Dalam artikel ini, kami berhasrat untuk meneroka soalan yang menarik tentang Pembahagi Sepunya Terhebat (GCD) tatasusunan dalam pelbagai bahasa pengaturcaraan, memfokuskan pada C++. Kami akan menunjukkan pendekatan algoritmik yang menggunakan pertukaran unsur berpasangan dan bilangan produk mereka untuk mengesahkan sama ada adalah mungkin untuk meningkatkan GCD melebihi 1. Di samping itu, kami akan menyediakan cara lain untuk menyelesaikan masalah ini, masing-masing dengan definisi sintaksnya. Sebagai tambahan kepada penyelesaian ini, kami juga akan membentangkan dua kod boleh laku lengkap yang mengandungi kaedah ini.

tatabahasa

Untuk memastikan pemahaman yang jelas tentang contoh kod seterusnya, kita mesti menilai dan memahami sintaks yang digunakan sebelum berbuat demikian.

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) {
   if (b == 0)
      return a;
   return gcd(b, a % b);
}

bool canIncreaseGCD(vector<int>& arr) {
   // Your implementation goes here
}

Algoritma

Mari kita mendalami persoalan sama ada pembahagi sepunya terbesar bagi tatasusunan boleh dipertingkatkan dengan menukar hasil darab sepasang elemen. Kami akan meneruskan seperti berikut:

• Untuk memudahkan proses carian menggunakan algoritma Euclidean untuk mendapatkan pembahagi sepunya (GCD) terbesar bagi dua nombor tertentu, mencipta fungsi tambahan yang dipanggil "gcd(a,b)" akan membawa bantuan besar. . Kaedah ini mengambil dua integer input "a" dan "b" dan setelah diproses melalui pembolehubah itu mengembalikan nilai "GDC" yang terhasil sebagai data output, dengan itu memudahkan dengan ketara perkara yang anda perlu lakukan untuk mendapatkan pelbagai pertanyaan skalar dan/atau produk untuk maklumat GDC.

• Dipanggil "canIncreaseGCD", pasukan kami mencadangkan mencipta fungsi boolean yang mengambil parameter input dipanggil 'arr' - mewakili tatasusunan nilai GCD ​​yang perlu dinilai. Matlamatnya adalah untuk menyemak sama ada terdapat kemungkinan operasi yang boleh meningkatkan nilai ini dengan mengembalikan "benar" atau "salah".

kaedah

Sekarang, mari kita bincangkan dua kaedah berbeza −

kaedah satu

• Mulakan arus pembolehubah GCD kepada pembahagi sepunya terbesar bagi dua elemen pertama dalam tatasusunan.

• Semak setiap elemen dalam tatasusunan, bermula dari elemen ketiga, dan hitung pembahagi sepunya terbesar (GCD) menggunakan nilai GCD semasa. Proses ini diulang untuk setiap elemen berikutnya.

• Dalam kes di mana pembahagi sepunya tertinggi bagi GDC semasa berbanding elemen lebih besar daripada satu nilai, pelarasan (GDC semasa) diperlukan supaya pelarasan adalah sama dengan nilai tertinggi/faktor sepunya diperkenalkan.

• Kembali benar daripada fungsi canIncreaseGCD jika currentGCD menjadi lebih besar daripada 1 semasa lelaran.

Contoh

Contoh

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) {
   if (b == 0)
      return a;
   return gcd(b, a % b);
}

bool canIncreaseGCD(vector<int>& arr) {
   int currentGCD = gcd(arr[0], arr[1]);
   for (int i = 2; i < arr.size(); i++) {
      if (gcd(arr[i], currentGCD) > 1) {
         currentGCD = gcd(arr[i], currentGCD);
         return true;
      }
   }
   return false;
}

int main() {
   vector<int> arr = {2, 3, 4, 5, 6};
   if (canIncreaseGCD(arr)) {
      cout << "The GCD of the array can be increased." << endl;
   } else {
      cout << "The GCD of the array cannot be increased." << endl;
   }
   return 0;
}

Output

The GCD of the array cannot be increased.

Penjelasan

Kaedah ini direka bentuk untuk mengesahkan sama ada pembahagi sepunya terbesar (GCD) tatasusunan dipertingkatkan dengan menggantikan sepasang elemen dengan produknya. Pertama, kod mentakrifkan fungsi untuk mengira GCD berdasarkan algoritma Euclidean. Selepas itu, CanIncreaseGCD diperkenalkan untuk memulakan GCD semasa menggunakan GCD daripada dua elemen pertama dalam arr vektor. Ia selanjutnya membandingkan GCD setiap elemen berikutnya dengan currentGDC dan mengemas kini currentGDC jika GCD unsur dan currentGDC melebihi 1. Semasa lelaran, jika GDC semasa melebihi 1, kita boleh menambah GCD tatasusunan dan mengembalikan benar jika tidak, mengembalikan palsu, menunjukkan bahawa kaedah ini gagal untuk jujukan nombor tertentu. Fungsi utama menunjukkan penggunaannya menggunakan tatasusunan contoh dan mencetak responsnya selepas menilai sama ada canIncreaseGDC boleh menambah nilai GDC yang sepadan.

Kaedah 2

• Memulakan pembolehubah totalGCD kepada pembahagi sepunya terbesar bagi semua elemen dalam tatasusunan.

• Lelaran pada tatasusunan dan kira pembahagi sepunya terbesar bagi setiap elemen dengan totalGCD.

• Jika pembahagi sepunya terbesar bagi suatu elemen dan jumlah GCD adalah lebih besar daripada 1, kembalikan benar daripada fungsi canIncreaseGCD.

• Jika tiada unsur yang meningkatkan pembahagi sepunya terbesar ditemui apabila lelaran selesai, kembalikan palsu.

Contoh

Contoh

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) {
   if (b == 0)
      return a;
   return gcd(b, a % b);
}

bool canIncreaseGCD(vector<int>& arr) {
   int totalGCD = arr[0];
   for (int i = 1; i < arr.size(); i++) {
      totalGCD = gcd(arr[i], totalGCD);
      if (totalGCD > 1)
         return true;
   }
   return false;
}

int main() {
   vector<int> arr = {2, 3, 4, 5, 6};
   if (canIncreaseGCD(arr)) {
      cout << "The GCD of the array can be increased." << endl;
   } else {
      cout << "The GCD of the array cannot be increased." << endl;
   }
   return 0;
}

Output

The GCD of the array cannot be increased.

Penjelasan

Satu lagi matlamat Kaedah 2 adalah untuk mengesahkan sama ada penggantian pasangan elemen dalam tatasusunan boleh meningkatkan pembahagi sepunya terbesar (GCD). Struktur kod adalah serupa dengan yang digunakan dalam Kaedah 1. Pertama, ia termasuk fungsi gcd untuk mengira GDC antara dua nombor, dan kemudian menyediakan fungsi canIncreaseGDC yang menerima vektor tatasusunan sebagai input. Dengan mula-mula memulakan totalGCG hanya menggunakan elemen pertamanya, dan kerana ia kemudiannya berulang ke atas elemen berikutnya, ia secara sistematik menilai setiap nilai terkira yang sepadan berhubung dengan totalCGC - Benar jika output semasa terbukti lebih tinggi daripada satu, menunjukkan keseluruhan CGC sememangnya dinaikkan. , jika tidak Palsu menunjukkan bahawa tiada kenaikan yang sesuai selepas carian selesai. Jadi, sekali lagi, pendekatan ini berfungsi dengan berkesan dalam situasi yang setanding dengan contoh yang digunakan dalam demonstrasi utama kami.

Kesimpulan

Dalam artikel ini, kami meneroka isu yang berkaitan dengan Pembahagi Sepunya Terhebat (GCD) tatasusunan dalam C++. Kami membincangkan pendekatan algoritma untuk menentukan sama ada GCD tatasusunan boleh lebih besar daripada 1 dengan menggantikan hasil darab pasangan unsur. Kami menyediakan sintaks kaedah yang digunakan dalam coretan kod dan mencadangkan dua cara berbeza untuk menyelesaikan masalah. Dua contoh kod boleh laku lengkap juga disediakan untuk setiap kaedah. Dengan menggunakan kaedah ini, anda boleh menentukan dengan berkesan sama ada GCD tatasusunan boleh ditingkatkan, membuka kemungkinan untuk penyelesaian masalah selanjutnya.

Atas ialah kandungan terperinci Semak sama ada pembahagi sepunya terbesar dalam tatasusunan boleh dibuat lebih besar daripada 1 dengan menggantikan pasangan dengan produk mereka. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!