# 2020q3 Homework4 (quiz4) contributed by < `jonec76` > ###### tags: `sysprog-2020` > [作業說明](https://hackmd.io/@sysprog/r1z0WPWLD) > [題目](https://hackmd.io/@sysprog/2020-quiz4) ## 開發環境 ```shell $ uname -a Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux ``` ## 參考解答 OP = ^ AAA = int ** BBB = -1 CCC = 1 << i KK1 = div5 KK2 = div3 KK3 = 2 ## Q1 - 解題想法 ```c=1 int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); } ``` 可以先觀察一下圖上的點，如果兩點之間 bit 中只有 1 位不相同的話，那可以知道兩個點的距離只差 1。根據這個原則，只要找出兩個數字有多少個 bit 不同即可。 那如何找出呢？這邊可以使用 XOR 找出，因為 XOR 的特性剛好可以使不同 bit （`0^1`）出來的結果是 1，若是相同的話就會變成 0。 接著，再使用 `__builtin_popcount` 計算出有多少個 1，即可知道答案了。 ## Q2 - 解題方向 在解 AAA 時，可以從下方這行程式碼得出 ```c=1 obj->parent = malloc(n * sizeof(int *)); ``` 表示 `obj->parent` 是個具有 n 個 `int *` 的 pointer，如此即可知道應為 `int **` 型態。 在解 BBB 之前，可以先了解此題題目目的，參考下方程式碼 ```c=1 int max_level = 32 - __builtin_clz(n) + 1; for (int i = 0; i < n; i++) { obj->parent[i] = malloc(max_level * sizeof(int)); for (int j = 0; j < max_level; j++) obj->parent[i][j] = -1; } ``` 找出 `max_level` 的方法蠻有趣的，背後含義是做了 $\lfloor log\ n\rfloor$。一開始想說應該是想要找出 n 最大會在哪個 level，但是！之後再看一次題目才知道不是這樣子（需要配合 `treeAncestorGetKthAncestor` 來看） 這邊就是建立每個點的 parent table，用來記錄該點之上的 "幾個" parent（不是所有都紀錄！），並且對每個 node 的 parent table 做初始化。 ```c=1 for (int i = 0; i < parentSize; i++) obj->parent[i][0] = parent[i]; ``` 接著可以看到下方 BBB 的填空 ```c=1 for (int i = 0; i < parentSize; i++) { obj->parent[i][j] = obj->parent[i][j + BBB] == -1 ? -1 : obj->parent[obj->parent[i][j - 1]][j - 1]; if (obj->parent[i][j] != -1) quit = 0; } ``` 若是倒著推回來的話，可以先思考一下怎樣的情況，parent 會是 `-1`？ 同時，又可以看到需要根據該點之外的其他 parent ，來更新目前的 parent。此時就可以推測出，如果在 `j - 1` 已經是 `-1`，也就是沒有任何 node 在 `j - 1` 之上，那 `j` 一定也不會有 parent。 接著，看到最後 CCC 選項 ```c=1 int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k) { int max_level = obj->max_level; for (int i = 0; i < max_level && node != -1; ++i) if (k & (CCC)) node = obj->parent[node][i]; return node; } ``` 上述程式碼蠻有趣的，是要拿第 k 個 parent。當初看到此題時，想說就是 n 往上數到第 k 個 node 並且回傳。但事實上並非如此，以下圖為例子 ```graphviz digraph skew_BST { size="10,3!" node [fontname="Arial"]; 0 -> 1; 1 -> 2; 2 -> 3; 3 -> 4; 4 -> 5; 5 -> 6; } ``` 以例子來看，在 node 6 的 parent table 應為下圖，parent[i] 紀錄的是往上數第 $2^i$ 個點 ```graphviz digraph hash_table { nodesep = .05; rankdir = LR; node[shape = record, width = .1, height = .1]; node0[label = "<f9> 6", height = 0.5]; node [width = 1.5]; node9[label = "{ 5|4|2}"]; node0:f9 -> node9; } ``` why? 由下方程式碼可以看出 ```c=1 for (int j = 1;; j++) { int quit = 1; for (int i = 0; i < parentSize; i++) { obj->parent[i][j] = obj->parent[i][j + BBB] == -1 ? -1 : obj->parent[obj->parent[i][j - 1]][j - 1]; ``` 以 `parent[5][2]` (node 6) 來看，那就會被更新為 `parent[4][1]` (node 5)。 以 `parent[5][3]` (node 6) 來看，那就會被更新為 `parent[3][2]` (node 4)。 這樣的紀錄方法，將會使得 `parent[i]` 紀錄的是往上數第 $2^i$ 個點。對於這樣設計的原因，自己思考後是認為這樣的設計能夠處理 balanced tree，也能處理 skew tree，不需要因為 tree 的高度而變動 parent table size，反而只要知道 node 總數即可。 既然如此，再回到 CCC 選項。若 node=6, k=5 時，也就是要找出 node=6 往上數第 5 個的 node。這邊以 `treeAncestorGetKthAncestor` 來看，跑法會是 1. 取出 node 6 的第 $2^0$ parent，也就是 5 2. 5 再取出第 $2^2$ 點，也就是 0 打破原先那直觀的觀念（往上走 5 步），而是用走 "2 的冪次方" 的方法取點。 ## Q3 - 程式碼分析 ```c=1 if (i % 3 == 0) printf("Fizz"); if (i % 5 == 0) printf("Buzz"); if (i % 15 == 0) printf("FizzBuzz"); if ((i % 3) && (i % 5)) printf("%u", i); ``` 此題的原意其實很簡單，目的就是根據以上的程式碼印出。 接著此題希望使用 `strncpy` 的方式，來複製出原始字串的 substring。複製的參數是 1. start 字串的起始位置 2. 複製的長度 複製程式碼如下： ```c=1 #define MSG_LEN 8 char fmt[MSG_LEN + 1]; strncpy(fmt, &"FizzBuzz%u"[start], length); fmt[length] = '\0'; printf(fmt, i); printf("\n"); ``` - 解題想法 ```c=1 strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length); ``` 此題基本上就是要把數字湊出來，在 [quiz2-Q4](https://hackmd.io/@jonec76/2020q3-quiz2#Q4) 中分析過 `is_divisible` 的原理。所以可以知道此題的 `div3` 、 `div5` 就會表示出目前的數可否被相對 `3` 或 `5` 整除，可以的話就得 `1`，否則 `0`。 以下為 output 合併 `strncpy` 參數的 table： |value|output|start index|length| |---|---|---|---|---| |n 整除 3|"Fizz"|0|4| |n 整除 5|"Buzz"|4|4| |n 整除 15|"FizzBuzz"|0|8| |以上皆非|n|0|0| 湊了幾組後即可得到答案。 這邊在課堂上寫的時候發生了粗心的情況，順便記錄一下。當時把 `div3 << 2` 跟 `2 << div3` 寫相反，當 `div3=1` 時的確值是一樣，但是缺少考慮了 `div3=0` 的 case。