# 2020q3 Homework5 (quiz5)
contributed by < `jeremy3951` >

###### tags: `(2020q3)進階電腦系統理論與實作`

## 題目2.
牛頓逼進法

qq1 : 把數值放到對的地方

## 題目3.
### 解題思路 :
觀察 for 迴圈的中止條件 : `i >= x`
再觀察 `x+= ZZZ` 這行 , 可得知 ZZZ 一定 <0 (不然迴圈不會停止)

選項中只有 (d) 選項 < 0 , 所以答案為 (d)
### 運作原理 :

擷取自[文章](https://blog.csdn.net/zhangpeterx/article/details/100735382)中

思路是：
let N = k + (k+1) + (k+2) + (k+3) + … + (k+i-1)
= ik + (1+2+3+… + i-1)
let sum(i) = (1+2+3+…+i-1), then we have
N = sum(i) + ik ==>i*k = N - sum(i)
Which means: for each i, we can calculate N-sum(i). If N-sum(i) can be divided by i, there is an answer with length i.

**要把 i 看成等差數列的長度 !!**

文章中的解法如下 :

int consecutiveNumbersSum(int N) {
        int sum = 0, ans = 0;
        for(int i = 1; sum < N; i++) {
            sum += i;
            if (((N-sum) % i) == 0)
                ans++;
        }
        return ans;
    }

再看回原本的題目 : ( 擷取部分而已 )

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

起初我以為 ret 的初始值為 1 和 i 從 2 開始都是因為 :

`(x % 1)==0` 一定會成立 , 所以省掉這步直接從 i=2 開始執行

第一步如下 : ( 我當時以為的 )
根據前面參考的程式碼 `if((N-sum)%i==0)`
第一步為 `N -( 1+2)` , 然後再看 N % 2 是否等於 0
以 N=9 為例子 , 9-(1+2)=6 , 再看 6 % 2 是否等於 0

可是 ,

此時看回原本的題目 : `x += 1 - i;`
9 + 1 - 2 = **8!!**

跟原本的數字不一樣了 !

再繼續往下 trace : `(x % i == 0) ?`
8 % 2 = 0 ( 還真的等於 0 ) ~~會是巧合嗎 ?~~

於是我就繼續往下 trace :

網路上參考的程式碼 : ( ret = 0 )
9 - 1 = 8 ----------> 8 % 1 =0 ,ret++
9 - 1 - 2 = 6 ------> 6 % 2 =0 , ret++
9 - 1 - 2 - 3 = 3 --> 3 % 3 = 0 , ret++

老師出的題目 : ( ret = 1 )
9 + 1 - 2 = 8 --> 8 % 2 = 0 , ret++
8 + 1 - 3 = 6 --> 6 % 3 = 0 , ret++
6 + 1 - 4 = 3 --> 3 % 4 = 3 , ret 不變

雖然看起來不一樣 , 但是經過整理一下 :
老師出的題目 : ( ret = 1 )
9 + 1 - 2 = 8 ------------------> 8 % 2 = 0 , ret++
9 + 1 - 2 + 1 - 3 = 6 ----------> 6 % 3 = 0 , ret++
9 + 1 - 2 + 1 - 3 + 1 - 4 = 3 --> 3 % 4 = 3 , ret 不變

再把左式同時 +1 -1 :
老師出的題目 : ( ret = 1 )
9 + 1 - 1 + 1 - 2 = 8 ------------------> 8 % 2 = 0 , ret++
9 + 1 - 1 + 1 - 2 + 1 - 3 = 6 ----------> 6 % 3 = 0 , ret++
9 + 1 - 1 + 1 - 2 + 1 - 3 + 1 - 4 = 3 --> 3 % 4 = 3 , ret 不變

整理一下 :
9 - 1 - 2 + 2 = 8 ----------> 8 % 2 = 0 , ret++
9 - 1 - 2 - 3 + 3 = 6 ------> 6 % 3 = 0 , ret++
9 - 1 - 2 - 3 - 4 + 4 = 3 --> 3 % 4 = 3 , ret 不變

+2 +3 +4 不會影響到後面的 %2 %3 %4 的結果可以拿掉 , 拿掉後 :

9 - 1 - 2 ~~+ 2~~ = 8 - 2 ----------> (8 - 2) % 2 = 0 , ret++
9 - 1 - 2 - 3 ~~+ 3~~ = 6 - 3 ------> (6 - 3) % 3 = 0 , ret++
9 - 1 - 2 - 3 - 4 ~~+ 4~~ = 3 - 4 --> (3 - 4) % 4 = 3 , ret 不變

得知

for (int i = 2; i < x; i++) {
        x += 1 - i; 
        if (x % i == 0)
            ret++;
    }

等價於

for(int i = 1; sum < N; i++) {
            sum += i;
            if (((N-sum) % i) == 0)
                ans++;
        }

### 推導更正 :
根據題目中的片段 :
$N-\dfrac{(k-1)k}{2}\ > 0$
從而推得近似解 :
$k< \sqrt{2N}$

我的推導 :
$N-\dfrac{(k-1)k}{2}\ > 0$
$N> \dfrac{(k-1)k}{2}> \dfrac{(k-1)(k-1)}{2}> \dfrac{(k-1)^2}{2}$
$2N > (k-1)^2$
$\sqrt{2N} > (k-1)$
$\sqrt{2N} >= k$

k 應改為 **小於等於** $\sqrt{2N}$ 才對
### 改寫分析 :
照著老師給的公式 :
$kx=N- \dfrac{(k-1)k}{2}$
自己針對迴圈內部改寫了程式碼如下 :

for (int i = 1; i < x; i++) {
        x=N;
        x -= ((i-1)*i)/2;
        if ((x%i==0))
            ret++;
    }

結果跟老師原本的程式碼跑出一樣的結果

我又提交了另一個版本 : (把迴圈內的 % 運算換掉)

 
    bool divisible(uint32_t n ,int D)
{
    uint64_t M = (UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1);
    return n * M <= M-1;
}
    int consecutiveNumbersSum(int N)
{
    if (N < 1)
        return 0;
    int ret = 1;
    int x = N;
    for (int i = 2; i < x; i++) {
        x += 1-i;
        if (divisible(x,i))
            ret++;
    }
    return ret;
} 

結果就妙了...

這四次都是一樣的程式碼 , 但跑出來的時間卻有點不同

於是我就想測試我第一個版本的程式碼 ....
果然也是這樣 !!
這我就不懂了...