问题
给定一个整数系数的多项式，我们要得到所有的有理数解x，使得x代入多项式为0。有理数解就是能用分数表示的解。
解题思路
如果有理数解为p/q，则多项式可分解成若干个（x-p/q）相乘的形式，其中p是多项式常数项系数的因数，q是多项式最高次项系数的因数。这样分解之后x=p/q就是我们需要求的有理数解，所以只需要尝试所有p、q的组合，判断p/q是否满足多项式为0，即可。需要注意的是，（1）要考虑负根（2）不能去掉重根，应该把所有的重根都列出来。
代码如下：
#方程式求有理数根import math
import fractionsdef add_poly(L1,L2):#多项式加法R=[]if len(L1)>len(L2):L1,L2=L2,L1i=0while i<len(L1):R.append(L1[i]+L2[i])i+=1R=R+L2[len(L1):len(L2)]return Rdef subtract_poly(L1,L2):#多项式减法R=[]L2=L2[:]#为了不改变原来的L2for i in range(len(L2)):L2[i]=-L2[i]R=add_poly(L1,L2)return Rdef multiply_poly(L1,L2):#多项式乘法if len(L1)>len(L2):L1,L2=L2,L1zero=[];R=[]for i in L1:T=zero[:]for j in L2:T.append(i*j)R=add_poly(R,T)zero=zero+[0]return Rdef divide_poly(L1,L2):#多项式除法if len(L1)<len(L2):return [0]d=len(L1)-len(L2)T=L1[:];R=[]for i in range(d+1):n=T[len(T)-1]/L2[len(L2)-1]R=[n]+RT1=[0]*(d-i)+[n]T2=multiply_poly(T1,L2)T=subtract_poly(T,T2)T=T[:len(T)-1]return Rdef check(L,s):#检查根代入方程式是否为0sum1=0for t in range(len(L)):if t==0:sum1=sum1+L[t]else:sum1=sum1+L[t]*s**tif abs(sum1)<1e-15:return True #检查sum1是否和0相等，一个小数的绝对值小于le-15就近似等于0.else:return False#if round(sum1, 20) < 1e-15:# return True#else:# return Falsedef rational(L):R=[]#存放最高次项系数的因数T=[]#存放常数项系数的因数S=[]#存放结果#求出次数最高次项系数的因数存放在R中k1=1while k1<=math.sqrt(abs(L[len(L)-1])):q=L[len(L)-1]/k1if int(q)==q:if q==k1 :R.append(int(q))else:R.append(k1)R.append(int(q))k1=k1+1#print(R)#求出常数项的所有因数存放在T中 k2=1while k2<=math.sqrt(abs(L[0])):p=L[0]/k2if int(p)==p:if p==k2 :T.append(int(p))else:T.append(k2)T.append(int(p))k2=k2+1#print(T)for i in T:for j in R:s1 = fractions.Fraction(i, j)#s1=i/jwhile check(L,s1):#用while循环主要是为了不去除重根S.append(s1)L=divide_poly(L,[-s1,1])#得到一个根之后就去除去一个因式ax-1，更新被除数#print(1,L,S)s2 = fractions.Fraction(-i, j)#s2是为了验证负根s2=-i/jwhile check(L,s2):S.append(s2)L=divide_poly(L,[-s2,1])#print(2,L,S)#print(S)return Sdef to_String(S):#把多项式列表转化成表达式str1=""for x in S:if x==0:str1="x"elif x>0:str1="(x-"+str(x)else :str1="(x+"+str(abs(x))str1=str1+")"print(str1,end="")print("\n")while True:s=input("请输入一个方程式的系数（低次项系数在前,以空格分隔）")L1=s.split(" ")L=[int(e) for e in L1]print("L:",L)S=rational(L)if len(S)==0:print("No solution!\n")else:print("方程分解成有理数根的形式是：",end="")to_String(S)