diff options
5 files changed, 141 insertions, 19 deletions
diff --git a/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp b/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp index adc7404..c2564b8 100644 --- a/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp +++ b/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp @@ -7,10 +7,27 @@ int calc_fib(int n) { return calc_fib(n - 1) + calc_fib(n - 2); } +int fib(int n) +{ + int a, b, c, i; + + if (n <= 1) + return n; + + a = 0; b = 1; + for(i = 1; i < n; i++) { + c = a + b; + a = b; + b = c; + } + + return b; +} + int main() { int n = 0; std::cin >> n; - std::cout << calc_fib(n) << '\n'; + std::cout << fib(n) << '\n'; return 0; } diff --git a/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/fibonacci_last_digit.cpp b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/fibonacci_last_digit.cpp index 08e8dd8..f064113 100644 --- a/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/fibonacci_last_digit.cpp +++ b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/fibonacci_last_digit.cpp @@ -1,8 +1,23 @@ #include <iostream> int get_fibonacci_last_digit(int n) { - //write your code here - return 0; + int a, b, c, i; + + if (n <= 1) + return n; + + a = 0; b = 1; + for(i = 1; i < n; i++) { + c = a + b; + if (c >= 10) + c -= 10; + a = b; + b = c; + } + if (b >= 10) + b -= 10; + + return b; } int main() { diff --git a/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp b/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp index f723be2..fc13392 100644 --- a/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp +++ b/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp @@ -1,16 +1,31 @@ #include <iostream> -int gcd(int a, int b) { - //write your code here - int current_gcd = 1; - for (int d = 2; d <= a && d <= b; d++) { - if (a % d == 0 && b % d == 0) { - if (d > current_gcd) { - current_gcd = d; - } +int gcd(int a, int b) +{ + int d, r; + + if ((a == b) || (a == 0)) + return a; + + if (b == 0) + return b; + + if (b > a) { + d = a; + a = b; + b = d; } - } - return current_gcd; + + for(;;) { + d = a / b; + r = a - (d * b); + if (r == 0) + break; + a = b; + b = r; + } + + return b; } int main() { diff --git a/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp b/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp index c6f503c..62e7799 100644 --- a/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp +++ b/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp @@ -1,8 +1,36 @@ #include <iostream> -long long lcm(int a, int b) { - //write your code here - return a*b; +long long gcd(int a, int b) +{ + long long d, r; + + if ((a == b) || (a == 0)) + return a; + + if (b == 0) + return b; + + if (b > a) { + d = a; + a = b; + b = d; + } + + for(;;) { + d = a / b; + r = a - (d * b); + if (r == 0) + break; + a = b; + b = r; + } + + return (long long) b; +} + +long long lcm(int a, int b) +{ + return (b / gcd(a, b)) * a; } int main() { diff --git a/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp b/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp index db0c074..8a9a61c 100644 --- a/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp +++ b/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp @@ -1,8 +1,55 @@ #include <iostream> -long long get_fibonaccihuge(long long n, long long m) { - //write your code here - return 0; +long long get_fibonaccihuge(long long n, long long m) +{ + long long a, b, c, i; //, r, g, R; + long long g; + + // length of pisano period pi(m) + a = 0; b = 1; + g = 0; + /* Fi mod m */ + for (i = 0; ; i++) { + c = a + b; + if (c >= m) + c -= m; + // start pattern is 011 + if (c == 0) + g = ((g == 0) ? 1 : 0); + else if (g == 1) + g = ((c == 1) ? 2 : 0); + else if (g == 2) { + if (c == 1) + break; + g = 0; + } + /* if (g == 2) { */ + /* i += 1; */ + /* break; */ + /* } */ + + a = b; + b = c; + } + + /* g = n % i; */ + g = (n / i); + g = n - (g * i); + + if (g <= 1) + return g; + + /* Fg mod m */ + a = 0; b = 1; + for (i = 1; i < g; i++) { + c = a + b; + if (c >= m) + c -= m; + a = b; + b = c; + } + + return b; } int main() { |