# 2020q3 Homework5 (quiz5)
contributed by < `jonec76` >
###### tags: `sysprog-2020`

> [作業說明](https://hackmd.io/@sysprog/r1z0WPWLD)
> [題目](https://hackmd.io/@sysprog/2020-quiz5)

## 開發環境

$ uname -a
Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux

## 參考解答

D1=2
D2=1
ZZZ=1-i
## Q1

- 解題想法

此題題目能夠處理浮點數的除法，在除法時又能夠分成兩種 case 探討，也就是除數是偶數或者奇數。

函式的第 1 個參數是被除數，型態可以是浮點數，第 2 個參數是除數。

    int od = slots & 1;

上方程式碼能夠檢查出現在的除數是否是奇數，並且進入下方的遞迴函式

    divop(orig / 2, od ? (slots + 1) >> 1 : slots >> 1)

先假設若除數在 `>>1` ( 除以 2 ) 的傳遞過程中，永遠都保持偶數的話，因為每次遞迴進去，`orig` 都會除以 2，所以這樣的結果，就是遞迴到終止條件的 `result`。那麽為何要額外處理奇數的？

    result += divop(result, slots);

這邊能夠從下方的數學式子而來：

$\dfrac{A}{B} = \dfrac{A}{B+1} + X,\ \ Where\ \ B\ \ is\ \ a\ \ odd\ \ number$

接著移項：

$X=\dfrac{A}{B}-\dfrac{A}{B+1}$
$\ \ \ \ =\dfrac{A}{B}＊(B+1)$
$\ \ \ \ =\dfrac{A}{B+1} *\dfrac{1}{B}$

在遞迴過程中，如果除數是奇數的話會讓該除數 + 1 之後往下傳，如同上方的 $A/(B+1) + X$，但因為原本是要計算 $A/(B)$，所以在往下遞迴時只做了加號左邊的部分，沒有算到 $X$。

所以在遞迴 backtracking 階段時，要將加號右邊的 $X$ 也加上才符合數學式子。而因為在前面已經算過 `result` 就是 $A/(B+1)$，要計算 $result*1/B$，只要再將這兩個值丟入 `divop` 進行計算即可。

## Q3

- 解題想法

根據題目的數學式，以及看答案後才知背後意思。可以先看到下方數學式

$kx=N - \dfrac{(k-1)k}{2}$

此題題目想要知道，$N$ 這個數可以被連續數相加的組合數有多少個，又知道上方的 x 一定是正整數，所以若可以找到一個 $k$ 是正整數且滿足上方的數學式，就可以得到一組 $k$ 個連續數相加的組合。

若假設由 3 個連續數組合出 $N$，那就可以知道 k=3，所以

$\dfrac{-(k-1)k}{2}=-3$

當 $kx$ 計算出來之後，$x$ 是正整數的話就表示有解，也就是下方程式碼處理的部分

    if (x % i == 0)
        ret++;

那為什麼需要 `+=` 的運算呢？

    x += ZZZ;

這部分在看完數學式才明白，這背後是梯形公式

$\dfrac{-(k-1)k}{2}=-1+-2+...+(-k+1)$

展開後得到的結果，所以答案湊起來才是 `1 - i`