Une séquence est une collection d'objets, dans notre cas c'est une collection d'entiers. La tâche consiste à déterminer si une séquence d'éléments utilisant des opérateurs d'addition et de soustraction est divisible par M.
Étant donné un entier M et un tableau d'entiers. Vérifie s'il existe une séquence valide dont la solution est divisible par M en utilisant uniquement l'addition et la soustraction entre les éléments.
Input: M = 2, arr = {1, 2, 5}
Output: TRUE
Explication - Pour le tableau donné, il peut y avoir une séquence valide {1 + 2 + 5} = {8}, qui est divisible par 2.
Input: M = 4, arr = {1, 2}
Output: FALSE
Explication - Pour le tableau donné, il est impossible d'avoir une séquence dont la solution est divisible par 4.
Un moyen simple de résoudre ce problème consiste à utiliser une fonction récursive pour trouver toutes les séquences possibles du tableau, puis à vérifier si une séquence est divisible par 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
Dans le programme suivant, nous utilisons la méthode récursive pour trouver toutes les séquences valides, puis vérifions si une séquence valide est divisible par 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
Complexité temporelle - O(2^n) en raison de l'utilisation de la récursivité.
Complexité spatiale - O(n) en raison de l'espace de la pile de récursion.
Cette méthode est similaire à la méthode récursive précédente par force brute, sauf qu'en utilisant le retour en arrière, nous pouvons revenir en arrière dans l'espace de recherche pour éviter de suivre un chemin dont nous savons qu'il n'a pas de séquence valide divisible par 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
Dans le programme ci-dessous, nous utilisons le backtracking pour élaguer l'espace de recherche afin de trouver la solution au problème.
#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
Complexité temporelle - La complexité temporelle dans le pire des cas est O(2^n), mais elle est en fait meilleure que la méthode par force brute en raison de l'élagage de l'espace de recherche.
Complexité spatiale - O(n) en raison de l'espace de pile récursif.
La solution gourmande à ce problème consiste à trier d'abord le tableau par ordre croissant, puis à appliquer goulûment la fonction d'addition si la somme ne dépasse pas M. Cette méthode ne donnera peut-être pas une solution globalement optimale, mais elle donnera une solution optimale locale.
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
Dans le programme suivant, un tableau est trié pour trouver le meilleur sous-tableau local divisible par 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
En utilisant le concept de programmation dynamique, dans cette solution nous stockons les résultats intermédiaires de l'évaluation. Nous allons créer un tableau avec N+1 lignes et M colonnes, et lorsque nous n'utilisons pas d'éléments de tableau, le cas de base donne % M == 0. Puis en itérant sur tous les restes possibles modulo M, nous mettons à jour le tableau.
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
Dans le programme ci-dessous, nous divisons le problème en sous-problèmes puis les résolvons.
#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
Pour résumer, afin de trouver des séquences valides divisibles par M, nous pouvons appliquer plusieurs méthodes et différentes analyses relationnelles et spatiales, allant de O(2^n) dans le cas de la force brute à O(NM) dans le cas de la programmation dynamique. est la méthode la plus efficace.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Quelle résolution est 1080p ?
Comment exécuter le projet phpstudy
psrpc.dll solution introuvable
Le dernier classement des dix principales bourses du cercle des devises
Raisons pour lesquelles l'écran tactile du téléphone portable échoue
Le WiFi ne montre aucun accès à Internet
Introduction au protocole xmpp
qu'est-ce que la fonction
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
