# 2020q3 Homework5 (quiz5)

contributed by < `fdfdd12345628` >

## 測驗一

題目要求作浮點除法，程式碼如下

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

double divop(double orig, int slots) {
    if (slots == 1 || orig == 0)
        return orig;
    int od = slots & 1;
    double result = divop(orig / D1, od ? (slots + D2) >> 1 : slots >> 1);
    if (od)
        result += divop(result, slots);
    return result;
}

可以發現，如果除數是偶數，就直接回傳第八行 `result`
因此可以合理判斷第八行是將除數與被除數都除以二，才會算出原本的答案，因此 `D1` 為 `2`

接著如果除數是奇數，則會再加上第十行的計算，因此可以用數學推算出遞迴的結果

$result={orig \over (slots+D2)}+{orig \over (slots+D2)^2}+{orig \over (slots+D2)^3}...$

由等比級數公式可以知道 $result={{orig \over (slots+D2)}*(1-1 / (slots+D2)^ \infty ) }/{(1-1/(slots+D2))}={orig/(slots+D2) \over 1-1/(slots+D2)}={orig \over slots+D2-1}$ 所以如果在奇數時要使等號成立， `D2` 為 `1`

## 測驗二

題目要求做根號 float ，也就是給定 $n$ 解 $x^2-n=0$ 的 $x$
根據牛頓法

## 測驗三

題目要求為給定一個正整數 N，問 N 能寫成多少種連續正整數之和，例如 9 可寫成 $4+5$ ，或者 $2+3+4$ 。

連續正整數的可以寫成以下格式 $X+(X+1)+(X+2)...$ 也就是 $X*n+(1+2+3+...+(n-1))$

所以如果要判斷一個整數是不是能夠寫成多少種連續正整數之和，只要將它減去 $(1+2+3+...+(n-1))$ 並且判斷剩下的數字能不能被 $n$ 整除即可，
由於 $(1+2+3+...+(n-1))$ 是會隨著 $n$ 而逐漸加上去的，因此可以重複使用之前計算的結果。

題目程式碼如下：

int consecutiveNumbersSum(int N)
{
    if (N < 1)
        return 0;
    int ret = 1;
    int x = N;
    for (int i = 2; i < x; i++) {
        x += ZZZ;
        if (x % i == 0)
            ret++;
    }
    return ret;
}

可以看到 `x` 的值在迴圈中是被重複利用的，所以可以判斷他會被逐漸減去 $1, 2 ...$ ，減去後再判斷能不能被 `i` 整除，如果可以就代表有一段連續整數和為這個數字。因此 `ZZZ` 為 `1-i` 來讓 `x` 逐漸減去越來越大的數字。