From 0887d8f96950a060a122e14ed2981182ff1eb37d Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sat, 28 Dec 2019 21:16:58 +0700 Subject: [usth/ICT2.1] Algorithm and Data Structures --- usth/ICT2.1/labwork/4/Bonus.c | 26 +++++++++++++++++++++ usth/ICT2.1/labwork/4/Ex1.c | 25 +++++++++++++++++++++ usth/ICT2.1/labwork/4/Ex2.c | 46 ++++++++++++++++++++++++++++++++++++++ usth/ICT2.1/labwork/4/Ex3.c | 32 ++++++++++++++++++++++++++ usth/ICT2.1/labwork/4/Ex4.c | 34 ++++++++++++++++++++++++++++ usth/ICT2.1/labwork/4/README.md | 46 ++++++++++++++++++++++++++++++++++++++ usth/ICT2.1/labwork/4/TT4.pdf | Bin 0 -> 371084 bytes usth/ICT2.1/labwork/4/construct.c | 26 +++++++++++++++++++++ usth/ICT2.1/labwork/4/construct.h | 14 ++++++++++++ 9 files changed, 249 insertions(+) create mode 100644 usth/ICT2.1/labwork/4/Bonus.c create mode 100644 usth/ICT2.1/labwork/4/Ex1.c create mode 100644 usth/ICT2.1/labwork/4/Ex2.c create mode 100644 usth/ICT2.1/labwork/4/Ex3.c create mode 100644 usth/ICT2.1/labwork/4/Ex4.c create mode 100644 usth/ICT2.1/labwork/4/README.md create mode 100644 usth/ICT2.1/labwork/4/TT4.pdf create mode 100644 usth/ICT2.1/labwork/4/construct.c create mode 100644 usth/ICT2.1/labwork/4/construct.h (limited to 'usth/ICT2.1/labwork/4') diff --git a/usth/ICT2.1/labwork/4/Bonus.c b/usth/ICT2.1/labwork/4/Bonus.c new file mode 100644 index 0000000..b46b3fe --- /dev/null +++ b/usth/ICT2.1/labwork/4/Bonus.c @@ -0,0 +1,26 @@ +/* + * Solve Towers of Hà Nội of height n, where towers are named foo, bar and baz. + * This is free and unencumbered software released into the public domain. + */ + +#include + +void anoi(unsigned n, char *one, char *other, char *another) +{ + if (n == 0) + return; + + anoi(n - 1, one, another, other); + printf("Move from %s to %s\n", one, other); + anoi(n - 1, another, other, one); +} + +int main() +{ + unsigned n; + + scanf("%u", &n); + anoi(n, "foo", "bar", "baz"); + + return 0; +} diff --git a/usth/ICT2.1/labwork/4/Ex1.c b/usth/ICT2.1/labwork/4/Ex1.c new file mode 100644 index 0000000..4d0ab5d --- /dev/null +++ b/usth/ICT2.1/labwork/4/Ex1.c @@ -0,0 +1,25 @@ +/* + * Multiply two natural numbers from stdin and print the result to stdout. + * This is free and unencumbered software released into the public domain. + */ + +#include + +int multiply(int a, int b) +{ + if (a > 0) + return multiply(a - 1, b) + b; + if (a < 0) + return multiply(a + 1, b) - b; + return 0; +} + +int main() +{ + int a, b; + + scanf("%d %d", &a, &b); + printf("%d\n", multiply(a, b)); + + return 0; +} diff --git a/usth/ICT2.1/labwork/4/Ex2.c b/usth/ICT2.1/labwork/4/Ex2.c new file mode 100644 index 0000000..6ad6b87 --- /dev/null +++ b/usth/ICT2.1/labwork/4/Ex2.c @@ -0,0 +1,46 @@ +/* + * Read n from stdin and print all primes from 1 to n to stdout. + * This is free and unencumbered software released into the public domain. + */ + +#include +#include + +void subsieve(int *mask, int n, int i, int j) +{ + if (j > n) + return; + mask[j] = 1; + subsieve(mask, n, i, i + j); +} + +void sieve(int *mask, int n, int i) +{ + if (i * i > n) + return; + if (!mask[i]) + subsieve(mask, n, i, i + i); + sieve(mask, n, i + 1); +} + +void print_primes(int *mask, int n) +{ + if (!n) + return; + if (!mask[n]) + printf("%d\n", n); + print_primes(mask, n - 1); +} + +int main() +{ + int n; + scanf("%d", &n); + + int *notprime = calloc(n + 1, sizeof(int)); + notprime[0] = notprime[1] = 1; + sieve(notprime, n, 2); + print_primes(notprime, n); + + return 0; +} diff --git a/usth/ICT2.1/labwork/4/Ex3.c b/usth/ICT2.1/labwork/4/Ex3.c new file mode 100644 index 0000000..ba016fc --- /dev/null +++ b/usth/ICT2.1/labwork/4/Ex3.c @@ -0,0 +1,32 @@ +/* + * Read numbers from stdin to a link list and print their sum to stdout. + * This is free and unencumbered software released into the public domain. + */ + +#include +#include + +#include "construct.h" + +construct *readoubles() +{ + double *x = malloc(sizeof(double)); + if (scanf("%lf", x) != EOF) + return cons(x, readoubles()); + free(x); + return NULL; +} + +double sum(construct *list) +{ + if (list == NULL) + return 0.0; + /* At program termination the memory will be freed anyway. */ + return *(double *) car(list) + sum(cdr(list)); +} + +int main() +{ + printf("%g\n", sum(readoubles())); + return 0; +} diff --git a/usth/ICT2.1/labwork/4/Ex4.c b/usth/ICT2.1/labwork/4/Ex4.c new file mode 100644 index 0000000..86eaabb --- /dev/null +++ b/usth/ICT2.1/labwork/4/Ex4.c @@ -0,0 +1,34 @@ +/* + * Exchange money from stdin to least number of 1, 2, 5, 10, 20 and 50 bills. + * This is free and unencumbered software released into the public domain. + */ + +#include + +struct change { + unsigned amount, bill; +}; + +const unsigned BILLS[] = {50, 20, 10, 5, 2, 1, 0}; + +void print_exchange(unsigned money, const unsigned *bills) +{ + if (!*bills) + return; + if (*bills > money) { + print_exchange(money, bills + 1); + return; + } + printf("%u %u\n", money / *bills, *bills); + print_exchange(money % *bills, bills + 1); +} + +int main() +{ + unsigned n; + + scanf("%u", &n); + print_exchange(n, BILLS); + + return 0; +} diff --git a/usth/ICT2.1/labwork/4/README.md b/usth/ICT2.1/labwork/4/README.md new file mode 100644 index 0000000..a7d0eee --- /dev/null +++ b/usth/ICT2.1/labwork/4/README.md @@ -0,0 +1,46 @@ +# Algorithms and Data Structures: Tutorial 4 + +This package contains the following files: + +* `construct.h`, `construct.c`: Lisp construct (with `cons`, `car` and `cdr`) +* `Ex1.c`: take 2 integers from stdin and print there product to stdout +* `Ex2.c`: print all primes in 1..n to stdout with n from stdin +* `Ex3.c`: print to stdout the sum of elements from stdin +* `Ex4.c`: exchange given amount of money from stdin to least number + of [1 2 5 10 20 50] bills and print the pairs of (amount, bill) to stdout +* `Bonus.c`: Towers of Hà Nội problem: no link list or stack needed + +Compilation can be done as follows + + cc Ex1.c -o Ex1 + cc Ex2.c -o Ex2 + cc construct.c Ex3.c -o Ex3 + cc Ex4.c -o Ex4 + cc Bonus.c -o Bonus + +All source files are as licensed under the Unlicense which states + +> This is free and unencumbered software released into the public domain. +> +> Anyone is free to copy, modify, publish, use, compile, sell, or +> distribute this software, either in source code form or as a compiled +> binary, for any purpose, commercial or non-commercial, and by any +> means. +> +> In jurisdictions that recognize copyright laws, the author or authors +> of this software dedicate any and all copyright interest in the +> software to the public domain. We make this dedication for the benefit +> of the public at large and to the detriment of our heirs and +> successors. We intend this dedication to be an overt act of +> relinquishment in perpetuity of all present and future rights to this +> software under copyright law. +> +> THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +> EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +> MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +> IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR +> OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, +> ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +> OTHER DEALINGS IN THE SOFTWARE. +> +> For more information, please refer to diff --git a/usth/ICT2.1/labwork/4/TT4.pdf b/usth/ICT2.1/labwork/4/TT4.pdf new file mode 100644 index 0000000..630172e Binary files /dev/null and b/usth/ICT2.1/labwork/4/TT4.pdf differ diff --git a/usth/ICT2.1/labwork/4/construct.c b/usth/ICT2.1/labwork/4/construct.c new file mode 100644 index 0000000..887b6d8 --- /dev/null +++ b/usth/ICT2.1/labwork/4/construct.c @@ -0,0 +1,26 @@ +/* + * Lisp construct implementation. + * This is free and unencumbered software released into the public domain. + */ + +#include + +#include "construct.h" + +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; +} diff --git a/usth/ICT2.1/labwork/4/construct.h b/usth/ICT2.1/labwork/4/construct.h new file mode 100644 index 0000000..35d2448 --- /dev/null +++ b/usth/ICT2.1/labwork/4/construct.h @@ -0,0 +1,14 @@ +/* + * Lisp construct header. + * This is free and unencumbered software released into the public domain. + */ + +typedef struct list construct; +struct list { + void *car; + construct *cdr; +}; + +construct *cons(void *, construct *); +void *car(construct *); +construct *cdr(construct *); -- cgit 1.4.1