ในปัญหานี้ เราจะได้สมการเชิงเส้นของตัวแปร n สำหรับรูปแบบ
coeff1(var1) + coeff2(var2) + … + coeffn(varn) = value
หาจำนวนคำตอบของสมการเชิงเส้นของตัวแปร n ตัว
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
coeff[] = {3, 1}, value = 4 ผลลัพธ์
1
คำอธิบาย
Equation : 3x + y = 4. Solution, x = 0, y = 4.
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการประเมินค่าของสมการ จากนั้นอัปเดตค่าโดยเรียกซ้ำ หากค่าเป็น 0 จำนวนโซลูชันจะเท่ากับ 1 มิฉะนั้นจะเกิดซ้ำด้วยค่าโดยการลบค่า coeff
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<iostream>
using namespace std;
int countSolutionsEq(int coeff[], int start, int end, int value) {
if (value == 0)
return 1;
int coefCount = 0;
for (int i = start; i <= end; i++)
if (coeff[i] <= value)
coefCount += countSolutionsEq(coeff, i, end, value -
coeff[i]);
return coefCount;
}
int main() {
int coeff[] = {3, 5, 1, 2};
int value = 6;
int n = sizeof(coeff) / sizeof(coeff[0]);
cout<<"The number of solutions of the linear equation is "<<countSolutionsEq(coeff, 0, n - 1, value);
return 0;
} ผลลัพธ์
The number of solutions of the linear equation is 8
