From 89985ca174a2355b4a8e0ebbc81180f78cb3b6ff Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Mon, 13 Aug 2018 21:56:10 -0500
Subject: First optimized Fibonacci done!

---
 PlaygroundCpp/Sources/Playground.cpp | 71 +++++++++++++++++++++++++-----------
 1 file changed, 49 insertions(+), 22 deletions(-)

(limited to 'PlaygroundCpp/Sources')

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 73738d3..47575e1 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,27 +1,54 @@
 #include <iostream>
-using std::cin;
-using std::cout;
+#include <cassert>
 
-int main() {
-	int bigger = 0;
-	int biggest = 0;
-	int n;
-	int i;
-	cin >> n;
-
-	for (int j = 0; j < n; j++) {
-		cin >> i;
-		if (i > biggest) {
-			bigger = biggest;
-			biggest = i;
-		} else if (i == biggest) {
-			bigger = i;
-		} else if (i > bigger) {
-			bigger = i;
+// The following code calls a naive algorithm for computing a Fibonacci number.
+//
+// What to do:
+// 1. Compile the following code and run it on an input "40" to check that it is slow.
+//    You may also want to submit it to the grader to ensure that it gets the "time limit exceeded" message.
+// 2. Implement the fibonacci_fast procedure.
+// 3. Remove the line that prints the result of the naive algorithm, comment the lines reading the input,
+//    uncomment the line with a call to test_solution, compile the program, and run it.
+//    This will ensure that your efficient algorithm returns the same as the naive one for small values of n.
+// 4. If test_solution() reveals a bug in your implementation, debug it, fix it, and repeat step 3.
+// 5. Remove the call to test_solution, uncomment the line with a call to fibonacci_fast (and the lines reading the input),
+//    and submit it to the grader.
+
+int fibonacci_naive(int n) {
+    if (n <= 1)
+        return n;
+
+    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2);
+}
+
+int64_t fibonacci_fast(int n) {
+    // write your code here
+		if (n <= 1)
+			return (int64_t) n;
+		int64_t fibArray [n+1];
+		fibArray[0] = 0;
+		fibArray[1] = 1;
+		for (int j = 2; j < n+1; j++) {
+			fibArray[j] = fibArray[j - 1] + fibArray[j - 2];
 		}
-	}
+		return fibArray[n];
+
+}
+
+void test_solution() {
+    assert(fibonacci_fast(3) == 2);
+    assert(fibonacci_fast(10) == 55);
+    for (int n = 0; n < 20; ++n)
+        assert(fibonacci_fast(n) == fibonacci_naive(n));
+}
 
-	int64_t prod = (int64_t) bigger * (int64_t) biggest;
-	cout << prod << "\n";
-	return 0;
+int main() {
+    int n = 0;
+    std::cin >> n;
+
+//    std::cout << fibonacci_naive(n) << '\n';
+//    test_solution();
+    std::cout << fibonacci_fast(n) << '\n';
+    return 0;
 }
+
-- 
cgit v1.2.3