辗转相除法求最大公因子及求逆C++编程

答案:1 悬赏:60 手机版

解决时间 2021-03-28 06:55

提问者网友：心牵心
2021-03-27 07:27

辗转相除法求最大公因子及求逆C++编程

最佳答案

五星知识达人网友：夜风逐马
2021-03-27 07:32

试试这个代码：
#include
#include
#include
struct 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("按下列格式输入系数:(例如x^4 + 2x^3 - 7x^1 + 5 输入:1 2 0 -7 5)\n");
printf("等待输入:");
for(i=n;i>=0;i--)
{
scanf("%lf",&ai);
(*c).an[i] = ai;
}
}
void show(struct chain c) //按照多项式的格式显示多项式
{
int i=c.n;
printf("多项式是:");
while(i>=0)
{
if((i!=c.n)&&(c.an[i]>=0))
printf(" + ");
switch(i)
{
case 1:
printf("%.2lfX",c.an[i]);
break;
case 0:
printf("%.2lf",c.an[i]);
break;
default:
printf("%.2lfX^%d",c.an[i],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).an[i] = ch1.an[i] + ch2.an[i]; //相同次数的系数相加
else
(*ch).an[i] = ch1.an[i]; //直接保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).an[i] = ch1.an[i] + ch2.an[i];
else
(*ch).an[i] = ch2.an[i];
}
}
}
void check_change(struct chain *r) //检验多项式r的最高次数并进行相应的修改
{
int i = (*r).n;
while((fabs((*r).an[i])<=1e-5)&&(i>=0)) //依次从高次项向低次项进行系数检验
i--;
(*r).n = i; //注意：如果多项式r为0，这里i=-1
}
bool check_zero(struct chain r) //检验多项式r的最高次数
{
int i;
for(i=0;i<=r.n;i++)
if(fabs(r.an[i])>=1e-6) //如果一旦有一个不为零，返回false
return false;
return true; //全为零的情况下返回true
}
void 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<=q.n)
{
r.n = ch1.n - 1; //r的最高次数为ch1的最高次数减1
q.an[q.n-i] = ch1.an[ch1.n]/ch2.an[ch2.n]; //多项式q的最高次项系数
tmp = q.an[q.n-i];
for(j=r.n;j>=0;j--)
{
if(j>=q.n-i)
r.an[j] = ch1.an[j] - tmp*ch2.an[j-q.n+i]; //高次对应相减
else
r.an[j] = ch1.an[j]; //低次保留
}
if(check_zero(r))
break; //若余式r系数全为零,退出循环
ch1 = r; //ch2没除干净，将r赋给ch1,继续除ch2
i++;
}
printf("---------------------------------------------\n");
printf("q(x):");
show(q); //显示每一步的多项式q
printf("r(x):");
show(r); //显示每一步与q对应的多项式r
printf("---------------------------------------------\n");
check_change(&r); //修改余式r的最高次数，即修改r.n
if(r.n==-1) //r.n==-1时，说明最大公因式已经找到
{
printf("所求最大公因式的");
show(ch2); //输出结果
free(r.an); //回收动态分配内存
}
else
do_div(ch2,r); //辗转相除
}
//(x2+2x+1)(x+1)=x3+3x2+3x+1

int main()
{
struct chain ch1,ch2,ch;
printf("***************建立第一个多项式**************\n\n");
creat_chain(&ch1);
show(ch1);
printf("***************建立第二个多项式**************\n\n");
creat_chain(&ch2);
show(ch2);
printf("***************以上两个多项式求和**************\n\n");
do_add(&ch,ch1,ch2);
show(ch);
printf("***************以上两个多项式求公因式**************\n\n");
do_div(ch1,ch2);
//回收动态分配内存
free(ch1.an);
free(ch2.an);
free(ch.an);
return 0;
}

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！