# 2018q1 Homework2 (assessment)
contributed by <`0922james0922`>
## 測驗題作答
### 第 1 周第 1 題
考慮以下程式碼

#include <stdlib.h>
    int isMultN(unsigned int n) 
    {
        int odd_c = 0, even_c = 0; /* variables to             
        count odd and even SET bits */
        if (n == 0)
            return 1;
        if (n == 1)
            return 0;
        // return true if difference is 0.
        // return false if the difference is not 0.
        while (n) 
        {
            if (n & 1)
            // odd bit is SET, increment odd_C
                odd_c++;
            n >>= 1;
            if (n & 1)
            // even bit is SET, increment even_c
                even_c++;
            n = n >> 1;
        }
        /* Recursive call till you get 0/1 */
        return(isMultN(abs(odd_c - even_c)));
    }

其作用為檢查一輸入整數是否為N的倍數，那麼N為多少？
(a) 13
(b) 11
(c) 7
(b) 5
(e) 3
(f) 2

:::success
延伸問題:
* 為甚麼上述程式碼可運作呢?
* 將N改為其他質數再改寫為對應的程式碼，一樣使用遞迴
:::

### 想法&思考
1. 一開始看到這段程式碼時，很直觀的就是在考遞迴，因此這時就要開始**分析**內容了，**我一開始不會看 function 內容是什麼**，先看 return 要丟回 function 裡的東西是啥東東，再搭配看終止條件，這就可以大概有個感覺知道這段遞迴想要做的事情。
2. 我有點忘記當時寫的時候有沒有註解，如果有註解當輔助當然是最好，但如果沒有註解也可以從宣告的變數名稱開始著手，看到有 `odd_c` 跟 `even_c` ，可想而知大概是在**統計奇數個數跟偶數個數**。
3. 接著看 function 裡最重要的 while 迴圈裡，判斷若跟1做 `&&` 的話成立就 `odd_c++` ，接著不管程不程力都要右移，右移完再判斷偶數位成立的話一樣 `even_c++` ，直到 n 變為0則return 偶數總數跟奇數總數的差
4. 若要讓遞迴 `return true` 的話就是偶數總數跟奇數總數要相等，目前學過判斷是否為某某數是用奇數位總合扣掉偶數位總合的也只有11的倍數的判斷

例:
12212112 是否為 11 的倍數？
奇數位總和 = 1+2+1+2 = 6
偶數位總和 = 1+2+1+2 = 6
(6-6) % 11 = 0 ---> 12212112 為 11的倍數

5. 但，這就是這題題目賤的地方，都已經看到右移的運算了，居然還用十進位去思考是白癡嗎?所以當時考試是做答錯的，可...可惡!!
6. 因此事後就將所有選項的二進位列出來

13 = 1101
11 = 1011
7  = 0111
5  = 0101
3  = 0011
2  = 0010

:::success
直接看二進位是不是覺得簡單多了呢~~
:::
7. 發現只有3是奇數位和跟偶數位和的差是為0，不過這也只是3是這樣，會剛好3的倍數都符合這樣的規矩嗎??
* 證明

假設有一個四位數abcd，它可以表示成以下形式：
abcd=1000a+100b+10c+d=999a+99b+9c+a+b+c+d
=9×(111a+11b+c) +a+b+c+d可以看出，
9×(111a+11b+c)必定能被3整除，所以判斷abcd能否被3整除，就看a+b+c+d能被3整除，
也就是看它各數位上的數字之和能否被3整除。

* 列舉

6  = 000110
9  = 001001
12 = 001100
15 = 001111

:::success
確實都剛好符和偶數位跟奇數位的和之差皆為0
:::
* Implement

#include <stdlib.h>
#include <stdio.h>
int isMultN(unsigned int n) 
{
        int odd_c = 0, even_c = 0; /* variables to             
        count odd and even SET bits */
        if (n == 0)
            return 1;
        if (n == 1)
            return 0;
        // return true if difference is 0.
        // return false if the difference is not 0.
        while (n) 
        {
            if (n & 1)
            // odd bit is SET, increment odd_C
                odd_c++;
            n >>= 1;
            if (n & 1)
            // even bit is SET, increment even_c
                even_c++;
            n = n >> 1;
        }
        /* Recursive call till you get 0/1 */
        return(isMultN(abs(odd_c - even_c)));
}
    
