# 2018q1 第 9 週測驗題 ### 測驗 1 考慮以下程式碼: clike= #include <math.h> #include <stdio.h> double powDoubleFloat(double base, float power) { return pow(base, power); } int main() { double (*powFloatDouble)(float, double) = (double (*)(float, double)) & *** & powDoubleFloat; printf("(0.99)^100: %lf \n", powDoubleFloat(0.99, 100)); printf("(100)^0.99: %lf \n", powFloatDouble(100, 0.99)); printf("(0.99)^100: %lf \n", powFloatDouble(0.99, 100)); return 0; }  已知程式輸出的第一行為 (0.99)^100: 0.366032，第二行和第三行輸出分別是 (100)^0.99: X1 與 (0.99)^100: X2，依據 IEEE 754 規範，求 X1 和 X2 的值。 X1 = ? * (a) 99.000000 * (b) 95.499258 * (c) 1.000000 * (d) 0.000000 * (e) -1.000000 X2 = ? * (a) 1.000000 * (b) 0.366032 * (c) 0.133979 * (d) 0.000000 * (e) -1.000000 :::success 延伸問題: 1. 依據 IEEE 754 規範，解釋為何輸出如此; 2. 程式碼第 7 和第 8 行的 & *** & 做了什麼事？請參閱 C99/C11 規範並解釋; 3. 參考 [Fast Exponentiation Algorithms](http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/fastexp.pdf)，實作 [Fixed-point arithmetic](https://en.wikipedia.org/wiki/Fixed-point_arithmetic) 版本的 pow 函式並驗證; ::: --- ### 測驗 2 考慮到以下採用 [Functional Programming](https://en.wikipedia.org/wiki/Functional_programming) 風格開發的 singly-linked list 程式: Clike #include <stdint.h> #include <stdio.h> #include <stdlib.h> /* integer linked list type */ typedef struct __int_list const *const int_list_t; static int_list_t const Nil = NULL; /* empty list */ /* singly linked list element */ typedef struct __int_list { int_list_t next; int32_t const val; } node_t; /* A pointer to where we are about to store the result of computation */ typedef void *const CPS_Result; /* prototypes for the continuations */ typedef void (*MakeListCallback)(int_list_t list, CPS_Result res); void make_list(uint32_t const arr_size, int32_t const array[], int_list_t lst, MakeListCallback const cb, CPS_Result res); typedef void (*ReversedListCallback)(int_list_t rlist, CPS_Result res); void reverse(int_list_t list, int_list_t rlist, ReversedListCallback const cb, CPS_Result res); typedef void (*VoidMappable)(int32_t const val); void void_map_array(VoidMappable const cb, uint32_t const size, int32_t const *const arr); void list2array(int_list_t list, CPS_Result res); /* reverse a list and then store it in an array */ void reverse_toarray(int_list_t list, CPS_Result res) { reverse(list, Nil, list2array, res); } static void print_val(int32_t const val) { printf("%d ", val); } #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0])) int main(int argc, char *argv[]) { int32_t arr[] = {99, 95, 90, 85, 80, 20, 75, 15, 10, 5}; uint32_t const arr_size = ARRAY_SIZE(arr); int32_t res[arr_size]; /* call make_list and pass reverse_toarray as the "continuation" */ make_list(arr_size, arr, Nil, reverse_toarray, res); /* print out the reversed array */ void_map_array(print_val, arr_size, res); printf("\n"); return 0; } /* construct a linked list from an array */ void make_list(uint32_t const arr_size, int32_t const arr[], int_list_t lst, MakeListCallback const cb, CPS_Result res) { if (!arr_size) { cb(lst, res); return; } make_list(arr_size - 1, arr, &(node_t){.val = arr[arr_size - 1], .next = lst}, cb, res); } /* transform a linked list into an array */ void list2array(int_list_t list, CPS_Result res) { if (Nil == list) return; int32_t *array = res; array[0] = list->val; list2array(list->next, array + 1); } void reverse(int_list_t list, int_list_t rlist, /* reversed list */ ReversedListCallback const cb, CPS_Result res) { if (Nil == list) { cb(rlist, res); return; } reverse(list->next, &(node_t) K1, cb, res); } /* iterate over an array and performs action cb on each element */ void void_map_array(VoidMappable const cb, uint32_t const size, int32_t const *const arr) { if (!size) return; cb(arr[0]); void_map_array(cb, K2, K3); }  程式輸出為 5 10 15 75 20 80 85 90 95 99，也就是將輸入的數值順序予以反轉，過程中不需要 malloc/free，請補完上述程式碼。 K1 = ? * (a) {.val = list->val, .next = list} * (b) {.val = list->val, .next = rlist} * (c) {.val = rlist->val, .next = list} * (d) {.val = rlist->val, .next = rlist} K2 = ? * (a) size - 1 * (b) size * (c) size + 1 K3 = ? * (a) arr - 1 * (b) arr * (c) arr + 1 :::success 延伸題目: 1. 解釋上述程式碼的運作，並且透過修改和實驗，理解 functional programming (FP) 風格; 2. 比照 FP，改寫上述程式碼，實作出 quick sort，同樣不得配置 heap memory (也就是不得用 malloc/free); 3. 測試這樣的 integer list 和 non-intrusive linked list 的效能差異; :::