diff options
5 files changed, 337 insertions, 43 deletions
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 index 0131b53..4ce529b 100644 --- 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 @@ -4,28 +4,128 @@ 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; +// How to express C(n) through C(n/3), C(n/2), C(n − 1):q + +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; + reverse(sequence.begin(), sequence.end()); + return sequence; +} + +#define NAN std::numeric_limits<int>::max() + +static inline int best(int a, int b, int c) +{ + int r = std::numeric_limits<int>::max(); + + if (c != 0 && c < r) + r = c; + if (b != 0 && b < r) + r = b; + /* if (a != 0 && a < r) */ + if (a < r) + r = a; + + return r; +} + +static inline int which(int a, int b, int c) +{ + int i = -1; + int r = std::numeric_limits<int>::max(); + + if (c != 0 && c < r) { + r = c; + i = 2; + } + if (b != 0 && b < r) { + r = b; + i = 1; + } + /* if (a != 0 && a < r) */ + if (a < r) + i = 0; + + return i; +} + +vector<int> jzu(int n) +{ + vector<int> solution; + + int N = n + 1; + int *add1 = new int[N]; + int *mult2 = new int[N]; + int *mult3 = new int[N]; + + add1[2] = mult2[2] = mult3[3] = 1; + add1[3] = 2; + /* std::cout << "0| " << add1[0] << " " << mult2[0] << " " << mult3[0] << std::endl; */ + /* std::cout << "1| " << add1[1] << " " << mult2[1] << " " << mult3[1] << std::endl; */ + /* std::cout << "2| " << add1[2] << " " << mult2[2] << " " << mult3[2] << std::endl; */ + /* std::cout << "3| " << add1[3] << " " << mult2[3] << " " << mult3[3] << std::endl; */ + + int c3 = 0; + bool even = true; + for (size_t i = 4, j = 3; i < N ; i++, j++) { + + add1[i] = best(add1[j], mult2[j], mult3[j]) + 1; + + if (even) { + int k = i >> 1; + mult2[i] = best(add1[k], mult2[k], mult3[k]) + 1; + } + + if (c3 == 2) { + int k = i / 3; + mult3[i] = best(add1[k], mult2[k], mult3[k]) + 1; + c3 = 0; + } else + c3++; + + even = !even; + /* std::cout << i << "| " << add1[i] << " " << mult2[i] << " " << mult3[i] << std::endl; */ + } + + while (n > 1) { + solution.push_back(n); + int op = which(add1[n], mult2[n], mult3[n]); + if (op == 0) { + n--; + } else if (op == 1) { + n /= 2; + } else + n /= 3; + } + solution.push_back(1); + + delete [] add1; + delete [] mult2; + delete [] mult3; + + return solution; } int main() { int n; std::cin >> n; - vector<int> sequence = optimal_sequence(n); + /* vector<int> sequence = optimal_sequence(n); */ + vector<int> sequence = jzu(n); std::cout << sequence.size() - 1 << std::endl; - for (size_t i = 0; i < sequence.size(); ++i) { + for (size_t i = sequence.size() - 1; i > 0; i--) { std::cout << sequence[i] << " "; } + std::cout << sequence[0] << " "; + std::cout << '\n'; } diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp index c284560..5782461 100644 --- a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp +++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp @@ -3,15 +3,43 @@ using std::vector; -int optimal_weight(int W, const vector<int> &w) { - //write your code here - int current_weight = 0; - for (size_t i = 0; i < w.size(); ++i) { - if (current_weight + w[i] <= W) { - current_weight += w[i]; +int optimal_weight(int W, const vector<int> &w) +{ + int I = w.size(); + int *m = new int[(W + 1) * (I + 1)]; + + int *current = &m[W + 2]; + int *not_taken = &m[1]; + + // each item + for (int i = 1; i <= I; i++) { + int wi = w[i - 1]; + for (int k = 1; k <= W; k++) { + if (k >= wi) { + int taken = *(not_taken - wi) + wi; + *current = ((taken > *not_taken) ? taken : *not_taken); + } else + *current = *not_taken; + + current++; + not_taken++; + } + // skip first column + current++; + not_taken++; } - } - return current_weight; + + /* for (int i = 0; i <= I; i++) { */ + /* for (int k = 0; k <= W; k++) */ + /* std::cout << m[(W +1) * i + k] << " "; */ + /* std::cout << std::endl; */ + /* } */ + + int ret = *(current - 2); + + delete [] m; + + return ret; } int main() { diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp index fd7d16e..8b124ed 100644 --- a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp +++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp @@ -3,9 +3,44 @@ using std::string; -int edit_distance(const string &str1, const string &str2) { - //write your code here - return 0; +int edit_distance(const string &str1, const string &str2) +{ + int s1 = str1.length() + 1; + int s2 = str2.length() + 1; + int *m = new int[s1 * s2]; + + for (int i = 0; i < s1; i++) m[i] = i; + for (int i = 0; i < s2; i++) m[i * s1] = i; + + for (int i = 1; i < s2; i++) { + for (int j = 1; j < s1; j++) { + int insertion = m[i * s1 + j - 1] + 1; + int deletion = m[(i - 1 ) * s1 + j] + 1; + int match = m[(i - 1) * s1 + j - 1]; + int mismatch = match + 1; + if (str2[i - 1] == str1[j - 1]) { + /* m[i, j] = ((insertion < deletion) ? */ + m[i * s1 + j] = ((insertion < deletion) ? + ((insertion < match) ? insertion : match) + : ((deletion < match) ? deletion : match)); + } + else { + m[i * s1 + j] = ((insertion < deletion) ? + ((insertion < mismatch) ? insertion : mismatch) + : ((deletion < mismatch) ? deletion : mismatch)); + } + } + } + + /* for (int i = 0; i < s2; i++) { */ + /* for (int j = 0; j < s1; j++) */ + /* std::cout << m[i * s1 + j] << " "; */ + /* std::cout << std::endl; */ + /* } */ + + delete [] m; + + return m[s1 * s2 - 1]; } int main() { diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp index 06861ab..8867a1e 100644 --- a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp +++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp @@ -2,27 +2,101 @@ #include <cassert> #include <string> #include <vector> +#include <limits> using std::vector; using std::string; using std::max; using std::min; -long long eval(long long a, long long b, char op) { - if (op == '*') { - return a * b; - } else if (op == '+') { - return a + b; - } else if (op == '-') { - return a - b; - } else { - assert(0); - } +long long eval(long long a, long long b, char op) +{ + if (op == '*') { + return a * b; + } else if (op == '+') { + return a + b; + } else if (op == '-') { + return a - b; + } else { + assert(0); + } } -long long get_maximum_value(const string &exp) { - //write your code here - return 0; +void get_min_max(int n, int x, int i, int j, const string &ops, long long *mins, long long *maxs) +{ + long long min = std::numeric_limits<long long>::max(); + long long max = std::numeric_limits<long long>::min(); + + for (int k = i; k < j; k++) { + int x = i * n + k; + int y = (k + 1) * n + j; + long long a = eval(maxs[x], maxs[y], ops[k]); + long long b = eval(maxs[x], mins[y], ops[k]); + long long c = eval(mins[x], mins[y], ops[k]); + long long d = eval(mins[x], maxs[y], ops[k]); + if (a < min) min = a; + if (b < min) min = b; + if (c < min) min = c; + if (d < min) min = d; + if (a > max) max = a; + if (b > max) max = b; + if (c > max) max = c; + if (d > max) max = d; + } + mins[x] = min; + maxs[x] = max; +} + +long long get_maximum_value(const string &exp) +{ + int n = (exp.length() + 1) / 2; + int nn = (n * n); + + string ops; + long long *mins = new long long[nn]; + long long *maxs = new long long[nn]; + + // collect the operators + for (int i = 1; i < exp.length(); i+=2) + ops += exp[i]; + + // feed both diagonals with operands + for (int i = 0, k = 0; i < nn; i+=(n + 1), k+=2) + maxs[i] = mins[i] = (exp[k] - '0'); + + // feed both first diagonals, result of pair + for (int i = 1, k = 1; i < nn; i+=(n + 1), k+=2) + maxs[i] = mins[i] = eval(mins[i - 1], mins[i + n], exp[k]); + + for (int i = 2, k = (n - 2); i < n; i++, k-=1) { + for (int j = 0; j < k; j++) { + int x = i + j * (n + 1); + /* maxs[x] = mins[x] = k; */ + /* std::cout << "[" << j <<";"<< j + i<<"]"<< std::endl; */ + get_min_max(n, x, j, j + i, ops, mins, maxs); + } + } + + /* std::cout << std::endl; */ + /* for (int i = 0; i < nn; i+=n) { */ + /* for (int j = 0; j < n; j++) */ + /* std::cout << mins[i + j] << " "; */ + /* std::cout << std::endl; */ + /* } */ + /* std::cout << std::endl; */ + /* for (int i = 0; i < nn; i+=n) { */ + /* for (int j = 0; j < n; j++) */ + /* std::cout << maxs[i + j] << " "; */ + /* std::cout << std::endl; */ + /* } */ + /* std::cout << std::endl; */ + + long long ret = maxs[n - 1]; + + delete [] mins; + delete [] maxs; + + return ret; } int main() { diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp index 2ca0339..473830f 100644 --- a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp +++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp @@ -1,11 +1,68 @@ #include <iostream> #include <vector> -using std::vector; +using namespace std; -int lcs3(vector<int> &a, vector<int> &b, vector<int> &c) { - //write your code here - return std::min(std::min(a.size(), b.size()), c.size()); +static inline int max(int a, int b, int c) { + if (a > b) + return (a > c ? a : c); + return (b > c ? b : c); +} + +static inline int max(int a, int b, int c, int d, int e, int f, int g) { + int abc = max(a, b, c); + int def = max(d, e, f); + return max(abc, def, g); +} + +int lcs3(vector<int> &a, vector<int> &b, vector<int> &c) +{ + vector<vector<vector<int> > > cost(a.size() + 1, + vector<vector<int> >(b.size() + 1, + vector<int>(c.size() + 1, 0))); + + int max_cost;; + for (int k = 1; k <= c.size(); k++) { + for (int j = 1; j <= b.size(); j++) { + for (int i = 1; i <= a.size(); i++) { + int c1 = cost[i - 1][j - 1][k - 1]; // -1 ; -1 ; -1 + int c2 = cost[i - 1][j - 1][k]; // -1 ; -1 ; 0 + int c3 = cost[i - 1][j][k - 1]; // -1 ; 0 ; -1 + + int c4 = cost[i][j - 1][k - 1]; // 0 ; -1 ; -1 + int c5 = cost[i - 1][j][k]; // -1 ; 0 ; 0 + int c6 = cost[i][j - 1][k]; // 0 ; -1 ; 0 + int c7 = cost[i][j][k - 1]; // 0 ; 0 ; -1 + + // (-1 ; -1 ; -1) + 1 + int c8_match = cost[i - 1][j - 1][k - 1] + 1; + + if (a[i - 1] == b[j - 1] && a[i - 1] == c[k - 1]) { +#if DEBUG + cout << "match " << a[i - 1] << " at (i, j, k) = " << i << "," << j << "," << k << endl; +#endif + max_cost = max(c8_match, c2, c3, c4, c5, c6, c7); + } else { + max_cost = max(c1, c2, c3, c4, c5, c6, c7); + } + cost[i][j][k] = max_cost; + } + } + } + +#if DEBUG + for (int k = 0; k <= c.size(); k++) { + cout << "======== k = " << k << " =========" << endl; + for (int j = 0; j <= b.size(); j++) { + for (int i = 0; i <= a.size(); i++) { + cout << cost[i][j][k] << " "; + } + cout << endl; + } + } +#endif + + return cost[a.size()][b.size()][c.size()]; } int main() { |