算法 《秦九韶算法java实践》 | 您所在的位置:网站首页 › 秦九韶多项式算法求根 › 算法 《秦九韶算法java实践》 |
【历史背景】 秦九韶算法是中国南宋时期的数学家秦九韶表述求解一元高次多项式的值的算法——正负开方术。它也能够配合牛顿法用来求解一元高次多项式的根。在西方被称作霍纳算法(Horner algorithm或Horner scheme),是以英国数学家威廉·乔治·霍纳命名的。 【原理解释】 设有n+1项的n次函数 f(x)=anxn+ an-1xn-1+an-2xn-2+ an-3xn-3+…… a2x2+a1x+ a0 将前n项提取公因子x,得 f(x)=(anxn-1+ an-1xn-2+an-2xn-3+…… a2x+a1)+ a0 再将括号内的前n-1项提取公因子x,得 f(x)=((anxn-2+ an-1xn-3+an-2xn-4+…… a2)x+ a1)x+a0 如此重复提取公因子x,最后将函数化为 f(x)=(((anx+ an-1)x+ an-2)x+……+a1)x+a0 令f1= anx+ an-1 f2=f1x+ an-2 f3=f2x+ an-3 。。。 fn=fn-1x+ a0 则fn即为所求 【代码演示样例】 AlgorithmCalculatorService.java /** * 获取系数集合 * @param N 多项式个数 * @return 系数集合 */ public static ArrayList getCoefficientList(Integer N) { ArrayList AnList = new ArrayList(); //随机生成N个0到10之间的系数 Random random = new Random(); while(N > 0) { AnList.add((double) (Math.round(random.nextFloat()*100)/10.0)); //随机一个[0-10]之间的一位小数 N--; } return AnList; } /** * 运行传统算法并获取结果 * 模板为 An*X^n + An-1*X^n-1 + ... A1X + A0 * @param AnList 系数集合 * @param X X值 * @return 计算结果 */ public static String getResultByTrandition(ArrayList AnList, Float X) { int N = AnList.size() - 1; Double result = 0D; long start = System.currentTimeMillis(); //获取当前时间,单位为毫秒 for(Double An : AnList) {//遍历系数集合,每一次循环计算出一项的值,并相加 Double Xn = 1D; int i = 0; while(i |
CopyRight 2018-2019 实验室设备网 版权所有 |