ที่นี่เราจะเห็นโปรแกรมที่สามารถตรวจสอบว่าตัวเลขสามารถแบ่งออกเป็นมากกว่าหนึ่งกลุ่มโดยมีผลรวมเท่ากันหรือไม่ สมมติว่าตัวเลขเช่น 74325 จากนั้นสามารถแบ่งออกเป็นสามส่วน (7), (4, 3), (2, 5) ทั้งหมดมีค่า um เท่ากัน
เราต้องทำตามขั้นตอนเหล่านี้เพื่อแก้ปัญหานี้
- ใช้ตัวเลขเป็นสตริง
- ใช้อาร์เรย์เพื่อเก็บผลรวมนำหน้าของอาร์เรย์
- ตอนนี้กำลังข้ามจากองค์ประกอบที่สองไปยังองค์ประกอบสุดท้าย และส่วนแรกจะเป็น 0 ถึง i-1 ซึ่งผลรวมจะถูกวางไว้ที่ prefix_sum[i - 1]
- ใช้ตัวแปรอื่นที่ข้ามจาก 1 ถึง n แล้วบวกผลรวมต่อไป
- หากค่าผลรวมเหมือนกับค่า prefix_sum[i – 1] ในขั้นตอนใดๆ เซ็กเมนต์จะมีผลรวมเท่ากับค่าแรก
- เริ่มต้นค่าผลรวมของเซ็กเมนต์ใหม่เป็น 0 จากนั้นเลื่อนตัวชี้ต่อไป
- หากผลรวมของเซ็กเมนต์มากกว่า prefix_sum[i – 1] ในขั้นใดๆ ให้ทำลายลูป
- หากเราไปถึงจุดหมายสุดท้าย และหากผลรวมของส่วนสุดท้ายเท่ากับผลรวมของส่วนแรก ก็สามารถแบ่งออกเป็นส่วนๆ ของผลรวมที่เท่ากันได้
ตัวอย่าง
#include <iostream>
using namespace std;
bool canBeSegmented(string str) {
int n = str.length();
int prefix_sum[n];
prefix_sum[0] = str[0] - '0';
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + (str[i] - '0');
}
for (int i = 1; i <= n - 1; i++) {
int sum = prefix_sum[i - 1];
int prev_sum = 0;
int it = i;
bool flag = false;
while (it < n) {
prev_sum += str[it] - '0';
if (prev_sum == sum) {
prev_sum = 0;
flag = true;
} else if (prev_sum > sum) {
break;
}
it++;
}
if (prev_sum == 0 && it == n && flag) {
return true;
}
}
return false;
}
int main() {
string s = "74325";
if (canBeSegmented(s))
cout << "Yes, This can be segmented into more than two segments";
else
cout << "No, This can not be segmented into more than two segments";
} ผลลัพธ์
Yes, This can be segmented into more than two segments
