# 2020 年秋季「進階電腦系統理論與實作」課程專題 (quiz7) contributed by < `erickuo5124` > ###### tags: `2020進階電腦系統理論與實作` > [題目描述](https://hackmd.io/@sysprog/2020-quiz7) ### 測驗`1` #### T = ? `(c)`僅 funcB 是 Tail recursion > Tail Call > In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail-recursive, which is a special case of direct recursion. funcA 的回傳值除了 funcA 本身之外還要另外做 *5 ,因此不是 Tail recursion #### 實驗 --- ### 測驗`2` #### Q = ? `(b)`編譯器一定可施加 TCO 函式 `f` 的區域變數 `x` 在返回後就不再存在於 stack,但全域變數 `global_var` 在程式執行時會一值存在,並指向原先 `x` 的位置,因此可以施加 TCO #### 探討 TCO 和遞迴程式的原理 #### 分析上述實驗的行為和解釋 gcc 對 TCO 的操作 #### 從 GitHub 裡頭找出 __builtin_return_address 的應用案例並解說 --- ### 測驗`3` #### P = ? `(b)` 不影響,依然可產生符合預期的輸出 僅僅是左右哪邊先處理,不影響最後結果。 #### 解釋上述程式運作原理,並探討編譯器針對遞迴呼叫的最佳化空間 #### 用 iteration 改寫,並降低記憶體開銷,需要用 Valgrind 一類的分析工具驗證 ```c= struct TreeNode *invertTree_iteration(struct TreeNode *root) { if (!root) return NULL; if (!root->left && !root->right) return root; struct TreeNode *curr = root; struct TreeNode *tmp; while(1){ tmp = curr->left; curr->left = curr->right; curr->right = tmp; if(curr->left) curr = curr->left; else if(curr->right) curr = curr->right; else if(curr->parent) curr = curr->parent; else break; } return root; } ``` --- ### 測驗`4` #### MASK = ? `(a)` `~((1U << count) - 1)` [解題思路](https://hackmd.io/@Zero871015/LeetCode-201)給了我們一個想法: > 將頭尾取出,並將兩數從左至右一個 bit 一個 bit 比對,直到出現一個「不一樣的 bit」,把包含那個 bit 後面補 0 並輸出。 在題目中: - `m & n` 可以得到在那個「不一樣的 bit」之前的正確答案 - `MASK` 需要將包含那個「不一樣的 bit」之後的 bit 全部變成 0 - `diff` 兩數的差,可以透過 `__builtin_clz` 得到那個「不一樣的 bit」的位置 - `count` 得到要變 0 的個數 將 1 往左移 `count` 的數量後減 1 即可得到要變 0 的地方(但這時會是 1),對它做 NOT 即可得到 `MASK` #### 解釋上述程式運作原理,並探討改進的方式 #### 能否實作完全無分支 (branchless) 且滿足上述 LeetCode 要求的程式碼?請探討並實作 ```c= // runtime error: passing zero to clz(), which is not a valid argument int rangeBitwiseAnd(int m, int n) { int diff = n - m; int count = 32U - __builtin_clz(diff); return m & n & MASK; } ``` --- ### 測驗`5` #### RRR = ? `(b)` `i + j - 1` [解題思路](https://medium.com/@bill800227/leetcode-97-interleaving-string-18b1202fb0ea)中提到 > s1[i-1] == s3[i+j-1] : 這個代表我們可以取出s1當前的元素來形成s3的下一個元素,所以這時候我們的transfer formula就會變成: dp[i][j] = dp[i-1][j] && (s1[i-1] ==s3[i+j-1]) 可得知 `p` = `i + j - 1`
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up