#include #include #define MAX 100 typedef struct { int numerator, denominator; } rational; typedef struct { int degree; int coefficient[MAX]; } polynomial; typedef struct { int nfactors; int factor[MAX]; } factorlist; int gcd ( int a, int b ) { int r; if ((a == 0) && (b == 0)) return 0; if (a < 0) a = -a; if (b < 0) b = -b; while (b) { r = a % b; a = b; b = r; } return a; } rational reduce ( rational x ) { int d; d = gcd(x.numerator,x.denominator); if (d > 0) { x.numerator /= d; x.denominator /= d; } return x; } rational radd ( rational x, rational y ) { rational z; z.numerator = (x.numerator)*(y.denominator) + (x.denominator)*(y.numerator); z.denominator = (x.denominator)*(y.denominator); return reduce(z); } rational rmul ( rational x, rational y ) { rational z; z.numerator = (x.numerator)*(y.numerator); z.denominator = (x.denominator)*(y.denominator); return reduce(z); } rational evalpoly ( polynomial f, rational x ) { int i; rational sum, xpower, term; if (f.degree < 0) return (rational){0,1}; sum.numerator = f.coefficient[0]; sum.denominator = 1; xpower = (rational){1,1}; for (i=1; i<=f.degree; ++i) { xpower = rmul(xpower,x); term = rmul(xpower,(rational){f.coefficient[i],1}); sum = radd(sum,term); } return reduce(sum); } factorlist getfactors ( int n ) { factorlist L; int d; if (n == 0) { L.nfactors = 0; return L; } if (n < 0) n = -n; L.nfactors = 0; for (d=1; d<=n; ++d) { if (n % d == 0) L.factor[L.nfactors++] = d; } return L; } void findroots ( polynomial f ) { int i,j,d; rational x, fx; factorlist L1, L2; if (f.degree <= 0) return; L1 = getfactors(f.coefficient[0]); L2 = getfactors(f.coefficient[f.degree]); for (i=0; i