多项式辗转相除法求最大公因式

#include#include#includestruct chain/定义一个多项式的结构体int n;/该多项式的最高次数double *an;/存放多项式的系数;void creat_chain(struct chain *c)/建立一个多项式int i,n;double ai;printf(请输入该多项式最高次数:);scanf(%d,&n);(*c).n = n;(*c).an = (double *)calloc(n+1,sizeof(double);/给该多项式系数动态分配内存printf(按下列格式输入系数:(例如x4 + 2x3 - 7x1 + 5 输入:1 2 0 -7 5)n);printf(等待输入:);for(i=n;i=0;i-)scanf(%lf,&ai);(*c).ani = ai;void show(struct chain c)/按照多项式的格式显示多项式int i=c.n;printf(多项式是:);while(i=0)if(i!=c.n)&(c.ani=0)printf( + );switch(i)case 1:printf(%.2lfX,c.ani);break;case 0:printf(%.2lf,c.ani);break;default:printf(%.2lfX%d,c.ani,i);break;i-;printf(n);void do_add(struct chain *ch,struct chain ch1,struct chain ch2)/两个多项式求和int i;if(ch1.n=ch2.n)(*ch).n = ch1.n;/求和之后多项式的最高次应是ch1和ch2中较高的次数(*ch).an = (double *)calloc(*ch).n+1,sizeof(double);for(i=0;i=(*ch).n;i+)if(i=ch2.n)(*ch).ani = ch1.ani + ch2.ani;/相同次数的系数相加else(*ch).ani = ch1.ani;/直接保ch1中有而ch2中没有的项的系数else/与上面if相反(*ch).n = ch2.n;(*ch).an = (double *)calloc(*ch).n+1,sizeof(double);for(i=0;i=(*ch).n;i+)if(i=ch1.n)(*ch).ani = ch1.ani + ch2.ani;else(*ch).ani = ch2.ani;void check_change(struct chain *r)/检验多项式r的最高次数并进行相应的修改int i = (*r).n;while(fabs(*r).ani)=0)/依次从高次项向低次项进行系数检验i-;(*r).n = i;/注意：如果多项式r为0，这里i=-1bool check_zero(struct chain r)/检验多项式r的最高次数int i;for(i=0;i=1e-6)/如果一旦有一个不为零，返回falsereturn false;return true;/全为零的情况下返回truevoid do_div(struct chain ch1,struct chain ch2)/辗转相除法,公式:ch1 = q*ch2+r;int i = 0,j;double tmp;struct chain q,r;if(check_zero(ch2)/判断所除的多项式是否为0，若为0，退出;printf(所除的多项式不能为0!n);exit(0);q.n = ch1.n - ch2.n;/q的最高次数为ch1和ch2最高次数相减r.n = ch1.n - 1;r.an = (double *)calloc(r.n+1,sizeof(double);/为系数动态分配内存q.an = (double *)calloc(q.n+1,sizeof(double);while(i=0;j-)if(j=q.n-i)r.anj = ch1.anj - tmp*ch2.anj-q.n+i;/高次对应相减elser.anj = ch1.anj;/低次保留if(check_zero(r)break;/若余式r系数全为零,退出循环ch1 = r;/ch2没除干净，将r赋给ch1,继续除ch2i+;printf(-n);printf(q(x):);show(q);/显示每一步的多项式qprintf(r(x):);show(r);/显示每一步与q对应的多项式rprintf(-n);check_change(&r);/修改余式r的最高次数，即修改r.nif(r.n=-1)/r.n=-1时，说明最大公因式已经找到printf(所求最大公因式的);show(ch2);/输出结果free(r.an);/回收动态分配内存elsedo_div(ch2,r);/辗转相除void main()struct chain ch1,ch2,ch;printf(*建立第一个多项式*nn);creat_chain(&ch1);show(ch1);printf(*建立第二个多项式*nn);creat_chain(&ch2);show(ch2);printf(*以上两个多项式求和*nn);