Cari pasangan GCD untuk tatasusunan yang diberikan

Soal Jawab Java: Mencari pasangan GCD bagi tatasusunan tertentu ialah soalan lazim yang memerlukan pengiraan pembahagi sepunya terbesar (GCD) nombor dalam tatasusunan. Di Java, anda boleh menggunakan algoritma Euclidean untuk menyelesaikan masalah ini. Dalam artikel ini, editor PHP Xigua akan memperkenalkan cara menggunakan Java untuk menulis kaedah mencari pasangan GCD bagi tatasusunan tertentu, membantu pembaca memahami dan menggunakan algoritma ini dengan lebih baik.

Kandungan soalan

Diberi tatasusunan integer saiz n, dengan n ialah nombor genap. Pilih 2 nombor daripada tatasusunan dan cari gcd. Begitu juga, pilih 2 item daripada item yang tinggal dalam tatasusunan dan cari gcd. Ulangi langkah di atas untuk mencari pasangan gcd. Jumlahkan nilai gcd dan dapatkan jumlah tertinggi.

Kekangan:

n is in range 2 to 20
arr[i] is in range 1 to 10^9

Contoh 1:

arr = [3,4,9,5]

Jawapan:

4

Arahan:

a) gcd of (4,5) is 1
b) gcd of (3,9) is 3
sum = 1+3 = 4. this is the highest possible gcd sum.

Contoh 2:

arr = [1,2,3,4,5,6]

Jawapan:

6

Arahan:

a) gcd of (1,5) is 1
b) gcd of (2,4) is 2
c) gcd of (3,6) is 3
sum = 1+2+3 = 6. this is the highest possible gcd sum.

Ini kod saya:

public static int solve(int[] ar) {
   int n = ar.length;
   Arrays.sort(ar);
   int sum = 0;
   for(int i=0; i<n/2; i++) {
     int a = ar.get(i), b = ar.get(n-i-1);
     int c = gcd(a,b); 
     sum += c;
   }
   return sum;
}

static int gcd(int a, int b)
{
    // if b=0, a is the GCD
    if (b == 0)
        return a;

    // call the gcd() method recursively by
    // replacing a with b and b with
    // modulus(a,b) as long as b != 0
    else
        return gcd(b, a % b);
}

Kod saya berfungsi untuk contoh pertama tetapi memberikan output yang salah untuk contoh kedua. Saya menyahpenyahnya dan mendapati bahawa kaedah yang saya gunakan adalah salah. Apakah cara yang betul untuk menyelesaikan masalah ini?

Penyelesaian

Kami boleh mencari secara rekursif semua cara yang mungkin untuk mengira jumlah gcd. Apa nak buat?

Jika tatasusunan mengandungi hanya dua elemen, kita boleh mengembalikan gcd dua elemen ini sahaja.

Jika ia mengandungi lebih banyak, mari kita ulangi semua pasangan nilai. Untuk setiap pasangan, kami mengira gcdnya, dan kami juga memanggil fungsi kami secara rekursif dengan salinan tatasusunan dengan kedua-dua nilai dialih keluar. Jika kami menambah hasil kedua-dua pengiraan, kami mendapat jumlah gcd untuk pasangan nilai yang dipilih pada masa ini.

Kini kami hanya menjejaki gcd terbaik yang ditemui setakat ini dan mengembalikannya pada penghujungnya.

Ini adalah kod yang (sepatutnya) melakukan perkara itu.

int solve(int[] ar) {
  // if we have only two elements, there's not much else we can do.
  if(ar.length == 2) {
    return gcd(ar[0], ar[1]);
  }

  //keep track of the largest gcd
  int best = 0;
  
  // for every pair of values in the array
  //  make a copy of the array without the pair and call recursively
  for(int i = 0; i < ar.length; i++) {
    for(int j = i + 1; j < ar.length; j++) {
      
      int score = gcd(ar[i], ar[j]);
      
      // make a copy
      int[] ar2 = new int[ar.length - 2];
      int copy_k = 0;
      for(int k=0; k < ar.length; k++) {
        // skip values that we already visited
        if(k == i || k == j) {
          continue;
        }
        
        ar2[copy_k] = ar[k];
        copy_k += 1;
      }
      
      // call recursively
      score += solve(ar2);
      
      if(score > best) // we found a better pair
        best = score;
    }
  }
  
  return best;
}

Algoritma ini agak perlahan. Jika anda perlu mempercepatkan, terdapat sekurang-kurangnya dua bidang yang boleh anda perbaiki:

• Mengira gcd adalah operasi yang mahal. Prapengiraan gcd semua kemungkinan pasangan nilai unik dan menyimpannya dalam peta cincang akan menghapuskan pengiraan berganda.
• Ia menyemak beberapa pilih atur yang mungkin beberapa kali. (cth. memilih pasangan pertama dan kemudian pasangan kedua pada rekursi seterusnya adalah sama seperti memilih pasangan kedua dan kemudian pasangan pertama) Saya mempunyai beberapa idea yang tidak jelas tentang cara menyelesaikan masalah ini, tetapi sudah terlambat malam ini, Harap maaf .

Kemungkinan besar terdapat algoritma yang lebih pantas, itu hanya idea saya.

Editor: Nah, selepas tidur sebentar, saya tiba-tiba faham. Jika kita meninggalkan gelung luar semasa membuat pasangan, kita tidak akan mendapat sebarang pengisihan pendua pasangan. Pada asasnya hanya gantikan i dengan 0 di mana-mana sahaja, seperti ini:

for(int j = 1; j < ar.length; j++) {
    
  int score = gcd(ar[0], ar[j]);
  
  // Make a copy
  int[] ar2 = new int[ar.length - 2];
  int copy_k = 0;
  for(int k=1; k < ar.length; k++) {
    // Skip values that we already visited
    if(k == j) {
      continue;
    }
    
    ar2[copy_k] = ar[k];
    copy_k += 1;
  }
}

Atas ialah kandungan terperinci Cari pasangan GCD untuk tatasusunan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!