Chúng ta sẽ xem xét một bài toán mà trong đó chúng ta được cho một chuỗi số nguyên và phải xác định có bao nhiêu chuỗi con chia hết cho 6 dưới dạng số nguyên. Cần lưu ý rằng đầu vào là dạng Chuỗi gồm các số (số nguyên). Tuy nhiên, kiểm tra chia hết sẽ được thực hiện coi nó như một số nguyên (không sử dụng giá trị ASCII của chuỗi đầu vào).
Đầu vào
str = "648"
Đầu ra
Giải thích
chuỗi con "6", "48", và "648" chia hết cho 6.
Đầu vào
str = "38342"
Đầu ra
4
Giải thích
chuỗi con "3834", "342", "834", và "42" chia hết cho 6.
Cách tiếp cận Brute-Force
Người dùng có thể kiểm tra mọi chuỗi con có thể có để xem nó có chia hết cho sáu hay không. Nếu chuỗi con chia hết, chúng ta thêm vào đếm. Phương pháp này sẽ mất nhiều thời gian hơn để giải quyết bài toán và mất O(n2) thời gian để hoàn thành nhiệm vụ.
Ví dụ
#include <bits/stdc++.h> using namespace std; int str_to_int (string str, int i, int j) { int temp = 0; for (; i <= j; i++) { temp = temp * 10 + (str[i] - '0'); } return temp; } int main () { char str[] = "24661"; int n = strlen (str); int count = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int temp = str_to_int (str, i, j); if (temp % 6 == 0) count++; } } cout << count << endl; return 0; }Đầu ra
6
Cách tiếp cận Hiệu quả
Chữ số cuối cùng của một số phải chia hết cho 2 để nó chia hết cho 6. Tổng số chữ số phải chia hết cho 3. Bằng cách theo dõi các câu trả lời đã tính trước, chúng ta có thể sử dụng quy hoạch động để khám phá các giải pháp.
Cho f(i,s) - số chuỗi từ chỉ số i có tổng chữ số modulo 3 là s cho Σin-1 f(i,0).
Cho a là chữ số thứ i của một chuỗi; Bây giờ, từ f(i,s), chúng ta cần tìm tất cả các chuỗi con là số chẵn và bắt đầu từ i + 1. Nếu (a+s) chia hết cho 3, một chuỗi con bổ sung có thể được tạo ra. Vì vậy, mối quan hệ hồi quy của chúng ta hình thành,
f(i,s) = f(i + 1, (s + a)%3) + ( a%2 == 0 AND (a+s)%3 == 0).
Ví dụ 2
#include <bits/stdc++.h> using namespace std; int find(int i, int s, char str[], int dp[][3]){ // khi đến cuối chuỗi. if (i == strlen(str)) return 0; // nếu đã tính toán thì trả về kết quả. if (dp[i][s] != -1) return dp[i][s]; int a = str[i] - '0'; int ans = ((a+s)%3 == 0 && a%2 == 0) + find(i+1, (s+a)%3, str, dp); return dp[i][s] = ans; } int main(){ char str[] = "24661"; int n = strlen(str); // mảng dp để lưu tất cả các trạng thái. int dp[n+1][3]; memset(dp, -1, sizeof dp); int count = 0; for (int i = 0; i < n; i++){ // nếu bất kỳ vị trí nào chứa 0 thì tăng count. if (str[i] == '0') count++; // Truyền tổng trước modulo 3 = 0 cho hàm đệ quy. else count += find(i, 0, str, dp); } cout << "Số chuỗi con chia hết cho 6: " << count << endl; return 0; }Đầu ra
Số chuỗi con chia hết cho 6: 6
Độ phức tạp thời gian: O(N)
Kết luận
Trong hướng dẫn này, chúng ta đã học cách sử dụng quy hoạch động để tìm số chuỗi con chia hết cho 6 trong chuỗi số nguyên. Chương trình tương tự có thể viết bằng các ngôn ngữ khác như C, Java, Python và những ngôn ngữ khác. Hy vọng bạn thấy bài học này hữu ích.