# 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 的效能差異;
:::