| 算法 秦九韶算法 | 您所在的位置：网站首页 › 秦九韶多项式算法程序 › 算法 秦九韶算法 |
算法 秦九韶算法
|
秦九韶算法又叫霍纳算法。 一般地，一元n次多项式的求值需要经过[n（n+1）]/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。在人工计算时，一次大大简化了运算过程。 Pn(x)= anx ^n+a(n－1)x^(n-1)+…+a1x+a0 可简化成 Pn(x)= anx ^n+a(n－1)x^(n-1)+…+a1x+a0=((…(((anx +an－1)x+an－2)x+ an－3)…)x+a1)x+a0 java实现 1 package com.qyf404.learn.algorithm; 2 3 import java.math.BigDecimal; 4 5 /** 6 * 7 秦九韶算法又称霍纳算法。 一般地，一元n次多项式的求值需要经过[n（n+1）]/2次乘法和n次加法， 8 * 而秦九韶算法只需要n次乘法和n次加法。在人工计算时，一次大大简化了运算过程。 9 * 10 * Pn(x)= anx ^n+a(n－1)x^(n-1)+…+a1x+a0 11 * 12 * 可简化成 13 * 14 * Pn(x)= anx ^n+a(n－1)x^(n-1)+…+a1x+a0=((…(((anx +an－1)x+an－2)x+ 15 * an－3)…)x+a1)x+a0 16 * 17 * @author qyfmac 18 */ 19 public class HornerAlgorithm { 20 private double a[]; 21 private Double x; 22 23 public HornerAlgorithm(double[] a, double x) { 24 this.a = a; 25 this.x = x; 26 } 27 public void check(){ 28 if(a == null || x == null || a.length < 1 ){ 29 throw new RuntimeException(); 30 } 31 } 32 33 /** 34 * 简单的for循环实现 35 * 36 * 测试比较使用 37 * @return 38 */ 39 private double oldCompute() { 40 check(); 41 double s = 0; 42 for (int i = 0; i < a.length; i++) { 43 s = s + Math.pow(x, i) * a[i]; 44 } 45 return s; 46 } 47 /** 48 * 简单的for循环实现 49 * 50 * 测试比较使用 51 * @return 52 */ 53 private BigDecimal oldCompute2BigDecimal() { 54 check(); 55 BigDecimal x = new BigDecimal(this.x); 56 BigDecimal s = new BigDecimal(0); 57 for (int i = 0; i < a.length; i++) { 58 s = s.add(x.pow(i).multiply(new BigDecimal(a[i]))); 59 } 60 return s; 61 } 62 63 64 /** 65 * 秦九韶算法实现 66 * 67 * @return 68 */ 69 public double compute() { 70 check(); 71 72 int n = a.length -1; 73 double s = a[n]; 74 75 if(n == 0){ 76 //f(x)=a0 的情况 77 return s; 78 } 79 80 int i = 0; 81 do{ 82 i++; 83 s = a[n-i] + x * s; 84 85 }while(i |
【本文地址】
公司简介
联系我们