Eine Sequenz ist eine Sammlung von Objekten, in unserem Fall eine Sammlung von ganzen Zahlen. Die Aufgabe besteht darin, mithilfe von Additions- und Subtraktionsoperatoren zu bestimmen, ob eine Folge von Elementen durch M teilbar ist.
Gegeben sind eine ganze Zahl M und ein ganzzahliges Array. Überprüft, ob es eine gültige Folge gibt, deren Lösung durch M teilbar ist, indem nur Addition und Subtraktion zwischen Elementen verwendet wird.
Input: M = 2, arr = {1, 2, 5}
Output: TRUE
Erklärung – Für das gegebene Array kann es eine gültige Folge {1 + 2 + 5} = {8} geben, die durch 2 teilbar ist.
Input: M = 4, arr = {1, 2}
Output: FALSE
Erklärung – Für das gegebene Array ist es unmöglich, eine Sequenz zu haben, deren Lösung durch 4 teilbar ist.
Eine einfache Möglichkeit, dieses Problem zu lösen, besteht darin, eine rekursive Funktion zu verwenden, um alle möglichen Sequenzen des Arrays zu finden und dann zu prüfen, ob eine Sequenz durch M teilbar ist.
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
Im folgenden Programm verwenden wir die rekursive Methode, um alle gültigen Sequenzen zu finden und prüfen dann, ob eine gültige Sequenz durch M teilbar ist.
#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
Zeitliche Komplexität – O(2^n) aufgrund der Verwendung von Rekursion.
Raumkomplexität – O(n) aufgrund des rekursiven Stapelraums.
Diese Methode ähnelt der vorherigen rekursiven Brute-Force-Methode, außer dass wir mithilfe von Backtracking den Suchraum zurückverfolgen können, um zu vermeiden, einen Pfad einzuschlagen, von dem wir wissen, dass er keine gültige, durch M teilbare Sequenz hat.
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
Im folgenden Programm verwenden wir Backtracking, um den Suchraum zu beschneiden und die Lösung für das Problem zu finden.
#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
Zeitkomplexität – Die Zeitkomplexität im schlimmsten Fall ist O(2^n), aber aufgrund der Beschneidung des Suchraums ist sie tatsächlich besser als die Brute-Force-Methode.
Raumkomplexität – O(n) aufgrund des rekursiven Stapelraums.
Die gierige Lösung für dieses Problem besteht darin, das Array zunächst in aufsteigender Reihenfolge zu sortieren und dann die Additionsfunktion gierig anzuwenden, wenn die Summe M nicht überschreitet. Diese Methode liefert möglicherweise keine global optimale Lösung, wohl aber eine lokal optimale Lösung.
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
Im folgenden Programm wird ein Array sortiert, um das beste lokale Subarray zu finden, das durch M teilbar ist.
#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
Anhand des Konzepts der dynamischen Programmierung speichern wir in dieser Lösung die Zwischenergebnisse der Auswertung. Wir erstellen eine Tabelle mit N+1 Zeilen und M Spalten, und wenn wir keine Array-Elemente verwenden, ergibt sich im Basisfall %M == 0. Dann iterieren wir modulo M über alle möglichen Reste und aktualisieren die Tabelle.
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
Im folgenden Programm zerlegen wir das Problem in Teilprobleme und lösen sie dann.
#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
Zusammenfassend lässt sich sagen, dass wir, um gültige durch M teilbare Sequenzen zu finden, mehrere Methoden und verschiedene relationale und räumliche Analysen anwenden können, die von O(2^n) im Brute-Force-Fall bis zu O(NM) im dynamischen Fall reichen ist die effektivste Methode.
Das obige ist der detaillierte Inhalt vonÜberprüfen Sie, ob es eine gültige durch M teilbare Folge gibt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Was bedeutet Java-Routing?
Was tun, wenn vom Computermikrofon kein Ton zu hören ist?
Was ist der Unterschied zwischen PHP und Java?
Was bedeutet Root-Server?
js-String in Array umwandeln
So kaufen, verkaufen und handeln Sie Bitcoin
Können Douyin-Funken wieder entzündet werden, wenn sie länger als drei Tage ausgeschaltet waren?
Was ist der Unterschied zwischen USB-C und TYPE-C?
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
