判断两多项式之积是否等于另一多项式

问题描述：判断p(x),q(x)之积是否等于r(x),p,q,r分别为m,n,l 阶多项式 Random_polynomial(p(x),q(x),r(x),m,n,l) 输入：随机选取X[1:k] 输出：p(x)*q(x)是否等于r(x) 1          K =max{m+n,l} 2          For k=1 to K do 3              X[k] = random(real)    //no repeat 4          For k=1 to K do 5              If(p(X[k])* q(X[k])!= r(X[k])) then 6                  Return false 7          Return true 获得正确解的概率： 若p(x)*q(x)与r(x)阶数相同成立，则对任意的k成立，输出正确解；若不成立，除非找到p(x)*q(x)-r(x)=0的k个根，否则等式一定不成立。 设实数集合大小为S，则找到k个根的概率为max{m+n,l}/S,因此一定为错误解的概率为max{m+n,l}/S。 时间复杂度：O(max{m+n,l}) 综上所述，若算法返回false则一定位正确解；若放回true，则正确解的概率为1-max{m+n,l}/S。 由于算法并不能总获得问题的正确解，显然该随机算法为蒙特卡洛算法。