資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究檢查是否有任何有效的序列可以被 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 <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;
}
輸出
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 <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;
}
輸出
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 <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;
}
輸出
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 <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;
}
輸出
TRUE
結論
總之，為了找到可以被 M 整除的有效序列，我們可以應用多種方法，其時間和空間分析各不相同，從暴力法的 O(2^n) 到動態規劃的 O(NM)，動態規劃是最有效的方法。
更新於：2023年7月25日
92 次瀏覽
廣告