2018q1 第 9 週測驗題

測驗 1

考慮以下程式碼:

#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

延伸問題:

1. 依據 IEEE 754 規範，解釋為何輸出如此;
2. 程式碼第 7 和第 8 行的 & *** & 做了什麼事？請參閱 C99/C11 規範並解釋;
3. 參考 Fast Exponentiation Algorithms，實作 Fixed-point arithmetic 版本的 pow 函式並驗證;

---

測驗 2

考慮到以下採用 Functional Programming 風格開發的 singly-linked list 程式:

#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

延伸題目:

1. 解釋上述程式碼的運作，並且透過修改和實驗，理解 functional programming (FP) 風格;
2. 比照 FP，改寫上述程式碼，實作出 quick sort，同樣不得配置 heap memory (也就是不得用 malloc/free);
3. 測試這樣的 integer list 和 non-intrusive linked list 的效能差異;