Semak sama ada terdapat sebarang jujukan yang sah yang boleh dibahagikan dengan M

Jujukan ialah himpunan objek, dalam kes kami ia ialah himpunan integer. Tugasnya adalah untuk menentukan sama ada urutan unsur menggunakan operator tambah dan tolak boleh dibahagikan dengan M.

Pernyataan Masalah

Diberi integer M dan tatasusunan integer. Menyemak sama ada terdapat urutan yang sah yang penyelesaiannya boleh dibahagikan dengan M hanya menggunakan penambahan dan penolakan antara unsur.

Contoh 1

Input: M = 2, arr = {1, 2, 5}

Output: TRUE

Penjelasan - Untuk tatasusunan yang diberikan, mungkin terdapat urutan yang sah {1 + 2 + 5} = {8}, yang boleh dibahagikan dengan 2.

Contoh 2

Input: M = 4, arr = {1, 2}

Output: FALSE

Penjelasan - Untuk tatasusunan yang diberikan, adalah mustahil untuk mempunyai urutan yang penyelesaiannya boleh dibahagikan dengan 4.

Kaedah 1: Kaedah kejam

Cara mudah untuk menyelesaikan masalah ini ialah menggunakan fungsi rekursif untuk mencari semua urutan tatasusunan yang mungkin dan kemudian semak sama ada sebarang jujukan boleh dibahagikan dengan M.

pseudokod

procedure divisible (M, arr[], index, sum, n)
   if index == n
      if sum is a multiple of M
         ans = TRUE
      end if
      ans = false
   end if
   divisible(M, arr, index + 1, sum + arr[index], n) or divisible(M, arr, index + 1, sum - arr[index], n)
end procedure

Contoh: Pelaksanaan C++

Dalam atur cara berikut, kami menggunakan kaedah rekursif untuk mencari semua jujukan yang sah dan kemudian menyemak sama ada sebarang jujukan yang sah boleh dibahagikan dengan M.

#include <bits/stdc++.h>
using namespace std;

// Recusive function to find if a valid sequence is divisible by M or not
bool divisible(int M, int arr[], int index, int sum, int n){

   // Cheking the divisiblilty by M when the array ends
   if (index == n)  {
      if (sum % M == 0){
         return true;
      }
      return false;
   }
   
   // If either of addition or subtraction is true, return true
   return divisible(M, arr, index + 1, sum + arr[index], n) || divisible(M, arr, index + 1, sum - arr[index], n);
}
int main(){
   int M = 4, arr[2] = {1, 5};
   if (divisible(M, arr, 0, 0, 2)){
      cout << "TRUE";
   }
   else{
      cout << " FALSE";
   }
   return 0;
}

Output

TRUE

Kerumitan masa - O(2^n) disebabkan penggunaan rekursi.

Kerumitan ruang - O(n) disebabkan oleh ruang tindanan ulangan.

Kaedah 2: Undur

Kaedah ini serupa dengan kaedah rekursif brute-force sebelumnya, kecuali dengan menggunakan penjejakan ke belakang, kita boleh menjejaki ruang carian untuk mengelak daripada menyusuri laluan yang kita tahu tidak mempunyai urutan yang sah yang boleh dibahagikan dengan M.

pseudokod

procedure divisible (M, arr[], index, sum, n)
   if index == n
      if sum is a multiple of M
         ans = TRUE
      end if
      ans = false
   end if
   if divisible(M, arr, index + 1, sum + arr[index], n)
      ans = true
   end if
   if divisible(M, arr, index + 1, sum - arr[index], n)
      ans = true
   end if
   ans = false
end procedure

Contoh: Pelaksanaan C++

Dalam program di bawah, kami menggunakan backtracking untuk memangkas ruang carian untuk mencari penyelesaian kepada masalah tersebut.

#include <bits/stdc++.h>
using namespace std;

// Function to find if a valid sequence is divisible by M or not
bool divisible(int M, int arr[], int index, int sum, int n){

   // Cheking the divisiblilty by M when the array ends
   if (index == n){
      if (sum % M == 0){
         return true;
      }
      return false;
   }
   
   // Checking the divisibility of sum + arr[index]
   if (divisible(M, arr, index + 1, sum + arr[index], n)){
      return true;
   }
   
   // Checking the divisibility of sum - arr[index]
   if (divisible(M, arr, index + 1, sum - arr[index], n)){
      return true;
   }
   return false;
}
int main(){
   int M = 4, arr[2] = {1, 5};
   if (divisible(M, arr, 0, 0, 2)){
      cout << "TRUE";
   }
   else{
      cout << " FALSE";
   }
   return 0;
}

Output

TRUE

Kerumitan Masa - Kerumitan masa yang paling teruk ialah O(2^n), tetapi ia sebenarnya lebih baik daripada kaedah brute force kerana pemangkasan ruang carian.

