methodsfortimingproblems.java

国外的数据结构与算法分析用书

import java.util.*;

/**	This class consists three methods, they are method1, HQPTiming, and maxCons */
public class MethodsForTimingProblems
{
	int m, n;
	int[] u;
	int[] v;
	
	public MethodsForTimingProblems()  throws Exception
	{	
		method1(u);
		
		HPQTiming();
		
		maxCons();
		
		testNumbers();	
		
		TimingArray ta = new TimingArray();
	}

	public double method1(int[] arr)
	{
		double sum = 0;
    		for (int i = 0; i < arr.length; i++)
        		sum += Math.abs(arr[i] - average(arr));
   		 return sum/arr.length;
   	}
   	
   	public double average(int[] arr)
   	{
   		int sum = 0;
   		for(int i =0; i< arr.length; i++)
   		{
   			sum += arr[i];
   		}
   		return sum/arr.length;
   	}
   	
   	public void HPQTiming()
   	{
   		int x = 10;
   		x = h(10);
   		p();
   		q(10);
   	}
   	
   	public int h(int x) 
	{
		int i = 0;
		while ((i < m) || (u[i] != x))
		{
			r();
			i++;
		}
		return i;
	}
 
	public void p()
	{
		for (int j = 0; j < n; j = 2 * j)
			v[j] = h(j) + w(j);
		q(m);
	}

	public void q(int  k)
	{
		u[k] = w(2 * k + 1);
		if (k - 1 > 0)
			q(k-1);
	}
	
	public void r()
	{
		for(int i=0; i<= Math.log(n*1.0); i++)
		{
			i +=i;
		}
	}
			
	public int w(int i)
	{
		for(int j=0; j<=m; j++)
		{
			i += j;
		}
		return i;
	}
	
	public void maxCons()
	{
		int[] x = new int[10];
		int result1 = maxCon1(x);
		int result2 = maxCon2(x);
	}
	
	/**	The maximum sum found in any contiguous subvector. */
	public int maxCon1(int[] x)
	{
		int maxSoFar = 0;
		for (int lower = 0; lower < x.length; lower++)
			for (int upper = lower; upper < x.length; upper++)
			{
				int sum = 0;
				for (int k = lower; k <= upper; k++)
					sum += x[k];
				if (sum > maxSoFar)
					maxSoFar = sum;
			}
		return maxSoFar;
	}

	/**	The maximum sum found in any contiguous subvector. */
	public int maxCon2(int[] x)
	{
		int maxSoFar = 0;
		for (int lower = 0; lower < x.length; lower++)
		{
			int sum = 0;
			for (int upper = lower; upper < x.length; upper++)
			{
				sum += x[upper];
				if (sum > maxSoFar)
					maxSoFar = sum;
			}
		}
		return maxSoFar;
	}
	
	public void testNumbers()
    	{   
        	System.out.println("starting testNumber");
    		NumberList n1 = new NumberList(20);
        	n1.fill(4);
        	System.out.println("Capacity : " + n1.capacity);
        	System.out.println(n1.findNumber(3));
       		n1.printDuplicates();
        	NumberList n2 = new NumberList(10);
        	n2.fill(6);
        	n2.summarize(n1);
        	System.out.println("\nFinish testNumber");
       	}
}