Chúng ta sẽ xem xét một vấn đề trong đó chúng ta được cung cấp 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 ở định dạng số nguyên. Cần lưu ý rằng đầu vào ở dạng Chuỗi được tạo từ các số (số nguyên). Tuy nhiên, việc kiểm tra tính chia hết sẽ được thực hiện khi chỉ coi nó là một số nguyên (không sử dụng giá trị ASCII của đầu vào chuỗi).
Đầ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
các chuỗi con “3834”, “342”, “834” và “42” chia hết cho 6.
Phương pháp tiếp cận vũ phu
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 có thể chia hết, chúng tôi sẽ đếm thêm. Phương pháp này sẽ mất nhiều thời gian hơn để giải quyết vấ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
Phương pháp 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 các chữ số phải là 3. Bằng cách theo dõi các câu trả lời đã tính trước đó, chúng tôi có thể sử dụng lập trình động để tìm ra các giải pháp.
Cho f (i, s) - số chuỗi từ chỉ số thứ i có tổng các chữ số của modulo 3 là s cho ta Σin-1 f (i, 0).
Gọi 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 chẵn và bắt đầu bằng i + 1. Nếu (a + s) chia hết cho 3, một chuỗi con bổ sung có thể được tạo ra. ,
f (i, s) =f (i + 1, (s + a)% 3) + (a% 2 ==0 VÀ (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]){
// when reached end of string.
if (i == strlen(str))
return 0;
// if already computed then return result.
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);
// dp array to store all states.
int dp[n+1][3];
memset(dp, -1, sizeof dp);
int count = 0;
for (int i = 0; i < n; i++){
// if any position contains 0 increment count.
if (str[i] == '0')
count++;
// Passing previous sum modulo 3 = 0 to recursive function.
else
count += find(i, 0, str, dp);
}
cout << "Number of substrings divisible by 6: " << count << endl;
return 0;
} Đầu ra
Number of substrings divisible by 6: 6
Độ phức tạp về 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 lập trình động để khám phá số chuỗi con chia hết cho 6 trong một chuỗi số nguyên. Cùng một chương trình có thể được viết bằng các ngôn ngữ khác nhau như C, Java, Python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài học này có ích.