秦九韶算法java程序_算法 秦九韶算法

1 packagecom.qyf404.learn.algorithm;2

3 importjava.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+a011 *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+a016 *17 *@authorqyfmac18 */

19 public classHornerAlgorithm {20 private doublea[];21 privateDouble x;22

23 public HornerAlgorithm(double[] a, doublex) {24 this.a =a;25 this.x =x;26 }27 public voidcheck(){28 if(a == null || x == null || a.length < 1){29 throw newRuntimeException();30 }31 }32

33 /**

34 * 简单的for循环实现35 *36 * 测试比较使用37 *@return

38 */

39 private doubleoldCompute() {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 returns;46 }47 /**

48 * 简单的for循环实现49 *50 * 测试比较使用51 *@return

52 */

53 privateBigDecimal 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(newBigDecimal(a[i])));59 }60 returns;61 }62

63

64 /**

65 * 秦九韶算法实现66 *67 *@return

68 */

69 public doublecompute() {70 check();71

72 int n = a.length -1;73 double s =a[n];74

75 if(n == 0){76 //f(x)=a0 的情况

77 returns;78 }79

80 int i = 0;81 do{82 i++;83 s = a[n-i] + x *s;84

85 }while(i

87

88 returns;89 }90 /**

91 * 秦九韶算法实现92 *93 *@return

94 */

95 publicBigDecimal compute2BigDecimal() {96 check();97

98 int n = a.length -1;99 BigDecimal s = newBigDecimal(a[n]);100

101 if(n == 0){102 //f(x)=a0 的情况

103 returns;104 }105 BigDecimal x = new BigDecimal(this.x);106 int i = 0;107 do{108 i++;109 s = new BigDecimal(a[n-i]).add(s.multiply(x));110

111 }while(i

113

114 returns;115 }116

117 public static voidmain(String[] args) {118 //double a[] ={1};119 //double a[] ={1,1};120 //double a[] ={1,1,1};121 //double a[] ={1,1,1,2};

122 double a[] = { 1 ,111.3 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,111 ,11};123 double x = 2;124 HornerAlgorithm ha = newHornerAlgorithm(a, x);125

126 {127 long start =System.currentTimeMillis();128 BigDecimal s =ha.oldCompute2BigDecimal();129 long end =System.currentTimeMillis();130 System.out.println("耗时" + (end - start) + "结果为" +s);131 }132 {133 long start =System.currentTimeMillis();134 BigDecimal s =pute2BigDecimal();135 long end =System.currentTimeMillis();136 System.out.println("耗时" + (end - start) + "结果为" +s);137 }138

139 }140 }