# 2023q1 Homework1 (quiz1) contributed by < `csm1735` > ## 測驗 `1` ```c if (list_empty(head) || list_is_singular(head)) return; ``` 在一開始我們首先檢查串列是否為空或只有一個節點，如果是的話則不需要排序，因此直接 ```return``` ```c struct list_head list_less, list_greater; INIT_LIST_HEAD(&list_less); INIT_LIST_HEAD(&list_greater); ``` 接著宣告了 ```list_less``` 和 ```list_greater``` ，並對其做初始化 ```c struct item *pivot = list_first_entry(head, AAA, BBB); list_del(&pivot->list); ``` 選擇第一個 entry 來做為 ```pivot``` ，並將其從原本的串列中刪除，我們可以看出 ```AAA``` 及 ```BBB``` 為 ```list_first_entry``` 所用到的兩個參數，而根據以下定義可知 ```AAA``` 為 struct 的型態， ```BBB``` 為成員的名稱。 ```c #define list_first_entry(head, type, member) \ list_entry((head)->next, type, member) ``` 因此 ```AAA``` = ```struct item``` ， ```BBB``` = ```list``` 。 ```c struct item *itm = NULL, *is = NULL; CCC (itm, is, head, list) { if (cmpint(&itm->i, &pivot->i) < 0) DDD (&itm->list, &list_less); else EEE (&itm->list, &list_greater); } ``` 這段可看出 ```CCC``` 功能為走訪所有的節點來做比較的動作並移動，且根據其傳入的參數可判斷 ```CCC``` = ```list_for_each_entry_safe``` ，這樣的選擇可以允許目前的節點被移走，對於比較動作完成後的移動有所幫助，也因此 ```DDD``` 跟 ```EEE``` 皆為用來移動的 ```list_move_tail``` ，將值小於 ```pivot``` 的節點移到 ```list_less``` ，反之則移動到 ```list_greater``` ，值得一提的是，考量到為了使得排序達到 stable 的目標，所以在這邊 ```DDD``` 跟 ```EEE``` 不能選擇用 ```list_move``` 。 ```c list_sort(&list_less); list_sort(&list_greater); list_add(&pivot->list, head); list_splice(&list_less, head); FFF(&list_greater, head); ``` 最後這邊，透過遞迴呼叫 ```list_sort``` 來將 ```list_less``` 和 ```list_greater``` 排序完成後，我們需要將```list_less``` 放在 ```pivot``` 之前，而```list_greater``` 放在 ```pivot``` 之後，所以 ```FFF``` 選擇使用 ```list_splice_tail``` ，這樣即完成排序。 --- ## 測驗 `2` ```c if (list_empty(head) || list_is_singular(head)) return; ``` 在一開始我們首先檢查串列是否為空或只有一個節點，如果是的話則不需要排序，因此直接 ```return``` ```c struct list_head stack[MAX_DEPTH]; for (int i = 0; i < MAX_DEPTH; i++) INIT_LIST_HEAD(&stack[i]); int top = -1; list_splice_init(head, &stack[++top]); ``` 宣告 stack ，並透過 ```INIT_LIST_HEAD``` 將其初始化，一開始先將 ```head``` 的節點全都移進 stack ```c struct list_head partition; INIT_LIST_HEAD(&partition); while (top >= 0) { INIT_LIST_HEAD(&partition); list_splice_init(&stack[top--], &partition); ``` 將 stack 中最頂端的 ```pop``` 出來放入 ```partition``` 中 ```c if (!list_empty(&partition) && !list_is_singular(&partition)) ``` 如果 ```partition``` 非空且不只一個節點則進行以下操作 ```c struct list_head list_less, list_greater; INIT_LIST_HEAD(&list_less); INIT_LIST_HEAD(&list_greater); struct item *pivot = list_first_entry(&partition, struct item, list); list_del(&pivot->list); INIT_LIST_HEAD(&pivot->list); ``` 這邊和測驗 1 類似，先宣告了 ```list_less``` 和 ```list_greater``` ，並對其做初始化，然後選擇 ```partition``` 中第一個 entry 來做為 ```pivot``` ，並將其從原本的串列中刪除。 ```c struct item *itm = NULL, *is = NULL; GGGG (itm, is, &partition, list) { list_del(&itm->list); if (cmpint(&itm->i, &pivot->i) < 0) list_move(&itm->list, &list_less); else list_move(&itm->list, &list_greater); } ``` 這段可看出 ```GGGG``` 功能為走訪所有的節點，且根據其傳入的參數可判斷 ```GGGG``` = ```list_for_each_entry_safe``` ，而這樣的選擇可以允許目前的節點被移走，對於比較判斷完成後的移動有所幫助，將值小於 ```pivot``` 的節點移到 ```list_less``` ，反之則移動到 ```list_greater``` 。 ```c HHHH (&pivot->list, &list_less); ``` 我們會希望將```list_less``` 放在 ```pivot``` 之前，因此這邊 ```HHHH``` 選擇 ```list_move_tail``` ，將 ```pivot``` 移動到 ```list_less``` 的尾端。 ```c if (!list_empty(&list_greater)) list_splice_tail(&list_greater, IIII); if (!list_empty(&list_less)) list_splice_tail(&list_less, JJJJ); ``` 這段則是針對非空的 ```list_greater``` 跟 ```list_less``` 做操作，由於尚未排序完成，我們是將其 push 進 stack 中，且為先推入大的 ```list_greater``` ，再推入小的 ```list_less``` 。 因此 ```IIII``` = ```JJJJ``` = ```&stack[++top]``` 。 ```c else { top++; list_splice_tail(&partition, &stack[top]); while (top >= 0 && list_is_singular(&stack[top])) { struct item *tmp = list_first_entry(&stack[top], struct item, list); list_del(&tmp->list); INIT_LIST_HEAD(KKKK); list_add_tail(&tmp->list, head); } } ``` 如果 ```partition``` 只有一個節點則先將其 ```push``` 到 stack中。 然後如果 top 大於等於 0 且 ```stack[top]``` 只有單個節點，將該節點做移除的動作並 ```INIT_LIST_HEAD``` 然後再從 stack 中 pop 掉，因此 ```KKKK``` = ```&stack[top--]``` 。 而被移除的節點則加入 ```head``` 的尾端。 由以上觀察可發現，越小的節點越會到 stack 的頂端，也因此被移除的節點會是尚未被排序的節點中最小的，而透過將被移除的節點加入 ```head``` 尾端的作法，等同於將節點由小到大加入尾端，因此全部加入完畢時也就是排序完成。 --- ## 測驗 `3`
Last changed by  
 
