2020q3 Homework5 (quiz5)

contributed by < jeremy3951 >

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

題目2.

牛頓逼進法

qq1 : 把數值放到對的地方

題目3.

解題思路 :

觀察 for 迴圈的中止條件 : i >= x
再觀察 x+= ZZZ 這行 , 可得知 ZZZ 一定 <0 (不然迴圈不會停止)

選項中只有 (d) 選項 < 0 , 所以答案為 (d)

運作原理 :

擷取自文章中

思路是：
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-{\displaystyle \frac{(k-1)k}{2}}>0$
從而推得近似解 :

$k<\sqrt{2N}$

我的推導 :

$N-{\displaystyle \frac{(k-1)k}{2}}>0$

$N>{\displaystyle \frac{(k-1)k}{2}}>{\displaystyle \frac{(k-1)(k-1)}{2}}>{\displaystyle \frac{(k-1{)}^2}{2}}$

$2N>(k-1{)}^2$

$\sqrt{2N}>(k-1)$

$\sqrt{2N}>=k$

k 應改為 小於等於

$\sqrt{2N}$ 才對

改寫分析 :

照著老師給的公式 :

$kx=N-{\displaystyle \frac{(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;
} 

結果就妙了…

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

於是我就想測試我第一個版本的程式碼 …

果然也是這樣 !!
這我就不懂了…