12.16 Program 7: Linear Diophantine Equations In this PROGRAM, you will be solving linear Diophantine equations recursively. A linear Diophantine equation is an equation in the form: ax + by = c where a, b, and c are all integers and the solutions will also be integers. See the following entry in Wikipedia: Linear Diophantine equations. You will be solving this using the recursive version of the Extended Euclidean algorithm for finding the integers x and y in Bezout's identity: ax + by = gcd (a,b) • You will need a Greatest Common Divisor helper function gcd(int x, int y): A recursive algorithm for GCD: the GCD of x and y is y if x mod y is 0 otherwise the GCD is the GCD of y and the remainder of x/y Required Recursive Function /* Returns true if a solution was found and false if there is no solution. x and y will contain a solution if a solution was found. This function will NOT output anything. */ bool diophantine (int a, int b, int c, int &x, int &y); Basic Algorithm • If gcd(a,b) does not divide c, then there is no solution. • If b divides a (the remainder of a / bis e), then you can just divide by b to get the solution: x = 0, y = c / b. • Otherwise (b does not divide a), through a substitution method, we can come up with a simpler version of the original problem and solve the simpler problem using recursion.
12.16 Program 7: Linear Diophantine Equations In this PROGRAM, you will be solving linear Diophantine equations recursively. A linear Diophantine equation is an equation in the form: ax + by = c where a, b, and c are all integers and the solutions will also be integers. See the following entry in Wikipedia: Linear Diophantine equations. You will be solving this using the recursive version of the Extended Euclidean algorithm for finding the integers x and y in Bezout's identity: ax + by = gcd (a,b) • You will need a Greatest Common Divisor helper function gcd(int x, int y): A recursive algorithm for GCD: the GCD of x and y is y if x mod y is 0 otherwise the GCD is the GCD of y and the remainder of x/y Required Recursive Function /* Returns true if a solution was found and false if there is no solution. x and y will contain a solution if a solution was found. This function will NOT output anything. */ bool diophantine (int a, int b, int c, int &x, int &y); Basic Algorithm • If gcd(a,b) does not divide c, then there is no solution. • If b divides a (the remainder of a / bis e), then you can just divide by b to get the solution: x = 0, y = c / b. • Otherwise (b does not divide a), through a substitution method, we can come up with a simpler version of the original problem and solve the simpler problem using recursion.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
100%
C++
given main function
int main() {
int a, b, c, x, y;
cout << "Enter a b c" << endl;
cin >> a >> b >> c;
cout << endl;
cout << "Result: ";
if (diophantine(a, b, c, x, y)) {
cout << x << " " << y << endl;
}
else {
cout << "No solution!" << endl;
}
return 0;
}
![12.16 Program 7: Linear Diophantine Equations
In this PROGRAM, you will be solving linear Diophantine equations recursively.
A linear Diophantine equation is an equation in the form:
ax + by =c
where a, b, and c are all integers and the solutions will also be integers.
See the following entry in Wikipedia: Linear Diophantine equations.
You will be solving this using the recursive version of the Extended Euclidean algorithm for finding the integers x and y in Bezout's identity:
ax + by = gcd (a, b)
• You will need a Greatest Common Divisor helper function gcd(int x, int y):
A recursive algorithm for GCD:
the GCD of x and y is y if x mod y is 0
otherwise the GCD is the GCD of y and the remainder of x/y
Required Recursive Function
/* Returns true if a solution was found and false if there is no solution.
x and y will contain a solution if a solution was found.
This function will NOT output anything.
*/
bool diophantine (int a, int b, int c,
int &X,
int &y);
Basic Algorithm
• If gcd(a,b) does not divide c, then there is no solution.
• If b divides a (the remainder of a / bis e), then you can just divide by b to get the solution: x = 0, y = c / b.
• Otherwise (b does not divide a), through a substitution method, we can come up with a simpler version of the original problem and
solve the simpler problem using recursion.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F672bf286-8abe-4b07-9ca1-0d5b2612956c%2Fd9d1f093-953b-46eb-ab6a-4cd1e59bc2ad%2F47i0dcn_processed.png&w=3840&q=75)
Transcribed Image Text:12.16 Program 7: Linear Diophantine Equations
In this PROGRAM, you will be solving linear Diophantine equations recursively.
A linear Diophantine equation is an equation in the form:
ax + by =c
where a, b, and c are all integers and the solutions will also be integers.
See the following entry in Wikipedia: Linear Diophantine equations.
You will be solving this using the recursive version of the Extended Euclidean algorithm for finding the integers x and y in Bezout's identity:
ax + by = gcd (a, b)
• You will need a Greatest Common Divisor helper function gcd(int x, int y):
A recursive algorithm for GCD:
the GCD of x and y is y if x mod y is 0
otherwise the GCD is the GCD of y and the remainder of x/y
Required Recursive Function
/* Returns true if a solution was found and false if there is no solution.
x and y will contain a solution if a solution was found.
This function will NOT output anything.
*/
bool diophantine (int a, int b, int c,
int &X,
int &y);
Basic Algorithm
• If gcd(a,b) does not divide c, then there is no solution.
• If b divides a (the remainder of a / bis e), then you can just divide by b to get the solution: x = 0, y = c / b.
• Otherwise (b does not divide a), through a substitution method, we can come up with a simpler version of the original problem and
solve the simpler problem using recursion.
![Substitution method
ax + by = c
Now, we can define a as:
a = bg + r
where q is (a / b) (using integer division) and r is the remainder (a % b).
Substituting (bq + r) in for a now:
(bg + r)x + by = c
which is the same as
b (сх + y) + rx 3D с
and now we have the equation in the same form, only with smaller coefficients:
bu +
rv = c
with u = qx + y and v = x
Finally, you recursively call your function on this simpler version of the original problem. Don't forget that this recursive call will actually
solve for u and v in this case, so you still have to solve for x and y to get the solution to the original problem:
x = v
y = u - qx
Linear Diophantine Example
Example showing steps of algorithm: LINK
Input/Output Test Samples
Here are some examples you can test your function on:
Input (a b c)
| Results (x y)
| 28 7 49o
I0 70
| 1024 96 2048
| -64 704
| No solution!
| 11 11 2010
| 1984 3070 1
| 395 252 1
| No solution!
| -37 58
| -6 4
I0 -2
| 4 0
| 25 38 2
| 200 -2 4
| 25 75 100
| 25 75 1000
| 25 75 1
| 40 0
| No solution!
|0 -10
| -10 -10 100
| 12 24 48
| 4 0
| 5 -29 6
| 36 6](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F672bf286-8abe-4b07-9ca1-0d5b2612956c%2Fd9d1f093-953b-46eb-ab6a-4cd1e59bc2ad%2F68n7vf3_processed.png&w=3840&q=75)
Transcribed Image Text:Substitution method
ax + by = c
Now, we can define a as:
a = bg + r
where q is (a / b) (using integer division) and r is the remainder (a % b).
Substituting (bq + r) in for a now:
(bg + r)x + by = c
which is the same as
b (сх + y) + rx 3D с
and now we have the equation in the same form, only with smaller coefficients:
bu +
rv = c
with u = qx + y and v = x
Finally, you recursively call your function on this simpler version of the original problem. Don't forget that this recursive call will actually
solve for u and v in this case, so you still have to solve for x and y to get the solution to the original problem:
x = v
y = u - qx
Linear Diophantine Example
Example showing steps of algorithm: LINK
Input/Output Test Samples
Here are some examples you can test your function on:
Input (a b c)
| Results (x y)
| 28 7 49o
I0 70
| 1024 96 2048
| -64 704
| No solution!
| 11 11 2010
| 1984 3070 1
| 395 252 1
| No solution!
| -37 58
| -6 4
I0 -2
| 4 0
| 25 38 2
| 200 -2 4
| 25 75 100
| 25 75 1000
| 25 75 1
| 40 0
| No solution!
|0 -10
| -10 -10 100
| 12 24 48
| 4 0
| 5 -29 6
| 36 6
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 6 steps with 3 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
Recommended textbooks for you
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education