yozz
190

Read more

2023q1 Homework5 (assessment)

contributed by < csm1735 > 〈因為自動飲料機而延畢的那一年〉心得 一開始看到這篇文章的標題時，我感到有些疑惑。作者竟然選擇了延畢來做飲料機，這樣的決定是否真的值得呢？在閱讀文章時，我了解到作者為了這個專案承受了各種壓力。如果換做是我，恐怕沒有勇氣做出這樣的決定。但是，仔細想想，當我們還年輕、還是學生的時候，就應該勇於放手一搏，做自己真正想做且值得去做的事情。畢竟，這樣的經驗不是每個人都能擁有，值得珍惜。 其中令我印象深刻的一段是，作者去找 Jserv 聊聊後， Jserv 指出作者最大的問題在太害怕失敗了，我認為這是許多人都面臨的問題，包括我自己。每當我遇到困難時，我會因為害怕失敗而選擇逃避，只做自己有把握的事情，然而，這樣做會錯過許多變強的機會，最終還是在原地，停滯不前。 此外，在文章的最後，作者提到 「飲料機的程式愷宏是寫不出來的，之所以能在一個月內完成，是因為我在大學期間就寫過好幾個網站了。愷宏能和工廠溝通、設計出可用的零件，是因為他在大一就在跑工廠做東西了。紘銘能輕易的設計出飲料機的電路，是因為他曾花了很多時間在電子電路課上頭，做了很多習題，纏著教授把每個疑惑都搞懂才罷休。」

4/16/2023
2023q1 Homework3 (quiz3)

contributed by < csm1735 > 測驗 1 測驗 2 測驗 3 LFSR 的運作原理及案例 Linear feedback shift register (LFSR) 是指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器 static void lfsr(uint64_t *up) {

3/22/2023
2023q1 Homework3 (fibdrv)

contributed by < csm1735 > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual

3/18/2023
2023q1 Homework2 (quiz2)

contributed by < csm1735 > 測驗 1 解釋程式碼原理 此題關鍵在於找出最高位元的 1 ，並將從此位元到最低位元的所有位元 set 為 1 ，再透過對 x + 1 來使其進位成 2 的冪的值。 舉例來說 x 如果是 $(0010$ $1010)_2$ ，需要先 set 成 $(0011$ $1111)_2$ ，再透過 x + 1 成為 $(0100$ $0000)_2$ 而因 x 為 64 位元的 uint64_t ，故最多需要右移 63 個位元。 因此程式碼為:

3/5/2023
Read more from yozz
Published on HackMD