递归

1.经典汉诺塔：

//x to z  tmp:y
import java.io.*;
public class Main {
	public static void hanoi(int n, char x, char y, char z) {
		if(n != 0) {
			hanoi(n-1, x, z, y);
			System.out.println(x + "->" + z);
			hanoi(n-1, y, x, z);
		}
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer in =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		int n;
		while(in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			hanoi(n, 'a', 'b', 'c');
		}
	}
}

2.必须经过中间

//x to z by y
import java.io.*;
public class Main {
	static int len = 0;
	public static void hanoi(int n, char x, char y, char z) {
		if(n != 0) {
			hanoi(n-1, x, y, z);
			System.out.println(x + "->" + y);
			len++;
			hanoi(n-1, z, y, x);
			System.out.println(y + "->" + z);
			hanoi(n-1, x, y, z);
			len++;
		}
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer in =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		int n;
		while(in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			hanoi(n, 'a', 'b', 'c');
			System.out.println(len);
		}
	}
}

3.全排列生成器

import java.io.*;
public class Main {
	public static void perm(int[] a, int k, int n) {
		if (k == n) {
			for (int i = 1; i <= n; ++i) {
				if (i == 1)
					System.out.print(a[1]);
				else
					System.out.print(" " + a[i]);
			}
			System.out.println();
		} else {
			for (int i = k; i <= n; ++i) {
				int tmp = a[k];
				a[k] = a[i];
				a[i] = tmp;
				perm(a, k + 1, n);
				tmp = a[i];
				a[i] = a[k];
				a[k] = tmp;
			}
		}
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(
				new InputStreamReader(System.in)));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			int n = (int) in.nval;
			int[] a = new int[n + 1];
			for (int i = 1; i <= n; ++i)
				a[i] = i;
			perm(a, 1, n);
		}
	}
}

4.01背包，回溯

import java.io.*;
public class Main {
    static int[] v, w;
    static int maxv, c, n;
    public static void knap(int i, int tw, int tv) {
        if(i == n) {
            if(tw<=c && tv>maxv) {
                maxv = tv;
            }
        } else {
            if(tw+w[i]<=c)
                knap(i+1, tw+w[i], tv+v[i]);
            knap(i+1, tw, tv);
        }
    }
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int t= (int) in.nval;
        while(t-- != 0) {
            maxv = 0;
            in.nextToken();
            n = (int) in.nval;
            v = new int[n];
            w = new int[n];
            in.nextToken();
            c = (int) in.nval;
            for(int i=0; i<n; ++i) {
                in.nextToken();
                v[i] = (int) in.nval;
            }
            for(int i=0; i<n; ++i) {
                in.nextToken();
                w[i] = (int) in.nval;
            }
            knap(0,0,0);
            System.out.println(maxv);
        }
    }
}