# 2020q3 Homework5 (quiz5)

contribute by <`hsiehong`>

###### tags: `進階電腦系統理論與實作`

[題目](https://hackmd.io/@sysprog/2020-quiz5)

[TOC]

## 測驗1
浮點數除法

#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;
}

D1 = `2`, D2 = `1`

* `od` : 判斷 `slot` (除數) 是否為奇數
* 若除數是偶數，則除數和被除數可以同除 2 ，結果是一樣的，即 `orig`/`slot` = $\dfrac{orig}{2}$/$\dfrac{slot}{2}$
* 當除數是奇數時要特別處理，因為呼叫遞迴是 `divop(orig/2, (slot+1)/2)`，因為 `slot` 是奇數。所以 `(slot+1)/2` 也會是整數，但是正確的應該是 `divop(orig/2, slot/2)`，所以 line 9, 10 在做修正，要修正的值是
$\dfrac{orig}{slot}$ - $\dfrac{orig}{slot+1}$ = $\dfrac{orig \times (slot+1)}{slot \times (slot+1)}$ - $\dfrac{orig \times slot}{slot \times (slot+1)}$ = $\dfrac{orig}{slot \times (slot+1)}$
其中 $\dfrac{orig}{slot+1}$ 就是 line8 所得到的 `result`，所以$\dfrac{result}
{slot}$即為要補回去的誤差值

## 測驗2

QQ0 = `0x01000000`, QQ1 = `0x3f000000`, QQ2 = `23`

## **測驗3**

LeetCode [829. Consecutive Numbers Sum](https://leetcode.com/problems/consecutive-numbers-sum/)

給定一正整數 N，問 N 能寫成幾種連續正整數之和

* 根據題目給定算式可以得到 $kx = N - \dfrac{(k - 1)k}{2}$，其中 $\dfrac{(k - 1)k}{2}$ 可以看成是 $0+1+...+(k-1)$，就是求 $k,x$ 正整數解個數，將上式移項可得 $x = \dfrac{N - \frac{k \times (k-1)}{2}}{k}$
* 已知 `x` 是從 `N` 開始，`x += zzz` 對應到就是 $N - \displaystyle\sum_ {i=0}^{k-1}i$，k 對應到 `i` ，從2開始檢查，因為1必有解就是該數本身，可得 zzz = `1 - i`
* 舉例來說，假設 N = 10，i 從 2 開始

| iteration | N(x) | i | x%i | ret |
|:---------:|:----:|:---:|:---:|:---:|
| init | 10 | 2 | - | 1 |
| 1 | 9 | 2 | 1 | 1 |
| 2 | 7 | 3 | 1 | 1 |
| 3 | 4 | 4 | 0 | 2 |

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;
} 

zzz = `1-i`

另解 :
根據式子 $kx = N - \dfrac{k \times (k+1)}{2}$，只要找出 $k$, $x$ 的正整數解即可，還有我們已經知道 k 的範圍 ($k < \sqrt{2N}$)，可以減少迴圈要跑的範圍

> question : 範圍應該是 k < $\sqrt{2N+k}$，不太明白為什麼估計值可以省略 k

int consecutiveNumbersSum(int N) 
{
    int res = 1;
    for (int k = 2; k <= sqrt(N << 1); k++) {
        if ((N - ((k * (k - 1)) >> 1)) % k == 0)
            res++;
    }
    return res;
}