summaryrefslogtreecommitdiff
path: root/PlaygroundCpp/Sources
diff options
context:
space:
mode:
Diffstat (limited to 'PlaygroundCpp/Sources')
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp99
1 files changed, 52 insertions, 47 deletions
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 <iostream>
-#include <cassert>
+//#include <gtest/gtest.h>
-// 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';
+ }