polynomialevaluation.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/**
 *PolynomialEvaluation.java
 *Calculate the polynomial evaluation
 *@author WPC
 *@version 1.0
 */
package cn.edu.whu.iss.algorithm.unit02;
import mypackage.tools.print.P;

/**
 * Polynmial evaluation.
 * @author wpc
 * @version 0.0.1
 *
 */
public class PolynomialEvaluation{

	/**
	 * Naive Polynmial evaluation
	 * @param a the value of the coefficients
	 * @param x the value of x
	 * @return reuslt polynmial evaluation
	 */
	public static int naive(int a[],int x){
		int y	=	0;
		for(int i=0;i<a.length;i++){
			int temp	=	a[i];
			for(int j=1;j<=i;j++){
				temp*=x;
			}
			y+=temp;
		}
		return y;
	}
	
	/**
	 * Horner rule.
	 * P(x)=siguma(a[k]*x^k) (k from 0 to n)
	 * 	=a[0]+x*(a[1]+x*(a[2]+...+x*(a[n-1]+x*a[n])))
	 * @param a the value of the coefficients
	 * @param x the value of the x
	 * @return result of the Polynmial evaluation
	 */
	public static int hornerRule(int a[],int x){
		int y	=	0;
		int	i	=	a.length-1;
		while(i>=0){
			y	=	a[i]+y*x;
			i--;
		}
		return y;
	}
	
	public static void main(String[] args){
		int a[]	=	{1,2,3,4,5};
		int		x	=	5;
		P.rintln(PolynomialEvaluation.naive(a,x));
		P.rintln(PolynomialEvaluation.hornerRule(a,x));
	}
}