From a3dd2581ed4847670f81157091016c14ca18803d Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Tue, 14 Jan 2020 18:29:11 +0700 Subject: [usth/MATH2.3] Mathemate Discretely --- usth/MATH2.3/3/README.md | 76 ++++++++++++++++++++++++++++++++ usth/MATH2.3/3/[Ch_Trees]_Practical.pdf | Bin 0 -> 31503 bytes usth/MATH2.3/3/a.out | Bin 0 -> 18288 bytes usth/MATH2.3/3/binary-search-tree.c | 68 ++++++++++++++++++++++++++++ usth/MATH2.3/3/dc.cc | 43 ++++++++++++++++++ usth/MATH2.3/3/graph-is-tree.cc | 56 +++++++++++++++++++++++ usth/MATH2.3/3/st-dfs.cc | 44 ++++++++++++++++++ usth/MATH2.3/3/sum-set.cc | 44 ++++++++++++++++++ 8 files changed, 331 insertions(+) create mode 100644 usth/MATH2.3/3/README.md create mode 100644 usth/MATH2.3/3/[Ch_Trees]_Practical.pdf create mode 100755 usth/MATH2.3/3/a.out create mode 100644 usth/MATH2.3/3/binary-search-tree.c create mode 100644 usth/MATH2.3/3/dc.cc create mode 100644 usth/MATH2.3/3/graph-is-tree.cc create mode 100644 usth/MATH2.3/3/st-dfs.cc create mode 100644 usth/MATH2.3/3/sum-set.cc (limited to 'usth/MATH2.3/3') diff --git a/usth/MATH2.3/3/README.md b/usth/MATH2.3/3/README.md new file mode 100644 index 0000000..fed19eb --- /dev/null +++ b/usth/MATH2.3/3/README.md @@ -0,0 +1,76 @@ +# Trees +## Problem 1 +`graph-is-tree.cc` (C++17) take a natural numbers `n` and a `n`-by-`n` adjacent +matrix from stdin and print to stdout either yes or no depending on whether the +given graph is a tree or not, e.g. + +### Input + 3 + 0 1 0 + 1 0 1 + 0 1 0 + +### Output + yes + +## Problem 2 +`binary-search-tree.c` takes a natural number `n` and `n` integers from stdin +and print to stdout a horizontal binary search tree formed (naïvely) from the +given input, e.g. + +### Input + 7 + 34 45 21 65 12 546 23 + +### Output + 12 + 21 + 23 + 34 + 45 + 65 + 546 + +## Problem 3 +`dc.cc` takes from stdin a list of numbers and operator, each terminated by a +semi-colon and print to stdout the evaluation of the given postfix arithmetic +expression, e.g. + +### Input + 6.9;4.20;+;2;^;6.9;4;-;3;/;+; + +### Output + 124.177 + +## Problem 4 +`st-dfs.cc` (C++17) takes a natural number `n` and an `n`-by-`n` adjacent +matrix from stdin and print the edges on a spanning tree of the given graph to +stdout, e.g. + +### Input + 4 + 0 1 1 1 + 1 0 1 1 + 1 1 0 1 + 1 1 1 0 + +### Output + 2 3 + 0 3 + 1 2 + +## Problem 5 +`sum-set.cc` takes a natural number `n` and a line of positive integers on one +line from stdin and print numbers whose sum are `n`, separated by a newline, to +stdout, e.g. + +### Input + 7 + 1 2 3 4 5 6 7 8 9 + +### Output + 1 2 4 + 1 6 + 2 5 + 3 4 + 7 diff --git a/usth/MATH2.3/3/[Ch_Trees]_Practical.pdf b/usth/MATH2.3/3/[Ch_Trees]_Practical.pdf new file mode 100644 index 0000000..cd0bef4 Binary files /dev/null and b/usth/MATH2.3/3/[Ch_Trees]_Practical.pdf differ diff --git a/usth/MATH2.3/3/a.out b/usth/MATH2.3/3/a.out new file mode 100755 index 0000000..e3f63ce Binary files /dev/null and b/usth/MATH2.3/3/a.out differ diff --git a/usth/MATH2.3/3/binary-search-tree.c b/usth/MATH2.3/3/binary-search-tree.c new file mode 100644 index 0000000..725fa44 --- /dev/null +++ b/usth/MATH2.3/3/binary-search-tree.c @@ -0,0 +1,68 @@ +#include +#include + +#define MKTREE(entry, left, right) (cons((entry), cons((left), cons((right), NULL)))) +#define ENTRY(tree) (car((tree))) +#define LEFT(tree) (car(cdr((tree)))) +#define RIGHT(tree) (car(cdr(cdr((tree))))) + +typedef struct list construct; +struct list { + void *car; + construct *cdr; +}; + +construct *cons(void *first, construct *rest) +{ + construct *list = malloc(sizeof(construct)); + list->car = first; + list->cdr = rest; + return list; +} + +void *car(construct *list) +{ + return list->car; +} + +construct *cdr(construct *list) +{ + return list->cdr; +} + +construct *insert(void *a, construct *tree) +{ + if (tree == NULL) + return MKTREE(a, NULL, NULL); + if (*(int *) a < *(int *) ENTRY(tree)) + return MKTREE(ENTRY(tree), insert(a, LEFT(tree)), RIGHT(tree)); + return MKTREE(ENTRY(tree), LEFT(tree), insert(a, RIGHT(tree))); +} + +void display(construct *tree, size_t indent) +{ + if (tree == NULL) + return; + display(LEFT(tree), indent + 1); + for (size_t i = 0; i++ < indent; putchar(9)); + printf("%d", *(int *) ENTRY(tree)); + putchar(10); + display(RIGHT(tree), indent + 1); +} + +int main() +{ + size_t n; + scanf("%zu", &n); + + construct *tree = NULL; + while (n--) { + int *a = malloc(sizeof(int)); + scanf("%d", a); + tree = insert(a, tree); + } + + display(tree, 0); + + return 0; +} diff --git a/usth/MATH2.3/3/dc.cc b/usth/MATH2.3/3/dc.cc new file mode 100644 index 0000000..b69742a --- /dev/null +++ b/usth/MATH2.3/3/dc.cc @@ -0,0 +1,43 @@ +#include +#include +#include +#include +#include + +using namespace std; + +int +main () +{ + double num, x, y; + string op; + vector v; + + while (cin.peek () != '\n') + { + getline (cin, op, ';'); + stringstream s {op}; + s >> num; + if (s) + { + v.push_back (num); + continue; + } + + y = v.back (); + v.pop_back (); + x = v.back (); + v.pop_back (); + if (op == "^") + v.push_back (pow (x, y)); + else if (op == "+") + v.push_back (x + y); + else if (op == "-") + v.push_back (x - y); + else if (op == "*") + v.push_back (x * y); + else if (op == "/") + v.push_back (x / y); + } + cout << v.back () << endl; +} diff --git a/usth/MATH2.3/3/graph-is-tree.cc b/usth/MATH2.3/3/graph-is-tree.cc new file mode 100644 index 0000000..f79564d --- /dev/null +++ b/usth/MATH2.3/3/graph-is-tree.cc @@ -0,0 +1,56 @@ +#include +#include +#include +#include + +using namespace std; + +int +main () +{ + size_t n; + int b; + unordered_map> edges; + + int m = 0; + cin >> n; + for (size_t i = 0; i < n; ++i) + for (size_t j = 0; j < n; ++j) + { + cin >> b; + if (!b || i > j) + continue; + edges[i].insert (j); + edges[j].insert (i); + m++; + } + + if (n - m - 1) + { + cout << "no" << endl; + return 0; + } + + unordered_set s; + int count = -1; + for (auto const& [v, p] : edges) + { + if (s.count (v)) + continue; + count++; + vector lifo {v}; + while (!lifo.empty ()) + { + size_t u = lifo.back (); + lifo.pop_back (); + if (s.count (u)) + continue; + s.insert (u); + for (auto const& w : edges[u]) + if (!s.count (w)) + lifo.push_back (w); + } + } + + cout << (count ? "no" : "yes") << endl; +} diff --git a/usth/MATH2.3/3/st-dfs.cc b/usth/MATH2.3/3/st-dfs.cc new file mode 100644 index 0000000..89814dd --- /dev/null +++ b/usth/MATH2.3/3/st-dfs.cc @@ -0,0 +1,44 @@ +#include +#include + +using namespace std; + +void +dfs (unordered_map>& graph, + unordered_map& been, size_t current) +{ + been[current] = 1; + for (auto const& [i, b] : graph[current]) + if (b > 0) + if (been[i]) + graph[current][i] = graph[i][current] = 0; + else + { + graph[current][i] = graph[i][current] = -1; + dfs (graph, been, i); + } +} + +int +main () +{ + size_t n; + unordered_map> edges; + + cin >> n; + for (size_t i = 0; i < n; ++i) + for (size_t j = 0; j < n; ++j) + { + cin >> edges[i][j]; + edges[j][i] = edges[i][j]; + } + + unordered_map> st; + unordered_map been; + dfs (edges, been, 0); + + for (auto const& [i, m] : edges) + for (auto const& [j, b] : m) + if (b && i <= j) + cout << i << " " << j << endl; +} diff --git a/usth/MATH2.3/3/sum-set.cc b/usth/MATH2.3/3/sum-set.cc new file mode 100644 index 0000000..880fc6d --- /dev/null +++ b/usth/MATH2.3/3/sum-set.cc @@ -0,0 +1,44 @@ +#include +#include + +using namespace std; + +void +backtrack (vector& big, vector& smol, size_t& n, size_t index) +{ + size_t sum = 0; + for (auto const& i : smol) + sum += i; + if (sum == n) + { + for (auto const& i : smol) + cout << i << " "; + cout << endl; + } + else + for (size_t i = index; i < big.size (); ++i) + if (sum + big[i] <= n) + { + smol.push_back (big[i]); + backtrack (big, smol, n, i + 1); + smol.pop_back (); + } +} + +int +main () +{ + size_t n; + size_t tmp; + vector s; + + cin >> n; + for (size_t i = 0; i < n; ++i) + { + cin >> tmp; + s.push_back (tmp); + } + + vector r; + backtrack (s, r, n, 0); +} -- cgit 1.4.1