recursivemethodsfortiming.java

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

public class RecursiveMethodsForTiming
{
	int[] a;

	/**	Handle the array segment from p to q. */
	public int test(int p, int q)
	{
		int total;
		int size = q - p + 1;
		if (size < 5)
		{
			total = 0;
			for (int i = p; i != q + 1; i++)
			{
				total += a[i];
				System.out.print(total + " ");
			}
			System.out.println();
		}
		else
		{
			int fifth = (size + 4) / 5;
			total = test(p, p + 2 * fifth)
				+ test(p + 1 * fifth, p + 4 * fifth)
				+ test(p + 3 * fifth, q);
			System.out.print("\n" + total + "\n");
		}
		return total;
	}
	
	public float sum(float[ ] a, int n)
	{
		if(n == 1)
			return a[1];
		else
			return sum(a, n - 1) + a[n];
	}

	int best = 0;

	public void knapSack(int[ ] p, int[ ] a, int k, int n)
	{
		if (k == 0)
		{
			int v = 0;
			for (int i = 1; i <= n; i++)
				v = v + p[i] * a[i];
			if(v > best)
				best = v;
		}
		else
		{
			a[k] = 0;
			knapSack(p, a, k - 1, n);
			a[k] = 1;
			knapSack(p, a, k - 1, n);
		}
	}

	public int f(int n)
	{
		if ((n == 0) || (n == 1))
		{
			System.out.println(1);
			return 1;
		}
		else
		{
			int x = f(n - 1);
			System.out.println(x);
			int y = f(n - 2);
			System.out.println(y);
			System.out.println(x + y);
			return x + y;
		}
	}
}