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/final/problem1.c | 33 +++++++++++ usth/ICT2.1/final/problem2.c | 127 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 160 insertions(+) create mode 100644 usth/ICT2.1/final/problem1.c create mode 100644 usth/ICT2.1/final/problem2.c (limited to 'usth/ICT2.1/final') diff --git a/usth/ICT2.1/final/problem1.c b/usth/ICT2.1/final/problem1.c new file mode 100644 index 0000000..dce5ca7 --- /dev/null +++ b/usth/ICT2.1/final/problem1.c @@ -0,0 +1,33 @@ +/* Read a natural number from stdin and print its divisors to stdout */ +#include + +/* Print all divisors of the given natural number n. */ +void print_divisors(int n, int i) +{ + if (i * i == n) + printf("%d\n", i); /* Θ(1) */ + if (i * i >= n) + return; /* Θ(1) */ + if (n % i == 0) + printf("%d\n%d\n", i, n / i); /* Θ(1) */ + print_divisors(n, i + 1); +} + +/* + * Complexity analysis: + * Let T(n, i) be the time complexity of print_divisors, it is obvious that + * T(n, i) = Θ(1) if i*i >= n + * T(n, i) = T(n, i + 1) + Θ(1) + * Thus T(n, 1) = sum(Θ(1) for i from 1 to ceil(sqrt(n))) = Θ(sqrt(n)) + * or the overall time complexity of the call from main is Θ(sqrt(n)) + * on all scenarios. + */ +int main() +{ + int n; + + scanf("%d", &n); + print_divisors(n, 1); + + return 0; +} diff --git a/usth/ICT2.1/final/problem2.c b/usth/ICT2.1/final/problem2.c new file mode 100644 index 0000000..1b3368d --- /dev/null +++ b/usth/ICT2.1/final/problem2.c @@ -0,0 +1,127 @@ +/* + * Read one natural number from stdin and print its prime factors to stdout + * The time complexity analysis of this program is commented in the source code + */ +#include +#include + +typedef struct list construct; +struct list { + void *car; + construct *cdr; +}; + +typedef struct { + construct *stack; +} stack; + +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; +} + +stack *mkstack() +{ + stack *s = malloc(sizeof(stack)); + s->stack = NULL; + return s; +} + +int stack_empty(stack *s) +{ + return s->stack == NULL; +} + +void stack_push(stack *s, void *item) +{ + s->stack = cons(item, s->stack); +} + +void *stack_top(stack *s) +{ + return car(s->stack); +} + +void *stack_pop(stack *s) +{ + void *first = car(s->stack); + construct *rest = cdr(s->stack); + free(s->stack); + s->stack = rest; + return first; +} + +int main() +{ + int n, m; /* Θ(1) */ + stack *s = mkstack(); /* Θ(1) */ + + scanf("%d", &n); /* Θ(1) */ + m = n; /* Θ(1) */ + /* + * Let P be the sequence of prime factors of n and l be length of P. + * Let T(n, 2) be the time complexity of this for loop. + * Consider the function T(n, i): + * T(n, i) = Θ(1) if i*i >= n + * T(n, i) = T(n, i + 1) + Θ(1) if n is not divisible by i (*) + * T(n, i) = T(n/i, i) + Θ(1) if n is divisible by i (**) + * + * If only the (*) recurrence occurs, it is the worst case and + * T(n, 2) = sum(Θ(1) for i from 2 to floor(sqrt(n))) = Θ(sqrt(n)) + * + * If only the (**) recurrence occurs, it is the best case where n + * is power of 2. For convenience, we define R(n) = T(n, 2) and get + * R(n) = 1R(n/2) + Θ(n^log2(1)) + * By the master theorem, + * R(n) = Θ(n^log2(1) lg(n)) = Θ(lg(n)). + * + * If both occurs (average case), I can imagine that there exist numbers + * n_0, n_1, etc. and m_0, m_1, etc. that + * T(n, 2) = sum(Θ(sqrt(n_i))) + sum(Θ(lg(m_i))) = Θ(sqrt(n)) + * I, however, fail to formulate a rigorous proof for this. + */ + for (int i = 2; i * i <= n; ++i) + while (n % i == 0) { + int *tmp = malloc(sizeof(int)); /* Θ(1) */ + *tmp = i; /* Θ(1) */ + stack_push(s, tmp); /* Θ(1) */ + n /= i; /* Θ(1) */ + } + if (n != 1) { + int *tmp = malloc(sizeof(int)); + *tmp = n; + stack_push(s, tmp); + } /* Θ(1) */ + + /* + * Since each iteration of the loop above produce at most one + * prime factor, the time complexity of the loop below is O(T(n, 2)). + */ + while (!stack_empty(s)) { + printf("%d * ", *(int *) stack_top(s)); /* Θ(1) */ + stack_pop(s); /* Θ(1) */ + } + /* Terrible hack, not even portable (depending on flush behavior) */ + printf("\b\b= %d\n", m); /* Θ(1) */ + + return 0; +} + +/* + * Conclusion on time complexity: + * Best case: Θ(lg(n)) + O(Θ(lg(n))) = Θ(lg(n)) + * Average case and worst case: Θ(sqrt(n)) + O(Θ(sqrt(n))) = Θ(sqrt(n)) + */ -- cgit 1.4.1