， C++ ^_^
ExEuclid /*
* ：myecu.cpp
* ：Extend Euclid Algorithm
* ：ld
* ：25th June,2010
*/
#include "stdafx.h"
#include
#include
#include
#include
#include
using namespace std;
typedef struct polyNode//
{
int coef;
int power;
}polyNode;
void CreatePoly(vector&poly);//
void SortPolyByPower(vector&poly);// ，
vector PolyAdd(vectorp1,vectorp2);//
vector PolySub(vectorp1,vectorp2);//
vector PolyMultiply(vectorp1,vectorp2);//
vector PolyDiv(vector&p1,vectorp2);//
vector Eculid(vector&p1,vector&p2);//
void SortPolyByPower(vector&poly)//OK
{
vector::iterator iter,tmpIter;
iter = poly.begin();
for (; iter != poly.end(); iter++)//
{
tmpIter = iter + 1;
int maxPower = (*iter).power;
for (; tmpIter != poly.end(); tmpIter++)
{
if ((*tmpIter).power > (*iter).power)
{
iter_swap(iter,tmpIter);
}
}
}
}
void CreatePoly(vector&poly)//OK
{
static int itemCount = 0;
cout<Please input the itemCount of the poly:"<>itemCount;
for (int t = 0; t < itemCount; t++)
{
static polyNode tmpItem;
cout<Please input the coef and power:"<>tmpItem.coef>>tmpItem.power;
poly.push_back(tmpItem);
}
SortPolyByPower(poly);
cout< ："<::iterator iter="" style="color:#0000ff;">for ( iter = poly.begin();iter!= poly.end();iter++)
{
cout<X^"<+";
}
cout< PolyAdd(vectorp1,vectorp2)//OK
{
vector tmpPolyAdd;
vector::iterator iter1,iter2;
iter1 = p1.begin();
iter2 = p2.begin();
if (p1.size() == 0)
{
tmpPolyAdd.clear();
tmpPolyAdd = p2;
return tmpPolyAdd;
}
else if(p2.size() == 0)
{
tmpPolyAdd.clear();
tmpPolyAdd = p1;
return tmpPolyAdd;
}
else
{
tmpPolyAdd.clear();
for (; iter1 != p1.end() && iter2 != p2.end();)
{
if ((*iter1).power > (*iter2).power)
{
tmpPolyAdd.push_back(*iter1);
iter1++;
}
else if ((*iter1).power == (*iter2).power)
{
polyNode tmp;
tmp.coef = ((*iter1).coef + (*iter2).coef)%2;
tmp.power = (*iter1).power;
if (tmp.coef != 0)
{
tmpPolyAdd.push_back(tmp);
}
else;
iter1++;
iter2++;
}
else if ((*iter1).power < (*iter2).power)
{
tmpPolyAdd.push_back(*iter2);
iter2++;
}
}
if (iter2 != p2.end())
{
for (;iter2 != p2.end();iter2++)
{
tmpPolyAdd.push_back(*iter2);
}
SortPolyByPower(tmpPolyAdd);
return tmpPolyAdd;
}
else if(iter1 != p1.end())
{
for (;iter1 != p1.end();iter1++)
{
tmpPolyAdd.push_back(*iter1);
}
SortPolyByPower(tmpPolyAdd);
return tmpPolyAdd;
}
else
{
SortPolyByPower(tmpPolyAdd);
return tmpPolyAdd;
}
}
}
vector PolySub(vectorp1,vectorp2)//OK
{
vector tmpPolySub;
vector::iterator iter1,iter2;
iter1 = p1.begin();
iter2 = p2.begin();
for (; iter1 != p1.end() && iter2 != p2.end();)
{
if ((*iter1).power > (*iter2).power)
{
tmpPolySub.push_back(*iter1);
iter1++;
}
else if ((*iter1).power == (*iter2).power)
{
polyNode tmp;
tmp.coef = ((*iter1).coef - (*iter2).coef)%2;
tmp.power = (*iter1).power;
if (tmp.coef != 0)
{
tmpPolySub.push_back(tmp);
}
else;
iter1++;
iter2++;
}
else if ((*iter1).power < (*iter2).power)
{
tmpPolySub.push_back(*iter2);
iter2++;
}
}
if (iter2 == p2.end())
{
for (;iter1 != p1.end();iter1++)
{
tmpPolySub.push_back(*iter1);
}
}
else if(iter1 == p1.end())
{
for (;iter2 != p2.end();iter2++)
{
tmpPolySub.push_back(*iter2);
}
}
SortPolyByPower(tmpPolySub);
return tmpPolySub;
}
vector PolyMultiply( vectorp1, vectorp2)//OK
{
vector tmpPolyMul;
tmpPolyMul.clear();
vector itemPoly;
polyNode tmp;
vector::iterator iter1,iter2;
iter1 = p1.begin();
iter2 = p2.begin();
for (; iter2 != p2.end(); iter2++)
{
for (;iter1 != p1.end(); iter1++)
{
tmp.coef = (*iter1).coef * (*iter2).coef;
tmp.power = (*iter1).power + (*iter2).power;
itemPoly.push_back(tmp);
}
SortPolyByPower(itemPoly);
iter1 = p1.begin();
tmpPolyMul = PolyAdd(tmpPolyMul,itemPoly);
itemPoly.clear();
}
SortPolyByPower(tmpPolyMul);
return tmpPolyMul;
}
vector PolyDiv(vector&p1, vectorp2)//OK
{
polyNode tmpItem;
vector tmpP1 = p1;
vector tmpP2 = p2;
static vector result;
static vector ret;
vector tmpMultiply;
vector tmpResult;
static vector rPoly;
vector::iterator iter1;
vector::iterator iter2;
iter1 = tmpP1.begin();
iter2 = tmpP2.begin();
while ((*iter1).power >= (*iter2).power)
{
for (;iter2!=tmpP2.end();iter2++)
{
tmpItem.coef = abs((*iter1).coef / (*iter2).coef);
tmpItem.power = (*iter1).power - (*iter2).power;
tmpResult.push_back(tmpItem);
result.push_back(tmpItem);
tmpMultiply = PolyMultiply(p2,tmpResult);
vector::iterator tmpIter;
tmpIter = tmpMultiply.begin();
tmpResult.clear();
rPoly= PolySub(tmpP1,tmpMultiply);
p1 = rPoly;
rPoly.clear();
return PolyDiv(p1,p2);
}
}
SortPolyByPower(result);
ret = result;
result.clear();
return ret;
}
vector Eculid(vector&mx,vector&bx)//OK
{
vector a1x;
vector a2x;
vector a3x;
vector a3xcp;
vector b1x;
vector b2x;
vector b3x;
vector t1x;
vector t2x;
vector t3x;
vector qx;
vector gcd;
vector inverse;
vector::iterator iter;
static polyNode tmpItem;
tmpItem.coef = 1;
tmpItem.power = 0;
a1x.push_back(tmpItem);
a3x.clear();
a3x = mx;
b1x.clear();
tmpItem.coef = 1;
tmpItem.power = 0;
b2x.push_back(tmpItem);
b3x = bx;
do
{
iter = b3x.begin();
if (b3x.empty())
{
cout<No inverse!!!"<else if (b3x.size() == 1 && ((*iter).coef == 1 && (*iter).power == 0))
{
inverse = b2x;
return inverse;
}
a3xcp = a3x;
qx = PolyDiv(a3x,b3x);
a3x = a3xcp;
t1x = PolySub(a1x,PolyMultiply(qx,b1x));
t2x = PolySub(a2x,PolyMultiply(qx,b2x));
t3x = PolySub(a3x,PolyMultiply(qx,b3x));
a1x = b1x;
a2x = b2x;
a3x = b3x;
b1x = t1x;
b2x = t2x;
b3x = t3x;
} while (1);
}
int main()
{
vector polynomial1;
vector polynomial2;
vector inverse;
vector ::iterator iter;
vector r;
CreatePoly(polynomial1);
CreatePoly(polynomial2);
inverse = Eculid(polynomial1,polynomial2);
SortPolyByPower(inverse);
iter = inverse.begin();
cout< ："<for (;iter!=inverse.end();iter++)
{
cout<X^"<+"<