Fibonacci-/Fibonacci.java at master · lyailyam/Fibonacci- · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package Tests;

import csci152.adt.Map;
import csci152.impl.LLQHashTableMap;

public class Fibonacci {

	/////////////////////////
	// Version One
	/////////////////////////

	private static int callCount1;

	public static long fibCalc1(int n) {

		if (n == 0 || n == 1) {
                    return n;
                }
		callCount1++;
		return (fibCalc1(n-1)+fibCalc1(n-2));
	}


	public static void testFibCalc1(int n) {
		callCount1 = 0;
		System.out.println("fibCalc1("+n+") = " + fibCalc1(n) +
				"; takes " + callCount1 + " calls.");
	}

	/////////////////////////
	// Version Two
	/////////////////////////

	private static int callCount2;
	private static Map<Integer, Long> ansMap = new LLQHashTableMap(5);

	public static long fibCalc2(int n) {

                if (ansMap.getValue(n) != null) {
                    return ansMap.getValue(n);
                }
            	if (n == 0 || n == 1) {
                    return n;
                }
		callCount2++;
                long x = fibCalc1(n-1)+fibCalc1(n-2);
                ansMap.define(n,x);
		return x;
	}


	public static void testFibCalc2(int n) {
		callCount2 = 0;

		System.out.println("fibCalc2("+n+") = " + fibCalc2(n) +
				"; takes " + callCount2 + " calls.");
	}

	///////////

	public static void main(String[] args) {

		for (int x = 0; x < 30; x++) {
			testFibCalc1(x);
		}

		for (int x = 0; x < 30; x++) {
			testFibCalc2(x);
		}

	}
}