From bc75b20fc0e80d6037ee14e3dccc2d88823f5f2f Mon Sep 17 00:00:00 2001
From: Jérémy Zurcher <jeremy@asynk.ch>
Date: Sun, 13 Nov 2016 21:18:32 +0100
Subject: Algorithms : add 01-algorithmic_toolbox 04-dynamic_programming

---
 .../primitive_calculator.cpp                       | 31 ++++++++++++++++++++++
 .../01-primitive_calculator/tests/01               |  1 +
 .../01-primitive_calculator/tests/01.a             |  2 ++
 .../01-primitive_calculator/tests/02               |  1 +
 .../01-primitive_calculator/tests/02.a             |  2 ++
 .../01-primitive_calculator/tests/03               |  1 +
 .../01-primitive_calculator/tests/03.a             |  2 ++
 7 files changed, 40 insertions(+)
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03
 create mode 100644 01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a

(limited to '01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator')

diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
new file mode 100644
index 0000000..0131b53
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
@@ -0,0 +1,31 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+using std::vector;
+
+vector<int> optimal_sequence(int n) {
+  std::vector<int> sequence;
+  while (n >= 1) {
+    sequence.push_back(n);
+    if (n % 3 == 0) {
+      n /= 3;
+    } else if (n % 2 == 0) {
+      n /= 2;
+    } else {
+      n = n - 1;
+    }
+  }
+  reverse(sequence.begin(), sequence.end());
+  return sequence;
+}
+
+int main() {
+  int n;
+  std::cin >> n;
+  vector<int> sequence = optimal_sequence(n);
+  std::cout << sequence.size() - 1 << std::endl;
+  for (size_t i = 0; i < sequence.size(); ++i) {
+    std::cout << sequence[i] << " ";
+  }
+}
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01
new file mode 100644
index 0000000..d00491f
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01
@@ -0,0 +1 @@
+1
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a
new file mode 100644
index 0000000..2734518
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a
@@ -0,0 +1,2 @@
+0
+1 
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02
new file mode 100644
index 0000000..7ed6ff8
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02
@@ -0,0 +1 @@
+5
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a
new file mode 100644
index 0000000..fc544c9
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a
@@ -0,0 +1,2 @@
+3
+1 2 4 5 
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03
new file mode 100644
index 0000000..c18d157
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03
@@ -0,0 +1 @@
+96234
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a
new file mode 100644
index 0000000..55a1c62
--- /dev/null
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a
@@ -0,0 +1,2 @@
+14
+1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234 
-- 
cgit v1.2.3