基于扩展欧几里得算法的多项式互素.doc

这个程序实现对以个多项式的各种操作，包括：从控制台读入多项式，检查多项式的合法性，多项式的存储与输出显示，多项式的加法，减法，乘法，除法。完成多项式技术后，将其运用到多项式的扩展欧几里得算法中，实现对两个多项式寻找到使u(x)f(x)+v(x)g(x)=1成立的v(x),u(x);

以下是多项式程序。
#include<iostream>
using namespace std;

#define MaxDXS 200

struct DXS{
int n;
double xi[MaxDXS+1];
};

int max(int a,int b)
{
if(a>b) return a;
return b;
}
int check(DXS &a)
{
while(a.n>0 && a.xi[a.n]==0) a.n--;

return 0;
}
int show(DXS a)//find a problem in show;
{
if(a.xi[a.n]==1)
{
if(a.n==0) cout<<1;
}
else if(a.xi[a.n]==-1) cout<<"-";
else cout<<a.xi[a.n];

if(a.n>1) cout<<"X^"<<a.n;
if(a.n==1) cout<<"X";

for(int i=a.n-1; i>=0; i--)
{
if(a.xi[i]>0)
{
if(a.xi[i]!=1) cout<<'+'<<a.xi[i];
else if(i==0) cout<<"+1";
else cout<<'+';

if(i>1) cout<<"X^"<<i;
if(i==1) cout<<"X";
}
else if(a.xi[i]<0)
{
if(a.xi[i]!=-1) cout<<a.xi[i];
else if(i==0) cout<<-1;
else cout<<'-';

if(i>1) cout<<"X^"<<i;
if(i==1) cout<<"X";
}
}
return 0;
}
bool GetDXS(DXS &a)
{
char s[MaxDXS*10];
DXS tmp={NULL};

cin>>s;

char lst='[';
double xi=0; int zhi=0;
int i=0;

int len=strlen(s);
s[len]='+',s[len+1]='\0';

while(s[i]!='\0')
{
if(s[i]>='0' && s[i]<='9')
{
double num=0,dotcnt=1;
bool isdot=false;

while(s[i]>='0' && s[i]<='9' || s[i]=='.' )
{
if(s[i]=='.')
{
if(isdot)
{
cout<<"小数点输入错误!"<<endl;
return false;
}else{
isdot=true;
dotcnt=1;
}
}else
{
if(isdot) dotcnt*=0.1;
num=num*10+(s[i]-'0');
}
num=num*dotcnt;
i++;
}

if(lst=='+' || lst=='[') xi=num; //xi
else if(lst=='-'|| lst=='[') xi=-num;//-xi
else if(lst=='^')//zhi
{
if(isdot)
{
cout<<"多项式的指数必须是正整数!"<<endl;
return false;
}
zhi=int(num);
if(zhi>=100)
{
cout<<"你的多项式输入次数太大了!"<<endl;
return false;
}
}
else
{
cout<<"你的输入有问题!"<<endl;
return false;
}
i--;
}else if(s[i]=='x' || s[i]=='X')
{
if(lst=='+' || lst=='[') xi=1;
else if(lst=='-') xi=-1;
else if(lst>='0' && lst<='9')
{
}
else
{
cout<<"你的输入有误!"<<endl;
return false;
}
}else if(s[i]=='^')
{
if(lst=='x' || lst=='X')
{
}else
{
cout<<"输入出错!"<<endl;
return false;
}
}else if(s[i]=='+' || s[i]=='-')
{
if(lst>='0' && lst<='9' || lst=='[' || lst=='x' || lst=='X')
{
if(lst>='0' && lst<='9')
{
tmp.xi[zhi]+=xi;
}else if(lst=='x' || lst=='X')
{
zhi=1;
tmp.xi[zhi]+=xi;
}

tmp.n=max(tmp.n,zhi);
}
else
{
cout<<"你的输入有问题!"<<endl;
return false;
}
//fresh every thing;
zhi=0;
xi=0;
}else
{
cout<<"你的输入有误!"<<endl;
return false;
}
lst=s[i];
i++;
}

check(tmp);
a=tmp;

return true;
}

DXS PLUS(DXS a,DXS b)
{
DXS tmp={NULL};

tmp.n=max(a.n,b.n);
for(int i=tmp.n; i>=0; i--)
tmp.xi[i]=a.xi[i]+b.xi[i];

check(tmp);

return tmp;
}

DXS SUB(DXS a,DXS b)
{
DXS tmp={NULL};
tmp.n=max(a.n,b.n);
for(int i=tmp.n; i>=0; i--)
tmp.xi[i]=a.xi[i]-b.xi[i];
check(tmp);

return tmp;
}
DXS MUL(DXS a,DXS b)
{
DXS tmp={NULL};
tmp.n=a.n+b.n;
for(int i=a.n; i>=0; i--)
for(int j=b.n; j>=0; j--)
tmp.xi[i+j]+=a.xi[i]*b.xi[j];
check(tmp);

return tmp;
}

DXS DEL(DXS a,DXS b,DXS &rest)//find something wrong!
{
DXS s={NULL},r={NULL};

if(b.n==0 && b.xi[0]==0)
{
cout<<"除数不能为0!运算失败!"<<endl;
return s;
}

r=a;

if(r.n>=b.n) s.n=r.n-b.n;

while(r.n>=b.n)
{
s.xi[r.n-b.n]=r.xi[r.n]/b.xi[b.n];

r.xi[r.n]=0;

for(int i=b.n-1; i>=0; i--)
r.xi[i+r.n-b.n]-=b.xi[i]*s.xi[r.n-b.n];

check(r);

if(r.n==0 && r.xi[0]==0) break;
}

rest=r;

return s;
}

以下是欧几里得算法程序。
#include"DXS.H"
#include<iostream>
using namespace std;

DXS a,b,u,v,d,sr;

void Egcd(int a,int b,int &x,int &y,int &d)
{
if(b==0)
{
d=a;
x=1;
y=0;
}
else
{
int x1,y1;
Egcd(b,a%b,x1,y1,d);
x=y1;
y=x1-y1*(a/b);
}
}

void Egcd_DXS(DXS a,DXS b,DXS &x,DXS &y,DXS &d)
{
if(b.n==0 && b.xi[0]==0)
{
d=a;
x.n=0; x.xi[0]=1;
y.n=0; y.xi[0]=0;
}
else
{
DXS x1,y1,q;

q=DEL(a,b,sr);

Egcd_DXS(b,sr,x1,y1,d);

x=y1;
y=SUB(x1,MUL(y1,q));
}

}
void InitDXS()
{
bool Dget=false;
while(!Dget)
{
cout<<"请输入第一个多项式:"<<endl;
Dget=GetDXS(a);
}

Dget=false;
while(!Dget)
{
cout<<"请输入第二个多项式："<<endl;
Dget=GetDXS(b);
}

if(a.n<b.n) swap(a,b);
}
void check_GCD(DXS &d,DXS &u)
{
int i;
for( i=0; i<d.n; i++)
d.xi[i]*=1/d.xi[d.n];
for( i=0; i<=u.n; i++)
u.xi[i]*=1/d.xi[d.n];
d.xi[d.n]=1;
}
int main()
{
InitDXS();

Egcd_DXS(a,b,u,v,d);

check_GCD(d,u);
check_GCD(d,v);
show(d); cout<<endl;
cout<<"("; show(a); cout<<")*";
cout<<"("; show(u); cout<<") + ";
cout<<"("; show(b); cout<<")*";
cout<<"("; show(v); cout<<") =";
show(d); cout<<endl;
system("pause");
return 0;
}