CS Prgram recursion Doiphantine In this PROGRAM you will b

CS Prgram - recursion - Doiphantine

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.

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 / b is 0), 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 = bq + r
where q is (a / b) (using integer division) and r is the remainder (a % b).
Substituting (bq + r) in for a now:
(bq + r)x + by = c
which is the same as:
b(qx + y) + rx = c
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 uand 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

Input/Output Test Samples

main function:

// C++ code
#include <iostream>
#include <string>
#include <fstream>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <iomanip> // std::setprecision

using namespace std;

int solution(int a, int b, int *x, int *y)
{
if (a == 0)
{
*x = 0;
*y = 1;
return b;
}

int xnew, ynew;
int gcd = solution(b%a, a, &xnew, &ynew);

*x = ynew - (b/a) * xnew;
*y = xnew;

return gcd;
}

// the GCD of two numbers
int gcd(int a, int b)
{
return (a%b == 0)? abs(b) : gcd(b,a%b);
}

bool diophantine(int a, int b, int c, int &x, int &y)
{
if (c%gcd(a,b) == 0)
{
if(a%b == 0)
{
x = 0;
y = c/b;
}
else
{

a = a/gcd(a,b);
b = b/gcd(a,b);
c = c/gcd(a,b);

solution(b%a,a,&x,&y);
x = x*c;
y = y*c;
}

return true;
}
else
{
return false;
}
}

int main()
{

int a, b, c, x, y;

cout << \"Enter a b c: \";
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;
}

/*
output:

Enter a b c: 28 7 490
Result: 0 70

Enter a b c: 11 11 2010
Result: No solution!