เราจะดูปัญหาที่เราได้รับสตริงตัวเลข และต้องหาว่ามีสตริงย่อยกี่ตัวที่หาร 6 ลงตัวในรูปแบบจำนวนเต็ม ควรสังเกตว่าข้อมูลนำเข้าอยู่ในรูปสตริงที่ประกอบด้วยตัวเลข (จำนวนเต็ม) แต่การตรวจสอบการหารลงตัวจะทำโดยถือว่าเป็นจำนวนเต็มเท่านั้น (ไม่ใช้ค่า ASCII ของสตริงนำเข้า)
ข้อมูลนำเข้า
str = "648"
ข้อมูลส่งออก
คำอธิบาย
สตริงย่อย "6", "48", และ "648" หาร 6 ลงตัว
ข้อมูลนำเข้า
str = "38342"
ข้อมูลส่งออก
4
คำอธิบาย
สตริงย่อย "3834", "342", "834", และ "42" หาร 6 ลงตัว
วิธี Brute-Force
ผู้ใช้สามารถตรวจสอบทุกสตริงย่อยที่เป็นไปได้เพื่อดูว่าหาร 6 ลงตัวหรือไม่ หากสตริงย่อยหารลงตัว เรานับเพิ่ม วิธีนี้จะใช้เวลานานและใช้เวลา O(n^2) ในการทำงาน
ตัวอย่างโค้ด (Brute-Force)
#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; }
ข้อมูลส่งออก
6
วิธีที่มีประสิทธิภาพ (Efficient Approach)
หลักสุดท้ายของตัวเลขต้องหาร 2 ลงตัวเพื่อให้หาร 6 ลงตัว ผลรวมตัวเลขควรหาร 3 ลงตัว โดยติดตามคำตอบที่คำนวณไว้ก่อนหน้านี้ เราอาจใช้ dynamic programming เพื่อค้นหาคำตอบ
ให้ f(i,s) - จำนวนสตริงจากดัชนี i ที่ผลรวมตัวเลข modulo 3 เป็น s ซึ่งให้ Σ f(i,0)
ให้ a เป็นตัวเลขหลักที่ i ของสตริง ตอนนี้ จาก f(i,s) เราต้องหาสตริงย่อยทั้งหมดที่เป็นเลขคู่และเริ่มต้นที่ i + 1 หาก (a+s) หาร 3 ลงตัว สามารถสร้างสตริงย่อยเพิ่มเติมได้หนึ่งตัว ดังนั้นความสัมพันธ์ซ้ำ (recurrence relation) ที่ได้คือ:
f(i,s) = f(i + 1, (s + a)%3) + ( a%2 == 0 AND (a+s)%3 == 0)
ตัวอย่างโค้ด (Efficient)
#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; }
ข้อมูลส่งออก
Number of substrings divisible by 6: 6
Time complexity: O(N)
สรุป
ในบทช่วยสอนนี้ เราเรียนรู้วิธีใช้ dynamic programming เพื่อหาจำนวนสตริงย่อยที่หาร 6 ลงตัวในสตริงตัวเลข โปรแกรมเดียวกันสามารถเขียนในภาษาอื่นๆ เช่น C, Java, Python และอื่นๆ ได้ หวังว่าบทเรียนนี้จะเป็นประโยชน์