Kerumitan Ruang - O(n) disebabkan oleh ruang tindanan rekursif.

Kaedah 3: Kaedah tamak

Penyelesaian tamak untuk masalah ini adalah dengan terlebih dahulu menyusun tatasusunan dalam tertib menaik dan kemudian dengan rakus menggunakan fungsi tambah jika jumlahnya tidak melebihi M. Kaedah ini mungkin tidak memberikan penyelesaian optimum global, tetapi ia akan memberikan penyelesaian optimum tempatan.

pseudokod

procedure divisible (M, arr[])
   sum = 0
   for i = 1 to end of arr
      sum = sum + arr[i]
   if sum is divisible by M
      ans = true
   end if
   sort array arr[]
   i = 0
   j = last index of array
   while i < j
      if arr[j] - arr[i] is divisible by M
         ans = true
      end if
      if sum % M == (sum - arr[j]) % M
         sum = sum - arr[j]
         j = j - 1
      else
         sum = sum - arr[i]
         i = i + 1
      end if
   ans = false
end procedure

Contoh: Pelaksanaan C++

Dalam program berikut, tatasusunan diisih untuk mencari subarray tempatan terbaik yang boleh dibahagikan dengan M.

#include <bits/stdc++.h>
using namespace std;

// Greedy function to find if a valid sequence is divisible by M or not
bool divisible(int M, vector<int> &arr){
   int sum = 0;
   for (int i = 0; i < arr.size(); i++) {
      sum += arr[i];
   }
   
   // Checking if sumof all elements is divisible by M
   if (sum % M == 0){
      return true;
   }
   
   sort(arr.begin(), arr.end());
   int i = 0, j = arr.size() - 1;
   while (i < j){
   
      // Checking if the difference between the largest and smallest element at a time in the array is divisible by M
      if ((arr[j] - arr[i]) % M == 0){
         return true;
      }
      
      // Removing either the largest or smallest element based on which does not affect the sum's divisibility
      if (sum % M == (sum - arr[i]) % M){
         sum -= arr[i];
         i++;
      }
      else{
         sum -= arr[j];
         j--;
      }
   }
   return false;
}
int main(){
   int M = 4;
   int array[2] = {1, 3};
   vector<int> arr(array, array + 2);
   if (divisible(M, arr)){
      cout << "TRUE";
   }
   else{
      cout << " FALSE";
   }
   return 0;
}

Output

TRUE

Kaedah 4: Pengaturcaraan Dinamik

Menggunakan konsep pengaturcaraan dinamik, dalam penyelesaian ini kami menyimpan hasil perantaraan penilaian. Kami akan mencipta jadual dengan baris N+1 dan lajur M, dan apabila kami tidak menggunakan elemen tatasusunan, kes asas menghasilkan % M == 0. Kemudian melelaran ke atas semua baki modulo M yang mungkin, kami mengemas kini jadual.

pseudokod

procedure divisible (arr[], M , N)
   dp[N+1][M] = false
   dp[0][0] = true 
   for i = 1 to N
      for i = j to M
         mod = arr[ i- 1] % M
         dp[i][j] = dp[i - 1][(j - mod + M) % M] or dp[i - 1][(j + mod) % M]
   ans = dp[N][0]
end procedure

Contoh: Pelaksanaan C++

Dalam program di bawah, kami memecahkan masalah kepada sub-masalah dan kemudian menyelesaikannya.

#include <bits/stdc++.h>
using namespace std;

// Function to find if a valid sequence is divisible by M or not
bool divisible(int arr[], int M, int N){

   // Creating the dp table of size N+1 * M
   vector<vector<bool> > dp(N + 1, vector<bool>(M, false));
   
   // Base case
   dp[0][0] = true;
   
   // For each element iterating over all possible remainders j modulo M
   for (int i = 1; i <= N; i++){
      for (int j = 0; j < M; j++){
         int mod = arr[i - 1] % M;
         
         // Either exclude or include the current element in the table
         dp[i][j] = dp[i - 1][(j - mod + M) % M] || dp[i - 1][(j + mod) % M];
      }
   }
   return dp[N][0];
}
int main(){
   int M = 4;
   int arr[2] = {1, 3};
   if (divisible(arr, M, 2)){
      cout << "TRUE";
   }
   else{
      cout << " FALSE";
   }
   return 0;
}

Output

TRUE

Kesimpulan

Untuk meringkaskan, untuk mencari jujukan sah yang boleh dibahagikan dengan M, kami boleh menggunakan berbilang kaedah dan analisis relasi dan ruang yang berbeza, antara O(2^n) dalam kes brute force hingga O(NM) dalam kes dinamik adalah Kaedah yang paling berkesan.

Atas ialah kandungan terperinci Semak sama ada terdapat sebarang jujukan yang sah yang boleh dibahagikan dengan M. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!