Heim > Artikel > Backend-Entwicklung > Überprüfen Sie, ob es eine gültige durch M teilbare Folge gibt
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!