int main()
{
    int input;
    while(1)
    {
        printf("Input:");
        scanf("%d", &input);
        if(isMultN(input))
        {
            printf("Your input %d can be divided by 3 \n", input);
        }
        else
        {
            printf("Your input %d can not be divided by 3 \n", input);
        }
    }
}


:::success
上圖視窗標題反映你的怨念很深啊～
:notes: jserv
:::

確實 implement 是可行的!!

### 第 1 周第 3 題

在 C 程式中，表達式 1 << 2 + 3 << 4 求值後為何？  
(a) 512  
(b) 16  
(c) 26  
(d) 52  
(e) 25

:::success
延伸問題:

- 在 C 語言規格書中，找出對應運算子優先權的描述並嘗試解讀
:::

* 遇到這種題目看似題目很簡單，但會就是會，不會就是連想送你分都送不了，所以一定要把運算子優先權的順序以及結合順序烙印在腦海裡。

* 運算子優先權 (C語言)
:::warning
下圖不是取自 C99/C11 規格書！請找出第一手材料
:notes: jserv
>好的收到感謝jser大大
>[color=red][name=0922james0922]
:::

:::danger
上圖為截自[C運算子優先權](http://magicjackting.pixnet.net/blog/post/70902861-c-%E8%AA%9E%E8%A8%80:%E9%81%8B%E7%AE%97%E5%AD%90%E5%84%AA%E5%85%88%E6%AC%A1%E5%BA%8F%E5%92%8C%E9%81%8B%E7%AE%97%E6%AC%A1%E5%BA%8F)，雖不是 C11/C99 規格書中的資料，但垃圾還是值得我們做比較的~
下面會補充 C11/C99 規格書中的運算子優先順序。
:::

有了順序的概念問題就迎刃而解了
1. 先將題目中運算子順序最高的找出並將之做括弧的標示，例如在本題目中最高的優先權就是 '+' (+比左移來的高) ex:

 1 << (2 + 3) << 4 

2. 接著在將次之優先權的運算子找出，本題目中的是 '<<'，由左而右依序做括弧的標示

(1 << (2 + 3)) << 4
((1 << (2 + 3)) << 4)

3. 有了絕對的運算順序就能由內而外處理括弧內的東東了

((1 << (2 + 3)) << 4)
((1 << 5) << 4)
(64 << 4)
512

* 是不是很簡單呢! 真的很簡單~~
:::warning
遇到這種題目若是要考陷阱題，一定會將左右結合混雜著考，問題就不會只有由左道又如此簡單了，需要特別將順算子的左或右結合釐清。
:::
* C11/C99
**C11**（也被稱為C1X）指ISO標準_**ISO/IEC 9899:2011**，是當前最新的C語言標準。在它之前的[C語言](https://zh.wikipedia.org/wiki/C%E8%AF%AD%E8%A8%80 "C語言")標準為[C99](https://zh.wikipedia.org/wiki/C99 "C99")。這次修訂新增了被主流C語言[編譯器](https://zh.wikipedia.org/wiki/%E7%BC%96%E8%AF%91%E5%99%A8 "編譯器")(如GCC,Clang,Visual C++等)增加的內容，和引入了[記憶體模型](https://zh.wikipedia.org/w/index.php?title=%E5%86%85%E5%AD%98%E6%A8%A1%E5%9E%8B&action=edit&redlink=1 "記憶體模型（頁面不存在）")以更好的執行[多執行緒](https://zh.wikipedia.org/wiki/%E5%A4%9A%E7%BA%BF%E7%A8%8B)。之前C99的一些被推遲的計劃在C11中增加了，但是對C99仍保留回溯相容。
**GCC**從4.6版本開始，已經可以支援一些C11的特性，Clang則是從3.1版本開始。但[多執行緒](https://zh.wikipedia.org/wiki/%E5%A4%9A%E7%BA%BF%E7%A8%8B "多執行緒")相關的函式庫直到2018年還未出現穩定的實作，等於沒有編譯器可以完整的支援C11。([截取自維基](https://zh.wikipedia.org/wiki/C11))

* C11/C99 規格書中並沒有表格整理運算子的優先順序，但我比較了一下目錄的順序，剛好符合網路上**流傳**的那些資訊的順序
:::info
上圖為截取自網路上[規格書](http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf)的目錄，比對上面網路上的順序剛好是由上到下為由高到低。
每個類別裡的內容都寫得非常詳盡，也說明每個運算子的做法跟功能，同學有興趣可以去詳讀一下可以增強記憶力。
:::

### 第 2 周第 4 題

在 [你所不知道的C語言: 遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl) 提到以下程式碼:

#include <stdio.h>
int p(int i, int N) {
    return (i < N && printf("%d\\n", i)
           &&!p(i + 1, N)) || printf("%d\\n", i);
}
int main() { return p(1, 10) && printf("\\n"); }

預期會得到以下輸出:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->

注意 `10` 只會出現一次。請填補下方程式碼，使得輸出為 `1 -> 2 -> 3 -> 4 -> 5 ->`，並且包含換行符號 (`\n`)

#include <stdio.h>
int p(int i, int N) {  
    return (i < N && printf("%d -\> ", i)
           && Q1(i + Q2, N + Q3));
}
int main() { return p(1, 10) && printf("\\n"); }

提示: Q1 是函式名稱，可能包含 `~` (bitwise NOT) 操作，Q2 和 Q3 是有號整數

* 這題看似簡短的幾行遞迴程式，卻隱含著我以往寫程式都沒用道的小技巧來精簡程式，

return (i < N && printf("%d -\> ", i) && Q1(i + Q2, N + Q3));

* 這行 return 裡包含三個判斷式且用 `&&` 做連結，也就是說若當地一個判斷示 i<N 不成立後面兩個判斷就都不用考慮且也不會執行；反之若是由 `||` 當做連結的話，

return (i < N || printf("%d -\> ", i) || Q1(i + Q2, N + Q3));

則是當地一個判斷式成立的話，後面兩個就不用考慮也不會執行到，所以需要注意的是，即使是 `||` ，判斷式的優先順序也有差，也就是若 `i < N` 跟 `printf("%d -\> ", i)` 交換的話結果就會不一樣了。
::: info
利用這種小技巧就可以避免寫出一堆 if else 的雜亂程式，寫看起來也比較精簡有水準
:::
* Implement

#include <stdio.h>
#include <stdlib.h>
#include <iostream> 

int p(int i, int N) 
{
    return (i < N && printf("%d -\>", i) 
    && !p(i + 1, N)) || printf("%d -\>", i) ;  
}
int main() 
{ 
    return p(1, 10) && printf("\\n") && system("PAUSE");; 
}

* 像是當我在執行時，C 做若是沒有做 `system("PAUSE")` 的動作的話，terminal會出現然後馬上消失，根本沒辦法看結果，於是遞迴的 system pause 要加在哪邊就是門學問了，正常應該是加在 `return 1` 的上面，但如果在這邊加在 return 上的話就會卡住根本不會跑遞迴，一開始有試過加在副函式 return 的最後面用 && 做連接，不過這樣就只會跑到10就停住了並不會執行 `||` 後面的 `print`，因此就在嘗試加在 main 裡的 return 且用 `&&` 連接就搞定了^^。
* 如果我還不知道可以用在 return 裡做 `||` 或 `&&` 連接的話，也許程式的精簡度就不會樣這樣那麼精簡，肯定會一堆if else 判斷。
:::warning
珍惜生命，請愛用 GNU/Linux 開發環境
:notes: jserv
:::

## 閱讀[因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1)心得與啟發
* [心得](https://hackmd.io/qWaLr9JJQa-0e0APgqPHhw?view)
---

##　研讀給定的「[課後學習](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」教材和 [CS:APP 3/e](http://csapp.cs.cmu.edu/)，紀錄心得和提問
================================================================================================================
研讀中。。。