Algorithms : add 01-algorithmic_toolbox 01-intro

25 files changed, 131 insertions, 0 deletions

diff --git a/01-algorithmic_toolbox/01-intro/00_introduction_problems.pdf b/01-algorithmic_toolbox/01-intro/00_introduction_problems.pdf
new file mode 100644
index 0000000..0092b73
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/00_introduction_problems.pdf
diff --git a/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp b/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp
new file mode 100644
index 0000000..adc7404
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/01-fibonacci/fibonacci.cpp
@@ -0,0 +1,16 @@
+#include <iostream>
+
+int calc_fib(int n) {
+    if (n <= 1)
+        return n;
+
+    return calc_fib(n - 1) + calc_fib(n - 2);
+}
+
+int main() {
+    int n = 0;
+    std::cin >> n;
+
+    std::cout << calc_fib(n) << '\n';
+    return 0;
+}
diff --git a/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/01 b/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/01
new file mode 100644
index 0000000..00750ed
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/01
@@ -0,0 +1 @@
+3
diff --git a/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/01.a b/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/01.a
new file mode 100644
index 0000000..0cfbf08
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/01.a
@@ -0,0 +1 @@
+2
diff --git a/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/02 b/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/02
new file mode 100644
index 0000000..f599e28
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/02
@@ -0,0 +1 @@
+10
diff --git a/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/02.a b/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/02.a
new file mode 100644
index 0000000..c3f407c
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/01-fibonacci/tests/02.a
@@ -0,0 +1 @@
+55
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
new file mode 100644
index 0000000..08e8dd8
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/fibonacci_last_digit.cpp
@@ -0,0 +1,13 @@
+#include <iostream>
+
+int get_fibonacci_last_digit(int n) {
+  //write your code here
+  return 0;
+}
+
+int main() {
+  int n;
+  std::cin >> n;
+  int c = get_fibonacci_last_digit(n);
+  std::cout << c << '\n';
+}
diff --git a/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/01 b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/01
new file mode 100644
index 0000000..00750ed
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/01
@@ -0,0 +1 @@
+3
diff --git a/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/01.a b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/01.a
new file mode 100644
index 0000000..0cfbf08
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/01.a
@@ -0,0 +1 @@
+2
diff --git a/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/02 b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/02
new file mode 100644
index 0000000..67e1dac
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/02
@@ -0,0 +1 @@
+327305
diff --git a/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/02.a b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/02.a
new file mode 100644
index 0000000..7ed6ff8
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/02-fibonacci_last_digit/tests/02.a
@@ -0,0 +1 @@
+5
diff --git a/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp b/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp
new file mode 100644
index 0000000..f723be2
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/03-gcd/gcd.cpp
@@ -0,0 +1,21 @@
+#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;
+      }
+    }
+  }
+  return current_gcd;
+}
+
+int main() {
+  int a, b;
+  std::cin >> a >> b;
+  std::cout << gcd(a, b) << std::endl;
+  return 0;
+}
diff --git a/01-algorithmic_toolbox/01-intro/03-gcd/tests/01 b/01-algorithmic_toolbox/01-intro/03-gcd/tests/01
new file mode 100644
index 0000000..46ce05e
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/03-gcd/tests/01
@@ -0,0 +1 @@
+18 35
diff --git a/01-algorithmic_toolbox/01-intro/03-gcd/tests/01.a b/01-algorithmic_toolbox/01-intro/03-gcd/tests/01.a
new file mode 100644
index 0000000..d00491f
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/03-gcd/tests/01.a
@@ -0,0 +1 @@
+1
diff --git a/01-algorithmic_toolbox/01-intro/03-gcd/tests/02 b/01-algorithmic_toolbox/01-intro/03-gcd/tests/02
new file mode 100644
index 0000000..4154bdb
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/03-gcd/tests/02
@@ -0,0 +1 @@
+28851538 1183019
diff --git a/01-algorithmic_toolbox/01-intro/03-gcd/tests/02.a b/01-algorithmic_toolbox/01-intro/03-gcd/tests/02.a
new file mode 100644
index 0000000..855d3af
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/03-gcd/tests/02.a
@@ -0,0 +1 @@
+17657
diff --git a/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp b/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp
new file mode 100644
index 0000000..c6f503c
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/04-lcm/lcm.cpp
@@ -0,0 +1,13 @@
+#include <iostream>
+
+long long lcm(int a, int b) {
+  //write your code here
+  return a*b;
+}
+
+int main() {
+  int a, b;
+  std::cin >> a >> b;
+  std::cout << lcm(a, b) << std::endl;
+  return 0;
+}
diff --git a/01-algorithmic_toolbox/01-intro/04-lcm/tests/01 b/01-algorithmic_toolbox/01-intro/04-lcm/tests/01
new file mode 100644
index 0000000..20a8108
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/04-lcm/tests/01
@@ -0,0 +1 @@
+6 8
diff --git a/01-algorithmic_toolbox/01-intro/04-lcm/tests/01.a b/01-algorithmic_toolbox/01-intro/04-lcm/tests/01.a
new file mode 100644
index 0000000..a45fd52
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/04-lcm/tests/01.a
@@ -0,0 +1 @@
+24
diff --git a/01-algorithmic_toolbox/01-intro/04-lcm/tests/02 b/01-algorithmic_toolbox/01-intro/04-lcm/tests/02
new file mode 100644
index 0000000..4154bdb
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/04-lcm/tests/02
@@ -0,0 +1 @@
+28851538 1183019
diff --git a/01-algorithmic_toolbox/01-intro/04-lcm/tests/02.a b/01-algorithmic_toolbox/01-intro/04-lcm/tests/02.a
new file mode 100644
index 0000000..4b84195
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/04-lcm/tests/02.a
@@ -0,0 +1 @@
+1933053046
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
new file mode 100644
index 0000000..db0c074
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp
@@ -0,0 +1,12 @@
+#include <iostream>
+
+long long get_fibonaccihuge(long long n, long long m) {
+  //write your code here
+  return 0;
+}
+
+int main() {
+    long long n, m;
+    std::cin >> n >> m;
+    std::cout << get_fibonaccihuge(n, m) << '\n';
+}
diff --git a/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/tests/01 b/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/tests/01
new file mode 100644
index 0000000..6f185a6
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/tests/01
@@ -0,0 +1 @@
+281621358815590 30524
diff --git a/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/tests/01.a b/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/tests/01.a
new file mode 100644
index 0000000..ebe3a24
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/05-fibonacci_huge/tests/01.a
@@ -0,0 +1 @@
+11963
diff --git a/01-algorithmic_toolbox/01-intro/check b/01-algorithmic_toolbox/01-intro/check
new file mode 100755
index 0000000..b73ff99
--- /dev/null
+++ b/01-algorithmic_toolbox/01-intro/check
@@ -0,0 +1,38 @@
+#! /bin/bash
+
+RESET="\033[0m"
+RED="\033[0;31m"
+GREEN="\033[0;32m"
+BROWN="\033[0;33m"
+
+BIN=/tmp/bin
+OUTA=/tmp/_outa
+OUTB=/tmp/_outb
+GPP_OPTS="-std=c++11 -O2"
+
+for path in $(find -name \*.cpp | sort); do
+    src=${path##*/}
+    dir=${path%/*}
+    echo -e "${RED}validate $BROWN$dir$RESET/$GREEN$src$RESET"
+    pushd $dir >/dev/null || exit 1
+    echo -e "   ${RED}compile $GREEN$src$RESET" && g++ $GPP_OPTS $src -o $BIN || exit 1
+    if [ -d tests ]; then
+        echo -e "   ${RED}check $GREEN$src$RESET"
+        for t in $(find ./tests -name "*[^a~]"|sort); do
+            if [ -f $t -a -f "$t.a" ]; then
+                cat $t | $BIN > $OUTA
+                cat $t.a > $OUTB
+                cmp $OUTA $OUTB >/dev/null
+                if [ $? -ne 0 ]; then
+                    echo -e "     $BROWN$t$RESET is ${RED}KO$RESET"
+                else
+                    echo -e "     $BROWN$t$RESET is ${GREEN}ok$RESET"
+                fi
+            fi
+        done
+    else
+        echo -e "   ${RED}no tests$RESET"
+    fi
+    popd > /dev/null
+done
+