java算法：基于应用ADT例子

java算法：基于应用ADT例子

例1：多项式ADT接口

class Poly{
    Poly(int,int)
    double eval(double)
    void add(Poly)
    void mult(Poly)
    public String toString()
}

class Poly{
	Poly(int,int)
	double eval(double)
	void add(Poly)
	void mult(Poly)
	public String toString()
}

例2：多项式客户程序

public class Binomial{
    public static void main(String args[]){
        int N = 100;
        double p = 1.1;
        Poly y = new Poly(1,0);
        Poly t = new Poly(1,0);
        t.add(new Poly(1,1));
        for(int i = 0; i < N; i++){
            y.mult(t);
            System.out.println(y + " ");
        }
        System.out.println("value: " + y.eval(p));
    }
}

public class Binomial{
	public static void main(String args[]){
		int N = 100;
		double p = 1.1;
		Poly y = new Poly(1,0);
		Poly t = new Poly(1,0);
		t.add(new Poly(1,1));
		for(int i = 0; i < N; i++){
			y.mult(t);
			System.out.println(y + " ");
		}
		System.out.println("value: " + y.eval(p));
	}
}

例3：多项式ADT的数组实现

class Poly{
    private int n;
    private int[] a;
    Poly(int c,int N){
        a = new int[N+1];
        n = N + 1;
        a[N] = c;
        for(int i = 0; i < N; i++){
            a[i] = 0;
        }
    }
    double eval(double d){
        double t = 0.0;
        for(int i = n - 1; i >= 0; i--){
            t = t * d + (double)a[i];
        }
        return t;
    }
    void add(Poly p){
        int[] t = new int[(p.n > n) ? p.n : n];
        for(int i = 0; i < p.n; i++){
            t[i] = p.a[i];
        }
        for(int j = 0; j < n; j++){
            t[j] += a[j];
        }
        a = t;
        n = t.length;
    }
    void mult(Poly p){
        int[] t = new int[p.n + n -1];
        for(int i = 0; i < p.n; i++){
            for(inti j = 0; j < n; j++){
                t[i+j] += p.a[i] * a[j];
            }
        }
        a = t;
        n = t.length;
    }
    public String toString(){
        String s = "";
        for(int i = 0; i < n; i++){
            s += a[i] + " ";
        }
        return s;
    }
}

class Poly{
	private int n;
	private int[] a;
	Poly(int c,int N){
		a = new int[N+1]; 
		n = N + 1; 
		a[N] = c;
		for(int i = 0; i < N; i++){
			a[i] = 0;
		}
	}
	double eval(double d){
		double t = 0.0;
		for(int i = n - 1; i >= 0; i--){
			t = t * d + (double)a[i];
		}
		return t;
	}
	void add(Poly p){
		int[] t = new int[(p.n > n) ? p.n : n];
		for(int i = 0; i < p.n; i++){
			t[i] = p.a[i];
		}
		for(int j = 0; j < n; j++){
			t[j] += a[j];
		}
		a = t;
		n = t.length;
	}
	void mult(Poly p){
		int[] t = new int[p.n + n -1];
		for(int i = 0; i < p.n; i++){
			for(inti j = 0; j < n; j++){
				t[i+j] += p.a[i] * a[j];
			}
		}
		a = t;
		n = t.length;
	}
	public String toString(){
		String s = "";
		for(int i = 0; i < n; i++){
			s += a[i] + " ";
		}
		return s;
	}
}

注意：Horner算法：a₄x⁴ + a₃x³ + a₂x² + a₁x + a₀ = (((a₄x + a₃)x + a₂)x + a₁)x + a₀