Adakah pembahagi sepunya terbesar bagi mana-mana subset tatasusunan tergolong dalam tatasusunan yang diberikan?

Di sini kita akan melihat soalan yang menarik. Terdapat satu set yang mengandungi N elemen. Kita mesti menjana tatasusunan supaya GCD mana-mana subset tatasusunan terletak dalam set elemen yang diberikan. Had lain ialah tatasusunan yang terhasil tidak boleh melebihi tiga kali panjang koleksi GCD. Sebagai contoh, jika terdapat 4 nombor {2, 4, 6, 12}, maka tatasusunan akan menjadi {2, 2, 4, 2, 6, 2, 12}

Untuk menyelesaikan masalah ini, kita mesti melakukan Isih, kemudian jika GCD adalah sama dengan elemen terkecil koleksi yang diberikan, anda mencipta tatasusunan dengan hanya meletakkan GCD antara setiap elemen. Jika tidak tatasusunan tidak boleh dibentuk.

Algoritma

generateArray(arr, n)

Begin
   answer := empty array
   gcd := gcd of array arr
   if gcd is same as the min element of arr, then
      for each element e in arr, do
         append gcd into answer
         append e into answer
      done
      display answer
   else
      array cannot be formed
   end if
End

Contoh

#include<iostream>
#include<vector>
#include<set>
using namespace std;
int gcd(int a, int b) {
   if (a == 0)
      return b;
   return gcd(b % a, a);
}
int getGCDofArray(vector<int> arr) {
   int result = arr[0];
   for (int i = 1; i < arr.size(); i++)
      result = gcd(arr[i], result);
   return result;
}
void generateArray(vector<int> arr) {
   vector<int> answer;
   int GCD_of_array = getGCDofArray(arr);
   if(GCD_of_array == arr[0]) { //if gcd is same as minimum element
      answer.push_back(arr[0]);
      for(int i = 1; i < arr.size(); i++) { //push min before each
         element
         answer.push_back(arr[0]);
         answer.push_back(arr[i]);
      }
      for (int i = 0; i < answer.size(); i++)
      cout << answer[i] << " ";
   }
   else
   cout << "No array can be build";
}
int main() {
   int n = 4;
   int data[]= {2, 4, 6, 12};
   set<int> GCD(data, data + n);
   vector<int> arr;
   set<int>::iterator it;
   for(it = GCD.begin(); it!= GCD.end(); ++it)
      arr.push_back(*it);
   generateArray(arr);
}

Output

2 2 4 2 6 2 12

Atas ialah kandungan terperinci Adakah pembahagi sepunya terbesar bagi mana-mana subset tatasusunan tergolong dalam tatasusunan yang diberikan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!