Rumah > Artikel > pembangunan bahagian belakang > Semak sama ada terdapat sebarang jujukan yang sah yang boleh dibahagikan dengan M
Jujukan ialah himpunan objek, dalam kes kami ia ialah himpunan integer. Tugasnya adalah untuk menentukan sama ada urutan unsur menggunakan operator tambah dan tolak boleh dibahagikan dengan M.
Diberi integer M dan tatasusunan integer. Menyemak sama ada terdapat urutan yang sah yang penyelesaiannya boleh dibahagikan dengan M hanya menggunakan penambahan dan penolakan antara unsur.
Input: M = 2, arr = {1, 2, 5}
Output: TRUE
Penjelasan - Untuk tatasusunan yang diberikan, mungkin terdapat urutan yang sah {1 + 2 + 5} = {8}, yang boleh dibahagikan dengan 2.
Input: M = 4, arr = {1, 2}
Output: FALSE
Penjelasan - Untuk tatasusunan yang diberikan, adalah mustahil untuk mempunyai urutan yang penyelesaiannya boleh dibahagikan dengan 4.
Cara mudah untuk menyelesaikan masalah ini ialah menggunakan fungsi rekursif untuk mencari semua urutan tatasusunan yang mungkin dan kemudian semak sama ada sebarang jujukan boleh dibahagikan dengan 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
Dalam atur cara berikut, kami menggunakan kaedah rekursif untuk mencari semua jujukan yang sah dan kemudian menyemak sama ada sebarang jujukan yang sah boleh dibahagikan dengan 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
Kerumitan masa - O(2^n) disebabkan penggunaan rekursi.
Kerumitan ruang - O(n) disebabkan oleh ruang tindanan ulangan.
Kaedah ini serupa dengan kaedah rekursif brute-force sebelumnya, kecuali dengan menggunakan penjejakan ke belakang, kita boleh menjejaki ruang carian untuk mengelak daripada menyusuri laluan yang kita tahu tidak mempunyai urutan yang sah yang boleh dibahagikan dengan 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
Dalam program di bawah, kami menggunakan backtracking untuk memangkas ruang carian untuk mencari penyelesaian kepada masalah tersebut.
#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
Kerumitan Masa - Kerumitan masa yang paling teruk ialah O(2^n), tetapi ia sebenarnya lebih baik daripada kaedah brute force kerana pemangkasan ruang carian.
Kerumitan Ruang - O(n) disebabkan oleh ruang tindanan rekursif.
Penyelesaian tamak untuk masalah ini adalah dengan terlebih dahulu menyusun tatasusunan dalam tertib menaik dan kemudian dengan rakus menggunakan fungsi tambah jika jumlahnya tidak melebihi M. Kaedah ini mungkin tidak memberikan penyelesaian optimum global, tetapi ia akan memberikan penyelesaian optimum tempatan.
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
Dalam program berikut, tatasusunan diisih untuk mencari subarray tempatan terbaik yang boleh dibahagikan dengan 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
Menggunakan konsep pengaturcaraan dinamik, dalam penyelesaian ini kami menyimpan hasil perantaraan penilaian. Kami akan mencipta jadual dengan baris N+1 dan lajur M, dan apabila kami tidak menggunakan elemen tatasusunan, kes asas menghasilkan % M == 0. Kemudian melelaran ke atas semua baki modulo M yang mungkin, kami mengemas kini jadual.
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
Dalam program di bawah, kami memecahkan masalah kepada sub-masalah dan kemudian menyelesaikannya.
#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
Untuk meringkaskan, untuk mencari jujukan sah yang boleh dibahagikan dengan M, kami boleh menggunakan berbilang kaedah dan analisis relasi dan ruang yang berbeza, antara O(2^n) dalam kes brute force hingga O(NM) dalam kes dinamik adalah Kaedah yang paling berkesan.
Atas ialah kandungan terperinci Semak sama ada terdapat sebarang jujukan yang sah yang boleh dibahagikan dengan M. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!