9 files changed, 249 insertions, 0 deletions
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 <stdio.h>
+
+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 <stdio.h>
+
+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 <stdio.h>
+#include <stdlib.h>
+
+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 <stdio.h>
+#include <stdlib.h>
+
+#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 <stdio.h>
+
+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 <http://unlicense.org/>
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
--- /dev/null
+++ b/usth/ICT2.1/labwork/4/TT4.pdf
Binary files differdiff --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 <stdlib.h>
+
+#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 *);