【算法设计与分析基础】18、霍纳法则

package cn.xf.algorithm.ch02;

import java.util.ArrayList;
import java.util.List;

/**
 * 生产随机数
 * @author xiaof
 *
 */
public class Random {

	/**
	 * 生产一个随机数的数列
	 * @param n  生成n个数列
	 * @param m  数据在0和m-1之间
	 * @param seed  随机初始种子
	 * @param a		参数
	 * @param b		参数
	 * @return
	 */
	public static List<Integer> randomNum(int n, int m, int seed, int a, int b)
	{
		List<Integer> numbers = new ArrayList<Integer>();
		int initData = (a * seed + b) % m;
		numbers.add(Math.abs(initData));	//初始化一个数据
		
		for(int i = 1; i < n; ++i)
		{
			int newData = (a * numbers.get(i - 1) + b) % m;
			numbers.add(Math.abs(newData));
		}
		
		return numbers;
	}
	
	/**
	 * 生产一个随机数的数列
	 * @param n 生成n个数列
	 * @param m  数据在0和m-1之间
     * @param seed  随机初始种子
     * @param a     参数
     * @param b     参数
     * @return
	 */
	public static List<Double> randomNumDouble(int n, int m, int seed, int a, int b) {
	    //创建结果数组
	    List<Double> numbers = new ArrayList<Double>();
	    int initData = (a * seed + b) % m; //取出一个初始值，在0到m之间
	    numbers.add((double) Math.abs(initData));   //加入第一个值
	    //后续数值以前一个数据作为基础种子进行变换
	    for(int i = 1; i < n; ++i) {
	        double newData = (a * numbers.get(i - 1) + b) % m;
	        numbers.add(Math.abs(newData));
	    }
	    
	    return numbers;
	}
	
	public static void main(String[] args) {
//		List<Integer> res = Random.randomNum(10, 10, 998, 58797676, 1);
		List<Double> res = Random.randomNumDouble(10, 10, 998, 58797676, 1);
		for(Double a : res)
		{
			System.out.print(a + "\t");
		}
 	}
}

package cn.xf.algorithm.ch06ChangeRule;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

import cn.xf.algorithm.ch02.Random;

/**
 * 
 * 功能：霍纳法则
 * @author xiaofeng
 * @date 2017年7月13日
 * @fileName HornerRule.java
 *
 */
public class HornerRule {
	/**
	 * 用霍纳法则求一个多项式在一个给定点的值
	 * 输入：一个n次多项式的系数数组P【0...n】（从低到高存储），以及一个数字x
	 * 输出：多项式在x点的值
	 * @param p
	 * @param x
	 */
	public Double horner(List<Double> p, int x) {
		if(p == null || p.size() <=0) {
			return 0d;
		}
		//求结果集
		Double result = p.get(p.size() - 1);
		for(int i = p.size() - 2; i >= 0; --i) {
			//累计往后添加系数数据
			//一次从大到小吧X的系数乘以X，  然后加上下一个次数等级的系数，然后求和，作为新的下一个次数的系数乘数
			result = result * x + p.get(i);
		}
		
		return result;
	}
	
	/**
	 * 普通计算方式
	 * @param p
	 * @param x
	 * @return
	 */
	public Double notHorner(List<Double> p, int x) {
	    if(p == null || p.size() <=0) {
            return 0d;
        }
	    
	    //p是系数存储列表
	    Double result = 0d;  //0次幂的
	    for(int i = 0; i < p.size(); ++i) {
	        result += p.get(i) * doublePow(x, i);
	    }
	    
	    return result;
	}
	
	//求x的n次幂
	public static Double doublePow(double x, int n) {
	    if(x == 0) 
	        return 0d;
	    
	    if(n == 0)
	        return 1d;
	    Double result = 1d;
	    for(int i = 0; i < n; ++i) {
	        result *= x;
	    }
	    
	    return result;
	}
	
	@Test
	public void test1() {
	    //定义的一个数组是方程式的系数，第二个参数是未知数的值
	    //方程：y=5x^5 + 3x^4 + 2x^2 + 3
	    //当x为4的时候
	    HornerRule hr = new HornerRule();
	    List<Double> xishus = new ArrayList<Double>();
	    //这个数组的顺序要按照，0次幂到N次幂的顺序来
	    xishus.addAll(Arrays.asList(3d, 0d, 2d, 0d, 3d, 5d));
	    System.out.println(hr.horner(xishus, 4));
	    //一般方式计算
	    System.out.println(hr.notHorner(xishus, 4));
	    System.out.printf("JOB START OUTPUT: %tF %<tT%n", System.currentTimeMillis());
	}
	
	@Test
    public void compare() {
        // 当x为4的时候
        HornerRule hr = new HornerRule();
        // 建造100个随机数
        List<Double> xishus = Random.randomNumDouble(600, 3, 998, 58797676, 1);
        //求值
        System.out.printf("JOB HORNER START OUTPUT: %tF %<tT%n", System.currentTimeMillis());
        System.out.println(hr.notHorner(xishus, 3));
        System.out.printf("JOB HORNER END OUTPUT: %tF %<tT%n", System.currentTimeMillis());
        System.out.println("######################################################################################");
        System.out.printf("JOB NOTHORNER START OUTPUT: %tF %<tT%n", System.currentTimeMillis());
        System.out.println(hr.notHorner(xishus, 3));
        System.out.printf("JOB NOTHORNER END OUTPUT: %tF %<tT%n", System.currentTimeMillis());
        
    }
}