From 5ac928038c567f70884d21d363fd862647d373bd Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Thu, 16 Aug 2018 18:15:53 -0500 Subject: Got googletest going and fib last digit done! --- PlaygroundCpp/.cproject | 38 +++++++++++++- PlaygroundCpp/Sources/Playground.cpp | 99 +++++++++++++++++++----------------- 2 files changed, 89 insertions(+), 48 deletions(-) diff --git a/PlaygroundCpp/.cproject b/PlaygroundCpp/.cproject index ea3a3d9..6299ddd 100644 --- a/PlaygroundCpp/.cproject +++ b/PlaygroundCpp/.cproject @@ -65,6 +65,20 @@ + + + + @@ -77,6 +91,12 @@ + + @@ -239,8 +259,24 @@ - + + + + + + + + + + + + + + + + + diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index 47575e1..8ef7faa 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,54 +1,59 @@ #include -#include +//#include -// The following code calls a naive algorithm for computing a Fibonacci number. +//int get_fibonacci_last_digit_naive(int n) { +// if (n <= 1) +// return n; // -// 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)); +// int previous = 0; +// int current = 1; +// +// for (int i = 0; i < n - 1; ++i) { +// int tmp_previous = previous; +// previous = current; +// current = tmp_previous + current; +// } +// +// return current % 10; +//} + +int get_fibonacci_last_digit_optimized(int n) { + if (n <= 1) + return n; + int fibLastDigitArray[n]; + fibLastDigitArray[0] = 0; + fibLastDigitArray[1] = 1; + for (int i = 2; i < n + 1; i++) { + fibLastDigitArray[i] = (fibLastDigitArray[i - 1] + + fibLastDigitArray[i - 2]) % 10; + } + return fibLastDigitArray[n]; } +//TEST(FibLastDigitTest, Zero) { +// ASSERT_EQ(get_fibonacci_last_digit_naive(0), 0); +//} +// +//TEST(FibLastDigitTest, One) { +// ASSERT_EQ(get_fibonacci_last_digit_naive(1), 1); +//} +// +//TEST(FibLastDigitTest, Three) { +// ASSERT_EQ(get_fibonacci_last_digit_naive(3), 2); +//} +// +//TEST(FibLastDigitTest, Forty) { +// ASSERT_EQ(get_fibonacci_last_digit_naive(40), 5); +// ASSERT_EQ(get_fibonacci_last_digit_optimized(40), 5); +//} +// +//TEST(FibLastDigitTest, ThreeThreeOne) { +// ASSERT_EQ(get_fibonacci_last_digit_optimized(331), 9); +// ASSERT_EQ(get_fibonacci_last_digit_optimized(327305), 5); +//} int main() { - int n = 0; + int n; std::cin >> n; - -// std::cout << fibonacci_naive(n) << '\n'; -// test_solution(); - std::cout << fibonacci_fast(n) << '\n'; - return 0; -} - + int c = get_fibonacci_last_digit_optimized(n); + std::cout << c << '\n'; + } -- cgit v1.2.3