diff options
| -rw-r--r-- | PlaygroundCpp/.cproject | 38 | ||||
| -rw-r--r-- | 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 @@ <tool id="cdt.managedbuild.tool.gnu.cpp.linker.exe.debug.1593738472" name="GCC C++ Linker" superClass="cdt.managedbuild.tool.gnu.cpp.linker.exe.debug"> + <option id="gnu.cpp.link.option.paths.1593365739" superClass="gnu.cpp.link.option.paths" valueType="libPaths"> + + <listOptionValue builtIn="false" value="/home/haidong/googletest/build/googlemock/gtest"/> + + </option> + + <option id="gnu.cpp.link.option.libs.2046973616" superClass="gnu.cpp.link.option.libs" valueType="libs"> + + <listOptionValue builtIn="false" srcPrefixMapping="" srcRootPath="" value="gtest"/> + + <listOptionValue builtIn="false" srcPrefixMapping="" srcRootPath="" value="gtest_main"/> + + </option> + <inputType id="cdt.managedbuild.tool.gnu.cpp.linker.input.1967757968" superClass="cdt.managedbuild.tool.gnu.cpp.linker.input"> <additionalInput kind="additionalinputdependency" paths="$(USER_OBJS)"/> @@ -77,6 +91,12 @@ <tool id="cdt.managedbuild.tool.gnu.assembler.exe.debug.183585801" name="GCC Assembler" superClass="cdt.managedbuild.tool.gnu.assembler.exe.debug"> + <option id="gnu.both.asm.option.include.paths.1592126793" superClass="gnu.both.asm.option.include.paths" valueType="includePath"> + + <listOptionValue builtIn="false" value="/home/haidong/googletest/googletest/include"/> + + </option> + <inputType id="cdt.managedbuild.tool.gnu.assembler.input.641163583" superClass="cdt.managedbuild.tool.gnu.assembler.input"/> </tool> @@ -239,8 +259,24 @@ <storageModule moduleId="org.eclipse.cdt.core.LanguageSettingsProviders"/> - <storageModule moduleId="refreshScope"/> + <storageModule moduleId="refreshScope" versionNumber="2"> + + <configuration configurationName="Debug"> + + <resource resourceType="PROJECT" workspacePath="/PlaygroundCpp"/> + + </configuration> + + <configuration configurationName="Release"> + + <resource resourceType="PROJECT" workspacePath="/PlaygroundCpp"/> + + </configuration> + + </storageModule> <storageModule moduleId="org.eclipse.cdt.make.core.buildtargets"/> + + <storageModule moduleId="org.eclipse.cdt.internal.ui.text.commentOwnerProjectMappings"/> </cproject> 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'; + } |