import java.util.Scanner;

public class Combi {

	/**
	 * Recursive computation of n choose k
	 * @param n >= 0
	 * @param k <= n
	 * @return the number of possible combinations of
	 * k out of n
	 */
	public long combRec(long n, long k){
		// pre: 0 <= k <= n
		// post:  return the number of possible combinations of
		// k out of n
		if (n==k || k==0) return 1;
		else // n>k and k>0
			return combRec(n-1,k-1) + combRec(n-1,k);
	}

	/*
	 * Fast Spock
	 */
	public long combFast(int n, int k, long[][] A) {
		long r;
		if (n==k || k==0) {
			A[n][k]=1;
			return 1;
		}
		else if (A[n][k] == 0) {
			r = combFast(n-1,k-1,A) + combFast(n-1,k,A);
			A[n][k] = r;
			return r;
		}
		else {
			r = A[n][k];
			return r;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner Input = new Scanner(System.in);
		int n;
		long start, finish, res;
		Combi S = new Combi();
		do{
			System.out.println("Enter set size n>0  (0 to finish)");
			n = Input.nextInt();

			if(n>0) {
				long[][] A = new long[n+1][n+1];
				for(int k = 0; k<=n; k++){ 

					start = System.currentTimeMillis();
					res = S.combFast(n, k, A);
					finish = System.currentTimeMillis();
					System.out.println("Number of combinations (fast): (" +
							n + " choose " +k+ ")  =  " + res + " time = " + (finish-start) + "  milliseconds");

					start = System.currentTimeMillis();
					res = S.combRec(n, k);
					finish = System.currentTimeMillis();
					System.out.println("Number of combinations (slow): (" +
							n + " choose " +k+ ")  =  " + res + ", time = " + (finish-start) + "  milliseconds\n");


				}
			}
		}
		while (n > 0);
	}

}