import java.io.*;

public class FibonacciNumbers
{
	public static long recursiveFibNum(int n)
	{
		if (n < 3) return 1;
		else return (recursiveFibNum(n-1) + recursiveFibNum(n-2));
	}
	
	public static long FibNum(int n)
	{
		if (n < 3) return 1;
		
		long[] fib = new long[n];
		fib[0] = fib[1] = 1;
		
		for (int i = 2; i < n; i ++)
			fib[i] = fib[i-1] + fib[i-2];
			
		return fib[n-1];
	}



	static BufferedReader keyboard = new BufferedReader 
										    	(new InputStreamReader (System.in));


	public static void main(String[] args) throws IOException
	{
		System.out.println("Hello.  Tell me which Fibonacci number you would like "
								+ "\nto know (1,2,3,etc).  I will tell you how long both "
								+ "\nthe recursive computation and iterative computation "
								+ "\ntook.  Enter n < 1 to quit:");
		
		long t0, t1;
		
		int n = Integer.parseInt(keyboard.readLine());
		long result;
		
		while (n >= 1)
		{
			t0 = System.currentTimeMillis();
			result = FibNum(n);
			t1 = System.currentTimeMillis();		
			System.out.println("The " + n + "th Fibonacci number is " + result + ".");
			
			System.out.println("Iterative computation time: " + (((double)t1 - t0)/1000) + " seconds.");
			
			t0 = System.currentTimeMillis();
			result = recursiveFibNum(n);
			t1 = System.currentTimeMillis();
			
			System.out.println("Recursive computation time: " + (((double)t1 - t0)/1000) + " seconds.");
		
			n = Integer.parseInt(keyboard.readLine());
		}
		
	}
}