Try   HackMD

2020q3 Homework5 (quiz5)

contribute by <hsiehong>

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

題目

測驗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 =
    orig2
    /
    slot2
  • 當除數是奇數時要特別處理,因為呼叫遞迴是 divop(orig/2, (slot+1)/2),因為 slot 是奇數。所以 (slot+1)/2 也會是整數,但是正確的應該是 divop(orig/2, slot/2),所以 line 9, 10 在做修正,要修正的值是
    origslot
    -
    origslot+1
    =
    orig×(slot+1)slot×(slot+1)
    -
    orig×slotslot×(slot+1)
    =
    origslot×(slot+1)

    其中
    origslot+1
    就是 line8 所得到的 result,所以
    resultslot
    即為要補回去的誤差值

測驗2

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

測驗3

LeetCode 829. Consecutive Numbers Sum

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

  • 根據題目給定算式可以得到
    kx=N(k1)k2
    ,其中
    (k1)k2
    可以看成是
    0+1+...+(k1)
    ,就是求
    k,x
    正整數解個數,將上式移項可得
    x=Nk×(k1)2k
  • 已知 x 是從 N 開始,x += zzz 對應到就是
    Ni=0k1i
    ,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=Nk×(k+1)2,只要找出
k
,
x
的正整數解即可,還有我們已經知道 k 的範圍 (
k<2N
),可以減少迴圈要跑的範圍

question : 範圍應該是 k <

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