Dal momento che il problema mi sembrava interessante, ho provato ad implementare qualcosa... ecco il codice:
#include <iostream>
#include <algorithm>
#include <cstdint>
#include <vector>
using namespace std;
int64_t mcd(int64_t a, int64_t b)
{
if(a < 0)
{
a = -a;
}
if(b < 0)
{
b = -b;
}
int64_t r;
while(r = a % b)
{
a = b;
b = r;
}
return b;
}
int64_t mcm(int64_t a, int64_t b)
{
if(a < 0)
{
a = -a;
}
if(b < 0)
{
b = -b;
}
return b / mcd(a, b) * a;
}
class frazione
{
private:
int64_t num;
int64_t den;
void normalizza_frazione()
{
if(!num)
{
den = 1;
}
else
{
if(den < 0)
{
num = -num;
den = -den;
}
int64_t MCD = mcd(num, den);
num /= MCD;
den /= MCD;
}
}
public:
frazione(const int64_t &_num = 0, const int64_t &_den = 1)
{
num = _num;
den = _den;
normalizza_frazione();
}
int64_t get_num() const
{
return num;
}
int64_t get_den() const
{
return den;
}
friend frazione operator -(const frazione &q)
{
return {-q.num, q.den};
}
friend frazione operator +(const frazione &q1, const frazione &q2)
{
frazione q3;
q3.den = mcm(q1.den, q2.den);
q3.num = q3.den / q1.den * q1.num + q3.den / q2.den * q2.num;
q3.normalizza_frazione();
return q3;
}
frazione& operator +=(const frazione &q)
{
return(*this = *this + q);
}
friend frazione operator *(const frazione &q1, const frazione &q2)
{
frazione q3(q1.num, q2.den);
frazione q4(q2.num, q1.den);
q3.num = q3.num * q4.num;
q3.den = q3.den * q4.den;
return q3;
}
frazione& operator *=(const frazione &q)
{
return(*this = *this * q);
}
friend frazione potenza(const frazione &base, const unsigned int esponente)
{
frazione q(1);
for(unsigned int i = 0; i < esponente; ++i)
{
q *= base;
}
return q;
}
friend bool operator ==(const frazione &q1, const frazione &q2)
{
return(q1.num == q2.num && q1.den == q2.den);
}
friend bool operator !=(const frazione &q1, const frazione &q2)
{
return(!(q1 == q2));
}
friend std::ostream& operator <<(std::ostream &out, const frazione &q)
{
out << q.num;
if(q.den != 1)
{
out << "/" << q.den;
}
return out;
}
explicit operator bool() const
{
return num;
}
};
int64_t raccogli_denominatore(vector<frazione> &coef)
{
int64_t MCM = 1;
for(unsigned int i = 0; i < coef.size(); ++i)
{
if(coef[i].get_den() != 1)
{
MCM = mcm(MCM, coef[i].get_den());
}
}
if(MCM != 1)
{
for(unsigned int i = 0; i < coef.size(); ++i)
{
coef[i] *= MCM;
}
}
return MCM;
}
vector<unsigned int> cerca_divisori(int64_t n)
{
vector<unsigned int> v;
if(n < 0)
{
n = -n;
}
for(unsigned int i = 1; i <= n / i; ++i)
{
if(!(n % i))
{
v.push_back(i);
if(i != n / i)
{
v.push_back(n / i);
}
}
}
return v;
}
vector<frazione> definisci_possibili_radici(const vector<unsigned int> &div_coef_0, const vector<unsigned int> &div_coef_max)
{
vector<unsigned int> u;
vector<frazione> v;
for(unsigned int i = 0; i < div_coef_0.size(); ++i)
{
for(unsigned int j = 0; j < div_coef_max.size(); ++j)
{
u.push_back(div_coef_max[1] / div_coef_max[j] * div_coef_0[i]);
}
}
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
for(unsigned int i = 0; i < u.size(); ++i)
{
v.push_back({u[i], div_coef_max[1]});
v.push_back(-v.back());
}
return v;
}
frazione valuta_polinomio(const vector<frazione> &coef, const frazione &x)
{
frazione q;
for(unsigned int i = 0; i < coef.size(); ++i)
{
q += coef[i] * potenza(x, coef.size() - 1 - i);
}
return q;
}
void stampa_polinomio(const vector<frazione> &coef)
{
cout << "(";
unsigned int grado = coef.size() - 1;
for(unsigned int i = 0; i <= grado; ++i)
{
if(coef[i])
{
cout << " ";
if(i && coef[i].get_num() > 0)
{
cout << "+";
}
if(i == grado || coef[i] != 1 && coef[i] != -1)
{
cout << coef[i];
}
if(i < grado)
{
if(coef[i] == -1)
{
cout << "-";
}
cout << "X";
if(grado - i > 1)
{
cout << "^" << grado - i;
}
}
}
}
cout << " )";
}
int main()
{
//INSERIRE I COEFFICIENTI DEL POLINOMIO COMPLETO ORDINATO SECONDO LE POTENZE DECRESCENTI.
//SI POSSONO INSERIRE ANCHE FRAZIONI.
vector<frazione> coef = {4, 0, -3, 5, -6};
//vector<frazione> coef = {2, 5, -5, -5, 3};
//vector<frazione> coef = {{1, 12}, {-3, 4}, {13, 6}, -2};
//vector<frazione> coef = {1, -7, 4, 5, -2};
if(coef.front() && coef.back())
{
stampa_polinomio(coef);
cout << " = ";
int64_t MCM = raccogli_denominatore(coef);
vector<unsigned int> div_coef_0 = cerca_divisori(coef.back().get_num());
vector<unsigned int> div_coef_max = cerca_divisori(coef.front().get_num());
vector<frazione> v = definisci_possibili_radici(div_coef_0, div_coef_max);
if(MCM != 1)
{
cout << frazione(1, MCM) << " ";
stampa_polinomio(coef);
cout << " = ";
cout << frazione(1, MCM) << " ";
}
for(unsigned int i = 0; i != v.size() && coef.size() > 2;)
{
for(i = 0; i < v.size(); ++i)
{
if(!valuta_polinomio(coef, v[i]))
{
coef.pop_back();
for(unsigned int j = 1; j < coef.size(); ++j)
{
coef[j] += coef[j - 1] * v[i];
}
stampa_polinomio({1, -v[i]});
break;
}
}
}
stampa_polinomio(coef);
cout << endl;
}
}
Il programma scompone il polinomio inserito fin quando possibile. L'input, che va inserito nella prima riga del main(), consiste nei coefficienti (che possono essere anche frazioni) di un polinomio completo ordinato secondo le potenze decrescenti.
Di seguito alcuni esempi:
INPUT --> {4, 0, -3, 5, -6}
( 4X^4 -3X^2 +5X -6 ) = ( X -1 )( X +3/2 )( 4X^2 -2X +4 )
Process returned 0 (0x0) execution time : 0.339 s
Press any key to continue.
INPUT --> {{1, 12}, {-3, 4}, {13, 6}, -2}
( 1/12X^3 -3/4X^2 +13/6X -2 ) = 1/12 ( X^3 -9X^2 +26X -24 ) = 1/12 ( X -2 )( X -3 )( X -4)
Process returned 0 (0x0) execution time : 0.030 s
Press any key to continue.
INPUT --> {1, -7, 4, 5, -2} (polinomio irriducibile)
( X^4 -7X^3 +4X^2 +5X -2 ) = ( X^4 -7X^3 +4X^2 +5X -2 )
Process returned 0 (0x0) execution time : 0.018 s
Press any key to continue.
Se trovate qualche bug o qualche errore dal punto di vista dell'impostazione matematica, fatemi sapere.