论文部分内容阅读
摘 要：设计出计算一元有理系数多项式有理根的算法及程序，并给出计算实例.
关键词：有理系数多项式；有理根；算法；程序.
多项式问题中，有理系数多项式有理根的计算非常重要，然而，尽管说已有完整的计算方法，但是人工操作却并非易事；尽管说已有大型的数学软件，但是它们的表现却并非如意.例如多项式：
有2重有理根-19162/429459 ，但用Matlab计算的结果却是 -233/5222。因此，本文研究专门的计算有理系数多项式有理根的算法及程序.
1. 理论基础
基本定义及结论请参阅文献[1]，下面仅列出主要的。
本原多项式[1] 若整系数多项式 f（x）的系数互素，则称 f（x） 为本原多项式.
整系数多项式有理根的性质[1] 设 f（x）=anxn+an-1xn-1+...+a1x+a0是整系数多项式.如果有理数u/v 是 f（x） 的一个根，其中 u和v 是互素的整数，那么：
（1）、整除 f（x）最高次项系数a0 ，而u 整除f（x） 的常数项an ；
（2）、 f（x）=（x-u/v）/q（x），这里 q（x）是一个整系数多项式.
并且，若有理数 u/v （ u，v∈z且 （u，v）=1）是 f（x）=anxn+an-1xn-1+...+a1x+a0的有理根，那么f（1）/（v-u） 和 f（-1）/（v+u）全为整数.
综合除法[1] 设f（x）=anxn+an-1xn-1+...+a1x+a0 是整系数多项式， c是整数，如果
f（x）=（x-c）（bn-1xn-1+bn-2xn-2+...+b1x+b0）+r
那么 bn-1=an， b-=ai+1+cbi+1（0≤i≤n-1）， r=a0+cb0.
2. 算法设计
根据整系数多项式有理根的性质，设计有理系数多项式 f（x）有理根算法如下。
2.1 主函数
⑴、输入 f（x）系数。输入系数需要区分整数与分数，为此用两个数组分别存储分子与分母，并初始化分母数组值为1，这样在输入整数时即可不顾分母。
⑵、调用"多项式输出子函数"，输出f（x） 的多项式形式。
⑶、调用"化本原子函数"，变f（x） 为本原多项式g（x）=a0xn+...+an-1x+an 。
⑷、调用"求特殊根子函数"，确定0、 €？是否为g（x） 的根。
⑸、调用"求普通根子函数"，确定 g（x）非0非€？ 的有理根。
2.2子函数
①、多项式输出子函数：需要根据各项系数及次数设计。
②、化本原式子函数：调用"求最小公倍数子函数"求得f（x） 系数之公分母 ，调用"求最大公因数子函数"求得 f（x）系数分子的最大公约数 ，则 g（x） = （l/g）/f（x）即是本原多项式。
③、求特殊根子函数：当 an=an-t=...=an-k=0而an+k-t≠0（k≥0） 时，0是 f（x）的 k+1重根；调用"综合除法子函数"计算且记下g（€？） 的值，并当 1或 -1是根时确定其重数且输出结果。
④、求普通根子函数：此函数的功能是求出g（x） 最高项系数H 、常数项T 的因子并构成 g（x）的可能的有理根 €%Z且判定 €%Z是否为 g（x）的根。为此设│a0│=H 、 │an│=T，首先 k从2循环到 ，当 k/T时，若 [T/K]=k，则 k是 T的因子，否则k 与T/k 都是 T的因子，用数组 U存储T 所有的正因子u 。其次k 从2循环到 ，同样方法确定H 的正因子v ，并且每求出一个v ，将 v与 U中的每个數 u组成分数 u/v且判断 u/v 是否为 g（x） 的根，为此需调用"判根子函数"。
⑤、综合除法子函数：此函数的功能是判定有理数 m/d是否为 g（x）的根，若是则输出结果。首先综合除法容易实现。其次用 m/d除 g（x） ，若余数为0，则设 g（x）=（x-m/d）/q（x） ，再用 m/d除 q（x），一直下去，假设 t+1次后的余数不为零，那么 m/d即是 f（x）的t 重根，输出此结果。
⑥、判根子函数：此函数的功能是将v 与U 中的每个数u 组成 u/v且判定其是否为 g（x）的根。为此需做：遍历 U中元素 u，构作u/v ，并且每构作一个就调用"排除非有理根子函数"判断其是否为可能的有理根，若是就调用"综合除法子函数"对其进行判定处理。
⑦、排除非有理根子函数：对于有理数u/v ，如果g（1）/（v-u） 与g（-1）/（v+u） 不全为整数，则u/v 不是 g（x）的有理根；否则 u/v即可能是f（x） 的有理根。
最大公因数、最小公倍数子函数等算法容易确定，从略。
3. 参考程序
根据算法，我们用C语言设计了参考程序，代码如下：
#include
#include
#include
#define UL 2000 /* 存储常数项正因子的数组U的长度*/
static int z； double x[2][50]，X[2][50]； static int Z； int y[50]；
static double F1，F2，a0，an； /*F1为f（1），F2为f（-1），a0为最高项系数，an为常数项*/
/* 判断两数相乘是否溢出子函数 */
int MUL（double a，double b） { if（a>0 && b>0 && a-pow（10，15）/b>=pow（10，-6）） return 1； /* 判斷有效数位是否超过15位*/
else if（a>0 && b<0 && a+pow（10，15）/b>=-pow（10，-6）） return 1；
else if（a<0 && b>0 && pow（10，-6）<=-pow（10，15）/b-a） return 1；
else if（a<0 && b<0 && pow（10，-6）<=pow（10，15）/b-a） return 1；
else return 0；}
/* 求最大公因数子函数 */
double GCD（double x，double y）
{ double r=1； for（；r；r=fmod（x，y），x=y，y=r）； return fabs（x）； }
/* 求最小公倍数子函数 */
double LCM（double* a，int n）
{ double* A=NULL；
for（A=a；A { if（MUL（*A/GCD（*A，*（A+1）），*（A+1）））
{ printf（"＼n＼n＼t数据溢出，未得到结果！＼n＼n"）； exit（1）； }
*（A+1）= *A/GCD（*A，*（A+1）） * *（A+1）；}
return *A； }
/* 多项式输出子函数 */
void FUN（double* am，double* ad，int n）
{ int p=0； printf（"＼n＼tf（x） = "）；
for（p=0；p<=n；p++）
{ double g=0.0； g=GCD（*（am+p），*（ad+p））；
if（g） { *（am+p）/=g； *（ad+p）/=g； }
if（*（ad+p） < 0.0） { *（am+p） *= -1； *（ad+p） *= -1； }}
for（p=0；p<=n；p++）
{ if（！ *（am+p） ） continue；
else if（*（am+p）>0.0 && p） printf（" + "）；
else if（*（am+p）>0.0 && ！p） printf（""）；
else printf（" - "）；
if（*（ad+p）==1.0）
{ if（！（n-p）） printf（"%.0lf"，fabs（*（am+p）））；
else if（n-p==1 && fabs（*（am+p））！=1.0） printf（"%.0lfx"，fabs（*（am+p）））；
else if（n-p==1 && fabs（*（am+p））==1.0） printf（"x"）；
else if（n-p>1 && fabs（*（am+p））==1.0） printf（"x^%d"，n-p）；
else if（n-p>1 && fabs（*（am+p））>1.0） printf（"%.0lfx^%d"，fabs（*（am+p）），n-p）；}
else
{ if（！（n-p）） printf（"（%.0lf/%.0lf）"，fabs（*（am+p）），*（ad+p））；
else if（n-p==1） printf（"（%.0lf/%.0lf）x"，fabs（*（am+p）），*（ad+p））；
else if（n-p>1） printf（"（%.0lf/%.0lf）x^%d"，fabs（*（am+p）），*（ad+p），n-p）；}}
printf（"＼n＼n的有理根有："）； }
/* 化本原子函数 */
double* INT（double* m，double* d，int n）
{ int p=0； double l=0.0，x=*m；
double *A=（double*）malloc（sizeof（double）*（n+1））；
double *pd=（double*）malloc（sizeof（double）*（n+1））；
for（p=0；p<=n；p++） *（pd+p）=*（d+p）；
l=LCM（pd，n+1）； /*l为所有系数分母的最小公倍数 */
free（pd）； pd=NULL；
for（p=0；p for（p=0；p<=n；p++）
{
if（MUL（（*（m+p））/x，（l / *（d+p））））
{ printf（"＼n＼n＼t数据溢出，未得到结果！＼n＼n"）； exit（1）；}
*（A+p） = （*（m+p））/x * （l / *（d+p））； /* 将相应的系数转化为整系数 */
}
return A；
}
/* 排除非有理根子函数 */
int TR（double f1，double f2，double m，double d） { return ！fmod（f1/（d-m），1.0） && ！fmod（f2/（d+m），1.0）； }
/* 综合除法子函数 */
/* 形参说明：*mu记录有理根m/d的重数，数组a存储多项式的系数 */
void DIV（double* a，int* n，int* mu，double m，double d，double* A1，double* A2）
{ int i=0，j=0，t=0； *A1=*a；
for（i=1；i<=*n；i++）
{ if （fmod（*（A1+i-1），d）） break；
*（A1+i）= *（a+i） + （*（A1+i-1）） / d * m；
if（fabs（fabs（*（A1+i））-pow（10，15））<=pow（10，-6））
{ if（！*mu） { x[0][z]=m； x[1][z]=d； y[z++]=*mu； } /* m/d是根，但无法确定重数 */
else { X[0][Z]=m； X[1][Z++]=d； } /* 无法确定m/d是否是根 */
return；}
*（A2+i）=*（A1+i）； if（！ *（A1+（*n））） j=1；}
if（j==1）
{ double g=1，x=*a，y=0；
*n=（*n）-1； *mu=（*mu）+1；
for（i=1；i<=*n；i++） *（a+i）=*（A2+i）；
for（i=0；i<*n；i++） { if（*（a+i+1）） { y=*（a+i+1）； g=GCD（x，y）； x=g； } }
for（i=0；i<=*n；i++） *（a+i）/=g；}
else if（*mu）
{ if（d！=1） printf（"＼n＼t＼t %.0lf/%.0lf＼t是f（x）的 %d 重有理根"，m，d，*mu）；
else printf（"＼n＼t＼t %.0lf＼t是f（x）的 %d 重有理根"，m，*mu）；}
}
/* 求特殊有理根子函数 */
/* 形参说明：检验0，1，-1是否为根。数组a存储多项式各项系数；数组sr[3]记录根的重数 */
int SR（double* a，int n，int *sr，double* A1，double* A2）
{ int p=0，t=0；
while（！ *（a+n） ） { sr[0]++； n--； }
a0=a[0]； an=a[n]；
for（p=0；p<=n；p++） { F1+=a[p]； F2+=a[p]*pow（-1，n-p）； }
while（！F1）
{ t=sr[1]； DIV（a，&n，&sr[1]，1，1，A1，A2）；
if（t==sr[1]） break； /* 重数不再改变，退出while循环 */}
while（！F2）
{ t=sr[2]； DIV（a，&n，&sr[2]，-1，1，A1，A2）； if（t==sr[2]） break； }
if（sr[0]） printf（"＼n＼t＼t 0＼t是f（x）的 %d 重有理根"，sr[0]）；
return n；}
/* 判根子函数 */
/* 形参说明：v为最高次项系数的正因子；数组U存储常数项系数的因子；c为因子个数 */
int ROOTS（double v，double* U，int c，double* a，int* n，int* or，double* A1，double* A2）
{ int M=0，p=0，X=0，P=0，u=0，S=0；
for（P=0；P<=*n；P++） *（or+P）=0；
for（u=0；u { if（U[u]！=v）
{ double g=GCD（U[u]，v）；
if（TR（F1，F2，U[u]/g，v/g））
{ X=*n； do { M=*n； DIV（a，n，or+p，U[u]/g，v/g，A1，A2）； } while（*n if（*n }
if（TR（F1，F2，-U[u]/g，v/g））
{ X=*n； do{ M=*n； DIV（a，n，or+p，-U[u]/g，v/g，A1，A2）； } while（*n if（*n }
}
}
for（P=0；P return S； }
/* 求普通有理根子函数 */
/* 形参说明：数组a存储本原多项式的系数；n为次数；数组or记录有理根的重数*/
int OR（double *a，int n，int* or，double* A1，double* A2）
{ int c=2，S=0；
double k=0.0，H=fabs（a0），SH=sqrt（fabs（a0）），T=fabs（an），ST=sqrt（fabs（an）），U[UL]； if（T==1.0） { U[0]=1.0； c=1； }
else
{ U[0]=1； U[1]=T；
for（k=2；k<=ST；k++）
if（！fmod（T，k）） if（T/k==k） U[c++]=k； else { U[c]=k； U[c+1]=T/k； c+=2； }}
if（H==1） S+=ROOTS（1，U，c，a，&n，or，A1，A2）；
else
{ S+=ROOTS（1，U，c，a，&n，or，A1，A2）； S+=ROOTS（H，U，c，a，&n，or，A1，A2）；
for（k=2；k<=SH；k++）
if（！fmod（H，k））
if（H/k==k） S+=ROOTS（k，U，c，a，&n，or，A1，A2）；
else { S+=ROOTS（k，U，c，a，&n，or，A1，A2）； S+=ROOTS（H/k，U，c，a，&n，or，A1，A2）； }
}
return S； /* 返回所有普通有理根的重数和 */}
int main（）
{ int p=0，n=0，sr[3]={0}，* or=NULL，S=0，S1=0，t1=0，t2=0；
double* m=NULL，* d=NULL，* a=NULL，* A1=NULL，* A2=NULL；
printf（"＼n＼t程序功能：求一元有理系数多项式的有理根.＼n"）；
printf（"＼t请输入有理系数多项式f（x）的次数： n = "）； scanf（"%d"，&n）；
m=（double*）malloc（sizeof（double）*（n+1））； /* 各项系数的分子 */
d=（double*）malloc（sizeof（double）*（n+1））； /* 各项系数的分母 */
printf（"＼t请输入f（x）各项系数（分数请以 a/b 格式输入），每个系数输完后请按回车键.＼n＼n"）；
for（p=0；p<=n；p++）
{ *（d+p）=1；
printf（"＼t＼t%2d 次项系数＼t"，n-p）； scanf（"＼t%lf/%lf"，m+p，d+p）；
t1=MUL（*（m+p），1）； /* 判断系数的分子是否超过有效数位15 */
t2=MUL（*（d+p），1）； /* 判断系数的分母是否超过有效数位15 */
if（t1+t2）
{printf（"＼n＼n＼t数据溢出，未得到结果！＼n＼n"）； exit（1）； } }
FUN（m，d，n）； a=INT（m，d，n）； /* 数组a存储本原多项式的各项系数 */
free（m）； m=NULL； free（d）； d=NULL；
A1=（double*）malloc（sizeof（double）*（n+1））； A2=（double*）malloc（sizeof（double）*（n+1））；
n=SR（a，n，sr，A1，A2）； /* n為除去根0，1，-1后多项式的次数 */
or=（int*）malloc（sizeof（int）*（n+1））；
S=OR（a，n，or，A1，A2）； /* S=0，说明原多项式没有普通有理根 */
free（a）； a=NULL； free（A1）； A1=NULL； free（A2）； A2=NULL；
for（p=0；p<3；p++） S1+=sr[p]； /* S1=0时，说明0，1，-1不是有理根 */
free（or）； or=NULL； printf（"＼n＼t"）； t1=t2=0；
for（p=0；p {
if（y[p] && x[1][p]！=1） { t1++； printf（"%lf/%lf "，x[0][p]，x[1][p]）； }
else if（y[p] && x[1][p]==1） { t1++； printf（"%lf "，x[0][p]）； }
if（p==z-1 && t1） /*t1！=0，存在不确定重数的有理 */
printf（"＼t是f（x）的有理根，但由于数据溢出，无法确定重数＼n＼n }
for（p=0；p { if（X[1][p]！=1） { t2++； printf（"%lf/%lf "，X[0][p]，X[1][p]）； }
else if（X[1][p]==1） { t2++； printf（"%lf "，X[0][p]）； }
if（p==Z-1 && t2） /* t2！=0，存在无法确定是否是根的有理数 */
printf（"＼t由于数据溢出，无法确定其是否是f（x）的有理根＼n＼n"）； }
if（！（S+S1+z+Z）） printf（"＼t＼t不存在有理根"）； /* S1+S+z+Z=0，说明多项式没有有理根 */
printf（"＼n＼n"）； return 0；}
4. 计算示例 下面给出一个计算例子，见图1：
5. 结束语
本文章设计了一元有理系数多项式有理根的算法及程序，该程序较Matlab准确、较Mathematicafb方便实用。算法的复杂度取决于本原多项式 的最高项系数及常数项的大小，但由于取其绝对值的算术根为循环终值，故极大程度地节约了计算时间。不足之处是因为未做大整数运算设计，所以计算中若整数超过15位时会发生数据溢出，有待于继续研究。
图1 程序计算示例
参考文献：
[1] 张禾瑞，郝鈵新.高等代数[M].5版.北京：高等教育出版社，2007：71-76
作者简介： 廖俊义（1991-）， 男， 广东省汕头市人， 韩山师范学院数学与统计学系2010级学生.
通讯作者：王积社（1954 -）， 男， 山西省晋城人， 副教授.主要研究： 数论、数学机械化、数学教育.wangfeng.yz@163.com.
关键词：有理系数多项式；有理根；算法；程序.
多项式问题中，有理系数多项式有理根的计算非常重要，然而，尽管说已有完整的计算方法，但是人工操作却并非易事；尽管说已有大型的数学软件，但是它们的表现却并非如意.例如多项式：
有2重有理根-19162/429459 ，但用Matlab计算的结果却是 -233/5222。因此，本文研究专门的计算有理系数多项式有理根的算法及程序.
1. 理论基础
基本定义及结论请参阅文献[1]，下面仅列出主要的。
本原多项式[1] 若整系数多项式 f（x）的系数互素，则称 f（x） 为本原多项式.
整系数多项式有理根的性质[1] 设 f（x）=anxn+an-1xn-1+...+a1x+a0是整系数多项式.如果有理数u/v 是 f（x） 的一个根，其中 u和v 是互素的整数，那么：
（1）、整除 f（x）最高次项系数a0 ，而u 整除f（x） 的常数项an ；
（2）、 f（x）=（x-u/v）/q（x），这里 q（x）是一个整系数多项式.
并且，若有理数 u/v （ u，v∈z且 （u，v）=1）是 f（x）=anxn+an-1xn-1+...+a1x+a0的有理根，那么f（1）/（v-u） 和 f（-1）/（v+u）全为整数.
综合除法[1] 设f（x）=anxn+an-1xn-1+...+a1x+a0 是整系数多项式， c是整数，如果
f（x）=（x-c）（bn-1xn-1+bn-2xn-2+...+b1x+b0）+r
那么 bn-1=an， b-=ai+1+cbi+1（0≤i≤n-1）， r=a0+cb0.
2. 算法设计
根据整系数多项式有理根的性质，设计有理系数多项式 f（x）有理根算法如下。
2.1 主函数
⑴、输入 f（x）系数。输入系数需要区分整数与分数，为此用两个数组分别存储分子与分母，并初始化分母数组值为1，这样在输入整数时即可不顾分母。
⑵、调用"多项式输出子函数"，输出f（x） 的多项式形式。
⑶、调用"化本原子函数"，变f（x） 为本原多项式g（x）=a0xn+...+an-1x+an 。
⑷、调用"求特殊根子函数"，确定0、 €？是否为g（x） 的根。
⑸、调用"求普通根子函数"，确定 g（x）非0非€？ 的有理根。
2.2子函数
①、多项式输出子函数：需要根据各项系数及次数设计。
②、化本原式子函数：调用"求最小公倍数子函数"求得f（x） 系数之公分母 ，调用"求最大公因数子函数"求得 f（x）系数分子的最大公约数 ，则 g（x） = （l/g）/f（x）即是本原多项式。
③、求特殊根子函数：当 an=an-t=...=an-k=0而an+k-t≠0（k≥0） 时，0是 f（x）的 k+1重根；调用"综合除法子函数"计算且记下g（€？） 的值，并当 1或 -1是根时确定其重数且输出结果。
④、求普通根子函数：此函数的功能是求出g（x） 最高项系数H 、常数项T 的因子并构成 g（x）的可能的有理根 €%Z且判定 €%Z是否为 g（x）的根。为此设│a0│=H 、 │an│=T，首先 k从2循环到 ，当 k/T时，若 [T/K]=k，则 k是 T的因子，否则k 与T/k 都是 T的因子，用数组 U存储T 所有的正因子u 。其次k 从2循环到 ，同样方法确定H 的正因子v ，并且每求出一个v ，将 v与 U中的每个數 u组成分数 u/v且判断 u/v 是否为 g（x） 的根，为此需调用"判根子函数"。
⑤、综合除法子函数：此函数的功能是判定有理数 m/d是否为 g（x）的根，若是则输出结果。首先综合除法容易实现。其次用 m/d除 g（x） ，若余数为0，则设 g（x）=（x-m/d）/q（x） ，再用 m/d除 q（x），一直下去，假设 t+1次后的余数不为零，那么 m/d即是 f（x）的t 重根，输出此结果。
⑥、判根子函数：此函数的功能是将v 与U 中的每个数u 组成 u/v且判定其是否为 g（x）的根。为此需做：遍历 U中元素 u，构作u/v ，并且每构作一个就调用"排除非有理根子函数"判断其是否为可能的有理根，若是就调用"综合除法子函数"对其进行判定处理。
⑦、排除非有理根子函数：对于有理数u/v ，如果g（1）/（v-u） 与g（-1）/（v+u） 不全为整数，则u/v 不是 g（x）的有理根；否则 u/v即可能是f（x） 的有理根。
最大公因数、最小公倍数子函数等算法容易确定，从略。
3. 参考程序
根据算法，我们用C语言设计了参考程序，代码如下：
#include
#include
#include
#define UL 2000 /* 存储常数项正因子的数组U的长度*/
static int z； double x[2][50]，X[2][50]； static int Z； int y[50]；
static double F1，F2，a0，an； /*F1为f（1），F2为f（-1），a0为最高项系数，an为常数项*/
/* 判断两数相乘是否溢出子函数 */
int MUL（double a，double b） { if（a>0 && b>0 && a-pow（10，15）/b>=pow（10，-6）） return 1； /* 判斷有效数位是否超过15位*/
else if（a>0 && b<0 && a+pow（10，15）/b>=-pow（10，-6）） return 1；
else if（a<0 && b>0 && pow（10，-6）<=-pow（10，15）/b-a） return 1；
else if（a<0 && b<0 && pow（10，-6）<=pow（10，15）/b-a） return 1；
else return 0；}
/* 求最大公因数子函数 */
double GCD（double x，double y）
{ double r=1； for（；r；r=fmod（x，y），x=y，y=r）； return fabs（x）； }
/* 求最小公倍数子函数 */
double LCM（double* a，int n）
{ double* A=NULL；
for（A=a；A
{ printf（"＼n＼n＼t数据溢出，未得到结果！＼n＼n"）； exit（1）； }
*（A+1）= *A/GCD（*A，*（A+1）） * *（A+1）；}
return *A； }
/* 多项式输出子函数 */
void FUN（double* am，double* ad，int n）
{ int p=0； printf（"＼n＼tf（x） = "）；
for（p=0；p<=n；p++）
{ double g=0.0； g=GCD（*（am+p），*（ad+p））；
if（g） { *（am+p）/=g； *（ad+p）/=g； }
if（*（ad+p） < 0.0） { *（am+p） *= -1； *（ad+p） *= -1； }}
for（p=0；p<=n；p++）
{ if（！ *（am+p） ） continue；
else if（*（am+p）>0.0 && p） printf（" + "）；
else if（*（am+p）>0.0 && ！p） printf（""）；
else printf（" - "）；
if（*（ad+p）==1.0）
{ if（！（n-p）） printf（"%.0lf"，fabs（*（am+p）））；
else if（n-p==1 && fabs（*（am+p））！=1.0） printf（"%.0lfx"，fabs（*（am+p）））；
else if（n-p==1 && fabs（*（am+p））==1.0） printf（"x"）；
else if（n-p>1 && fabs（*（am+p））==1.0） printf（"x^%d"，n-p）；
else if（n-p>1 && fabs（*（am+p））>1.0） printf（"%.0lfx^%d"，fabs（*（am+p）），n-p）；}
else
{ if（！（n-p）） printf（"（%.0lf/%.0lf）"，fabs（*（am+p）），*（ad+p））；
else if（n-p==1） printf（"（%.0lf/%.0lf）x"，fabs（*（am+p）），*（ad+p））；
else if（n-p>1） printf（"（%.0lf/%.0lf）x^%d"，fabs（*（am+p）），*（ad+p），n-p）；}}
printf（"＼n＼n的有理根有："）； }
/* 化本原子函数 */
double* INT（double* m，double* d，int n）
{ int p=0； double l=0.0，x=*m；
double *A=（double*）malloc（sizeof（double）*（n+1））；
double *pd=（double*）malloc（sizeof（double）*（n+1））；
for（p=0；p<=n；p++） *（pd+p）=*（d+p）；
l=LCM（pd，n+1）； /*l为所有系数分母的最小公倍数 */
free（pd）； pd=NULL；
for（p=0；p
{
if（MUL（（*（m+p））/x，（l / *（d+p））））
{ printf（"＼n＼n＼t数据溢出，未得到结果！＼n＼n"）； exit（1）；}
*（A+p） = （*（m+p））/x * （l / *（d+p））； /* 将相应的系数转化为整系数 */
}
return A；
}
/* 排除非有理根子函数 */
int TR（double f1，double f2，double m，double d） { return ！fmod（f1/（d-m），1.0） && ！fmod（f2/（d+m），1.0）； }
/* 综合除法子函数 */
/* 形参说明：*mu记录有理根m/d的重数，数组a存储多项式的系数 */
void DIV（double* a，int* n，int* mu，double m，double d，double* A1，double* A2）
{ int i=0，j=0，t=0； *A1=*a；
for（i=1；i<=*n；i++）
{ if （fmod（*（A1+i-1），d）） break；
*（A1+i）= *（a+i） + （*（A1+i-1）） / d * m；
if（fabs（fabs（*（A1+i））-pow（10，15））<=pow（10，-6））
{ if（！*mu） { x[0][z]=m； x[1][z]=d； y[z++]=*mu； } /* m/d是根，但无法确定重数 */
else { X[0][Z]=m； X[1][Z++]=d； } /* 无法确定m/d是否是根 */
return；}
*（A2+i）=*（A1+i）； if（！ *（A1+（*n））） j=1；}
if（j==1）
{ double g=1，x=*a，y=0；
*n=（*n）-1； *mu=（*mu）+1；
for（i=1；i<=*n；i++） *（a+i）=*（A2+i）；
for（i=0；i<*n；i++） { if（*（a+i+1）） { y=*（a+i+1）； g=GCD（x，y）； x=g； } }
for（i=0；i<=*n；i++） *（a+i）/=g；}
else if（*mu）
{ if（d！=1） printf（"＼n＼t＼t %.0lf/%.0lf＼t是f（x）的 %d 重有理根"，m，d，*mu）；
else printf（"＼n＼t＼t %.0lf＼t是f（x）的 %d 重有理根"，m，*mu）；}
}
/* 求特殊有理根子函数 */
/* 形参说明：检验0，1，-1是否为根。数组a存储多项式各项系数；数组sr[3]记录根的重数 */
int SR（double* a，int n，int *sr，double* A1，double* A2）
{ int p=0，t=0；
while（！ *（a+n） ） { sr[0]++； n--； }
a0=a[0]； an=a[n]；
for（p=0；p<=n；p++） { F1+=a[p]； F2+=a[p]*pow（-1，n-p）； }
while（！F1）
{ t=sr[1]； DIV（a，&n，&sr[1]，1，1，A1，A2）；
if（t==sr[1]） break； /* 重数不再改变，退出while循环 */}
while（！F2）
{ t=sr[2]； DIV（a，&n，&sr[2]，-1，1，A1，A2）； if（t==sr[2]） break； }
if（sr[0]） printf（"＼n＼t＼t 0＼t是f（x）的 %d 重有理根"，sr[0]）；
return n；}
/* 判根子函数 */
/* 形参说明：v为最高次项系数的正因子；数组U存储常数项系数的因子；c为因子个数 */
int ROOTS（double v，double* U，int c，double* a，int* n，int* or，double* A1，double* A2）
{ int M=0，p=0，X=0，P=0，u=0，S=0；
for（P=0；P<=*n；P++） *（or+P）=0；
for（u=0；u
{ double g=GCD（U[u]，v）；
if（TR（F1，F2，U[u]/g，v/g））
{ X=*n； do { M=*n； DIV（a，n，or+p，U[u]/g，v/g，A1，A2）； } while（*n
if（TR（F1，F2，-U[u]/g，v/g））
{ X=*n； do{ M=*n； DIV（a，n，or+p，-U[u]/g，v/g，A1，A2）； } while（*n
}
}
for（P=0；P
/* 求普通有理根子函数 */
/* 形参说明：数组a存储本原多项式的系数；n为次数；数组or记录有理根的重数*/
int OR（double *a，int n，int* or，double* A1，double* A2）
{ int c=2，S=0；
double k=0.0，H=fabs（a0），SH=sqrt（fabs（a0）），T=fabs（an），ST=sqrt（fabs（an）），U[UL]； if（T==1.0） { U[0]=1.0； c=1； }
else
{ U[0]=1； U[1]=T；
for（k=2；k<=ST；k++）
if（！fmod（T，k）） if（T/k==k） U[c++]=k； else { U[c]=k； U[c+1]=T/k； c+=2； }}
if（H==1） S+=ROOTS（1，U，c，a，&n，or，A1，A2）；
else
{ S+=ROOTS（1，U，c，a，&n，or，A1，A2）； S+=ROOTS（H，U，c，a，&n，or，A1，A2）；
for（k=2；k<=SH；k++）
if（！fmod（H，k））
if（H/k==k） S+=ROOTS（k，U，c，a，&n，or，A1，A2）；
else { S+=ROOTS（k，U，c，a，&n，or，A1，A2）； S+=ROOTS（H/k，U，c，a，&n，or，A1，A2）； }
}
return S； /* 返回所有普通有理根的重数和 */}
int main（）
{ int p=0，n=0，sr[3]={0}，* or=NULL，S=0，S1=0，t1=0，t2=0；
double* m=NULL，* d=NULL，* a=NULL，* A1=NULL，* A2=NULL；
printf（"＼n＼t程序功能：求一元有理系数多项式的有理根.＼n"）；
printf（"＼t请输入有理系数多项式f（x）的次数： n = "）； scanf（"%d"，&n）；
m=（double*）malloc（sizeof（double）*（n+1））； /* 各项系数的分子 */
d=（double*）malloc（sizeof（double）*（n+1））； /* 各项系数的分母 */
printf（"＼t请输入f（x）各项系数（分数请以 a/b 格式输入），每个系数输完后请按回车键.＼n＼n"）；
for（p=0；p<=n；p++）
{ *（d+p）=1；
printf（"＼t＼t%2d 次项系数＼t"，n-p）； scanf（"＼t%lf/%lf"，m+p，d+p）；
t1=MUL（*（m+p），1）； /* 判断系数的分子是否超过有效数位15 */
t2=MUL（*（d+p），1）； /* 判断系数的分母是否超过有效数位15 */
if（t1+t2）
{printf（"＼n＼n＼t数据溢出，未得到结果！＼n＼n"）； exit（1）； } }
FUN（m，d，n）； a=INT（m，d，n）； /* 数组a存储本原多项式的各项系数 */
free（m）； m=NULL； free（d）； d=NULL；
A1=（double*）malloc（sizeof（double）*（n+1））； A2=（double*）malloc（sizeof（double）*（n+1））；
n=SR（a，n，sr，A1，A2）； /* n為除去根0，1，-1后多项式的次数 */
or=（int*）malloc（sizeof（int）*（n+1））；
S=OR（a，n，or，A1，A2）； /* S=0，说明原多项式没有普通有理根 */
free（a）； a=NULL； free（A1）； A1=NULL； free（A2）； A2=NULL；
for（p=0；p<3；p++） S1+=sr[p]； /* S1=0时，说明0，1，-1不是有理根 */
free（or）； or=NULL； printf（"＼n＼t"）； t1=t2=0；
for（p=0；p
if（y[p] && x[1][p]！=1） { t1++； printf（"%lf/%lf "，x[0][p]，x[1][p]）； }
else if（y[p] && x[1][p]==1） { t1++； printf（"%lf "，x[0][p]）； }
if（p==z-1 && t1） /*t1！=0，存在不确定重数的有理 */
printf（"＼t是f（x）的有理根，但由于数据溢出，无法确定重数＼n＼n }
for（p=0；p
else if（X[1][p]==1） { t2++； printf（"%lf "，X[0][p]）； }
if（p==Z-1 && t2） /* t2！=0，存在无法确定是否是根的有理数 */
printf（"＼t由于数据溢出，无法确定其是否是f（x）的有理根＼n＼n"）； }
if（！（S+S1+z+Z）） printf（"＼t＼t不存在有理根"）； /* S1+S+z+Z=0，说明多项式没有有理根 */
printf（"＼n＼n"）； return 0；}
4. 计算示例 下面给出一个计算例子，见图1：
5. 结束语
本文章设计了一元有理系数多项式有理根的算法及程序，该程序较Matlab准确、较Mathematicafb方便实用。算法的复杂度取决于本原多项式 的最高项系数及常数项的大小，但由于取其绝对值的算术根为循环终值，故极大程度地节约了计算时间。不足之处是因为未做大整数运算设计，所以计算中若整数超过15位时会发生数据溢出，有待于继续研究。
图1 程序计算示例
参考文献：
[1] 张禾瑞，郝鈵新.高等代数[M].5版.北京：高等教育出版社，2007：71-76
作者简介： 廖俊义（1991-）， 男， 广东省汕头市人， 韩山师范学院数学与统计学系2010级学生.
通讯作者：王积社（1954 -）， 男， 山西省晋城人， 副教授.主要研究： 数论、数学机械化、数学教育.wangfeng.yz@163.com.