C++ แบ่งตัวเลขเป็นสองส่วนที่หารลงตัว

ในปัญหานี้ เราได้รับสตริงที่สามารถตีความเป็นตัวเลข ตอนนี้เราต้องแบ่งสตริงนั้นออกเป็นสองส่วน โดยส่วนแรกหารด้วย A ลงตัว และส่วนที่สองหารด้วย B ลงตัว (A และ B เป็นจำนวนเต็มที่กำหนด) เช่น

Input : str = "123", a = 12, b = 3 Output : YES 12 3 "12" หาร 12 ลงตัว และ "3" หาร 3 ลงตัว
Input : str = "1200", a = 4, b = 3 Output : YES 12 00
Input : str = "125", a = 12, b = 3 Output : NO

ในปัญหานี้ เราจะทำ Pre-calculation (คำนวณล่วงหน้า) บางอย่างที่จะทำให้โปรแกรมเร็วขึ้น และทำงานได้กับข้อจำกัดที่สูงกว่า

วิธีการแก้ปัญหา

ในวิธีนี้ เราจะรันลูปสองครั้งผ่านสตริง ครั้งแรกจากหน้าไปหลัง และครั้งที่สองจากหลังมาหน้า ตอนนี้ที่ทุกจุด เราหา Mod ของจำนวนเต็มที่สร้างขึ้นกับ a ในลูปแรก และกับ b ในลูปที่สอง จากนั้นเราสามารถหาคำตอบได้

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 

void divisionOfString(string &str, int a, int b){ 
    int n = str.length(); 
    vector<int> mod_a(n+1, 0); 
    mod_a[0] = (str[0] - '0')%a; 
    for (int i=1; i<n; i++) 
        mod_a[i] = ((mod_a[i-1]*10)%a + (str[i]-'0'))%a; 
    vector<int> mod_b(n+1, 0); 
    mod_b[n-1] = (str[n-1] - '0')%b; 
    int power10 = 10; 
    for (int i= n-2; i>=0; i--){ 
        mod_b[i] = (mod_b[i+1] + (str[i]-'0')*power10)%b; 
        power10 = (power10 * 10) % b; 
    } 
    for (int i=0; i<n-1; i++){ 
        if (mod_a[i] != 0) continue; 
        if (mod_b[i+1] == 0){ 
            cout << "YES\n"; 
            for (int k=0; k<=i; k++) cout << str[k]; 
            cout << " "; 
            for (int k=i+1; k < n; k++) cout << str[k]; 
            return; 
        } 
    } 
    cout << "NO\n"; 
} 

int main(){ 
    string str = "123"; 
    int a = 12, b = 3; 
    divisionOfString(str, a, b); 
    return 0; 
}

ผลลัพธ์

YES 12 3

คำอธิบายโค้ด

ในวิธีนี้ เราคำนวณเศษของจำนวนที่สร้างขึ้นที่ทุกจุดแบ่ง ส่วนแรกต้องหาร a ลงตัว จึงรันลูปไปข้างหน้าเก็บ Mod กับ a ส่วนที่สองต้องหาร b ลงตัว จึงรันลูปถอยหลังเก็บ Mod กับ b ตอนนี้เรารู้ว่าถ้า Mod กับ a ที่ตำแหน่งใดเป็น 0 และ Mod กับ b ของตำแหน่งถัดไปก็เป็น 0 นั่นคือจุดแบ่งของเรา จึงพิมพ์ออกมา

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหาการแบ่งตัวเลขเป็นสองส่วนที่หารลงตัว เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์