檢查是否有任何有效的序列可以被M整除-C++-PHP中文網

檢查是否有任何有效的序列可以被M整除

WBOY

發布： 2023-09-11 14:37:24

轉載

715 人瀏覽過

檢查是否有任何有效的序列可以被M整除

序列是物件的集合，在我們的例子中，它是整數的集合。任務是判斷元素內使用加減運算子的序列是否能被 M 整除。

問題陳述

給定一個整數 M 和一個整數陣列。僅使用元素之間的加法和減法檢查是否存在其解可被 M 整除的有效序列。

範例 1

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

登入後複製

Output: TRUE

登入後複製

解釋 - 對於給定的數組，可能存在有效序列 {1 2 5} = {8}，且可被 2 整除。

範例 2

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

登入後複製

Output: FALSE

登入後複製

解釋 - 對於給定的數組，不可能存在其解可被 4 整除的序列。

方法 1：暴力方法

解決這個問題的簡單方法是使用遞歸函數來尋找陣列的所有可能序列，然後檢查是否有任何序列可被 M 整除。

虛擬程式碼

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

登入後複製

範例：C 實作

在下面的程式中，我們使用遞歸方法來尋找所有有效序列，然後檢查是否有任何有效序列可被 M 整除。

#include 
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;
}

登入後複製

輸出

TRUE

登入後複製

時間複雜度 - O(2^n) 由於使用了遞迴。

空間複雜度 - O(n) 由於遞歸堆疊空間。

方法 2：回溯

此方法類似於先前的強力遞歸方法，不同之處在於使用回溯，我們可以回溯搜尋空間，以免走上我們知道不具有可被 M 整除的有效序列的路徑。

虛擬程式碼

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

登入後複製

範例：C 實作

在下面的程式中，我們使用回溯來修剪搜尋空間，以找到問題的解決方案。

#include 
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;
}

登入後複製

輸出

TRUE

登入後複製

時間複雜度 - 最壞情況下的時間複雜度為 O(2^n)，但實際上由於搜尋空間的修剪，它比暴力方法更好。

空間複雜度 - 由於遞歸堆疊空間而導致的 O(n)。

方法 3：貪婪方法

這個問題的貪心解法是先將陣列依升序排序，然後在總和不超過 M 的情況下貪婪地應用加法函數。這種方法可能不會給出全域最優解，但會給出局部最優解。

虛擬程式碼

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

登入後複製

範例：C 實作

在下面的程式中，將陣列進行排序以找到可被 M 整除的最佳局部子陣列。

#include 
using namespace std;

// Greedy function to find if a valid sequence is divisible by M or not
bool divisible(int M, vector &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 arr(array, array + 2);
   if (divisible(M, arr)){
      cout << "TRUE";
   }
   else{
      cout << " FALSE";
   }
   return 0;
}

登入後複製

輸出

TRUE

登入後複製

方法 4：動態規劃

使用動態規劃的概念，在此解決方案中我們儲存評估的中間結果。我們將建立一個包含 N 1 行和 M 列的表，並且當我們不使用陣列元素時，結果 % M == 0 的基本情況。然後迭代模 M 的所有可能餘數，我們更新表格。

虛擬程式碼

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

登入後複製

範例：C 實作

在下面的程式中，我們將問題分解為子問題，然後解決它們。

#include 
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 > dp(N + 1, vector(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;
}

登入後複製