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/4/README.md | 71 ++++++++++++++++++++++++++++++ usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf | Bin 0 -> 34287 bytes usth/MATH2.3/4/deg3.c | 18 ++++++++ usth/MATH2.3/4/k-map.c | 16 +++++++ usth/MATH2.3/4/sum-of-products.c | 25 +++++++++++ usth/MATH2.3/4/sum.c | 26 +++++++++++ usth/MATH2.3/4/threshold.c | 23 ++++++++++ 7 files changed, 179 insertions(+) create mode 100644 usth/MATH2.3/4/README.md create mode 100644 usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf create mode 100644 usth/MATH2.3/4/deg3.c create mode 100644 usth/MATH2.3/4/k-map.c create mode 100644 usth/MATH2.3/4/sum-of-products.c create mode 100644 usth/MATH2.3/4/sum.c create mode 100644 usth/MATH2.3/4/threshold.c (limited to 'usth/MATH2.3/4') diff --git a/usth/MATH2.3/4/README.md b/usth/MATH2.3/4/README.md new file mode 100644 index 0000000..880dacf --- /dev/null +++ b/usth/MATH2.3/4/README.md @@ -0,0 +1,71 @@ +# Booleans +## Problem 1 +`deg3.c` prints the a table listing the set of values of all 256 Boolean +functions of degree three to stdout. + +## Problem 2 +`sum-of-products.c` takes 2 natural numbers `n` and `f` from stdin, where `f` +is the encoded truth table of a Boolean function of degree `n`, for example, + +| x0 | x1 | value | +| :---: | :---: | :---: | +| 0 | 0 | 1 | +| 0 | 1 | 0 | +| 1 | 0 | 1 | +| 1 | 1 | 0 | + +will be encoded as `0b0101 = 5`. The program then print the bitwise arithmetic +sum-of-products expression to stdout, e.g. + +### Input + 2 5 + +### Output + ~x0&~x1 | ~x0&x1 + +## Problem 3 +`k-map`, e.g. + +### Input + 0 0 0 1 + 0 0 1 0 + 0 1 0 1 + 1 0 0 0 + 1 1 1 0 + 0 1 1 0 + 1 1 0 1 + 1 0 1 0 + +### Output + 00 01 10 11 + 0 1 0 1 1 + 0 0 0 0 0 + +## Problem 4 +`threshold.c` takes in natural number `n`, a real threshold value `t` and `n` +weights, then `n` boolean values from stdin and print to stdout the output of +the given threshold gate, e.g. + +### Input + 7 0.25051534245890184 + 0.11609819805105248 + 0.7924365005827357 + 0.9835187780201641 + 0.4235209817923591 + 0.08303890030044114 + 0.7196176517110272 + 0.988645113198539 + 1 1 0 1 1 0 1 + +### Output + 1 + +## Problem 5 +`sum.c` takes similar input format from stdin and print the bitwise arithmetic +expression using only bit flip (`~`) and addition (`|`) to stdout, e.g. + +### Input + 3 69 + +### Output + ~(~x0 | x1 | x2) | ~(~x0 | ~x1 | x2) | ~(~x0 | ~x1 | ~x2) diff --git a/usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf b/usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf new file mode 100644 index 0000000..fd3680e Binary files /dev/null and b/usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf differ diff --git a/usth/MATH2.3/4/deg3.c b/usth/MATH2.3/4/deg3.c new file mode 100644 index 0000000..a4f5726 --- /dev/null +++ b/usth/MATH2.3/4/deg3.c @@ -0,0 +1,18 @@ +#include + +int main() +{ + printf("(x y z)"); + for (int i = 0; i < 8; ++i) + printf("\t(%d %d %d)", i & 4 && 1, i & 2 && 1, i & 1 && 1); + putchar(10); + + for (int i = 0; i < 256; ++i) { + printf("f%02x", i); + for (int j = 0; j < 8; ++j) + printf("\t%d", i & 1 << j && 1); + putchar(10); + } + + return 0; +} diff --git a/usth/MATH2.3/4/k-map.c b/usth/MATH2.3/4/k-map.c new file mode 100644 index 0000000..ef19b80 --- /dev/null +++ b/usth/MATH2.3/4/k-map.c @@ -0,0 +1,16 @@ +#include + +int main() +{ + int x, y, z, f[8]; + + for (int i = 0; i < 8; ++i) { + scanf("%d %d %d", &x, &y, &z); + scanf("%d", f + x + (y << 1) + (z << 2)); + } + + printf("\t00\t01\t10\t11\n0\t%d\t%d\t%d\t%d\n0\t%d\t%d\t%d\t%d\n", + f[0], f[1], f[2], f[3], f[4], f[5], f[6], f[7]); + + return 0; +} diff --git a/usth/MATH2.3/4/sum-of-products.c b/usth/MATH2.3/4/sum-of-products.c new file mode 100644 index 0000000..3fac72b --- /dev/null +++ b/usth/MATH2.3/4/sum-of-products.c @@ -0,0 +1,25 @@ +#include + +int main() +{ + size_t n, f; + int b = 0; + + scanf("%zu %zu", &n, &f); + for (size_t i = 0; !(i >> n); ++i) { + if (!(f & 1 << i)) + continue; + if (b) + printf(" | "); + b = 1; + printf(i & 1 ? "x0" : "~x0"); + for (size_t j = 1; j < n; ++j) + if (i & 1 << j) + printf("&x%zu", j); + else + printf("&~x%zu", j); + } + putchar(10); + + return 0; +} diff --git a/usth/MATH2.3/4/sum.c b/usth/MATH2.3/4/sum.c new file mode 100644 index 0000000..8fd28f3 --- /dev/null +++ b/usth/MATH2.3/4/sum.c @@ -0,0 +1,26 @@ +#include + +int main() +{ + size_t n, f; + int b = 0; + + scanf("%zu %zu", &n, &f); + for (size_t i = 0; !(i >> n); ++i) { + if (!(f & 1 << i)) + continue; + if (b) + printf(" | "); + b = 1; + printf(i & 1 ? "~(x0" : "~(~x0"); + for (size_t j = 1; j < n; ++j) + if (i & 1 << j) + printf(" | ~x%zu", j); + else + printf(" | x%zu", j); + putchar(41); + } + putchar(10); + + return 0; +} diff --git a/usth/MATH2.3/4/threshold.c b/usth/MATH2.3/4/threshold.c new file mode 100644 index 0000000..5c39b3c --- /dev/null +++ b/usth/MATH2.3/4/threshold.c @@ -0,0 +1,23 @@ +#include +#include + +int main() +{ + size_t n; + scanf("%zu", &n); + + double t, *weights = malloc(n * sizeof(double)); + scanf("%lf", &t); + for (size_t i = 0; i < n; ++i) + scanf("%lf", weights + i); + + int tmp; + for (size_t i = 0; i < n; ++i) { + scanf("%d", &tmp); + t -= tmp && weights[i]; + } + + putchar((t <= 0) + 48); + putchar(10); + return 0; +} -- cgit 1.4.1