Re: [問題] 資料結構 陣列

[yauhh (喲)]

※ 引述《aleelyle (lyle)》之銘言：
: 某個學校的考古題.....
: 一個size是N的陣列 有以下的operations
: 1>initial()
: 2>write(k,m)
: 3>read<k>
: 4>multiplyall(n) 所有陣列的元素乘以n
: 條件: 除了 1> 以外, 其他的operations  time 的 worst case 都是O(1)
: 實作這個陣列

struct Rnum {
    double numerator,
           denominator;
};

class Arr {
    private:
        struct Rnum *elm;
        double mul;
    public:
        Arr(int n);
        Arr write(int k, double m);
        double read(int k);
        Arr multiplyall(double n);
};

Arr(int n) {
    elm = new struct Rnum[n];
    for (int i=0; i<n; i++) {
        elm[i].numerator = 0;
        elm[i].denominator = 1;
    }
    mul = 1;
}

Arr Arr::multiplyall(double n) {
    if (abs(n - 0) < 0.000001) {
        cerr << "Error: multiplyall doesn\'t accept zero as a argument.\n";
        return null;
    }
    mul *= n;      // Multiply-all要造成O(1)程度,八成是只改個變數吧...
    return this;   // 因此, write 和 read 函數要配合它.
}                  // 原本O(n)的multiplyall要想辦法擠壓成O(1),
                   // 真是消耗人生.

Arr Arr::write(int k, double m) {
    elm[k].numerator = m;
    elm[k].denominator = mul;
    return this;
}

double Arr::read(int k) {
    if (abs(elm[k].denominator - mul) < 0.0000001)
        return elm[k].numerator;
    else
        return (elm[k].numerator / elm[k].denominator * mul);
}


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.108.35
※ 編輯: yauhh           來自: 218.160.108.35       (02/24 02:53)
→ aleelyle:看來沒別的方法了.. 感謝
→ yauhh:麻煩的是zeroall加進來,就更...
推 ledia:為什麼還要分分子和分母呀? @@
推 Dannvix:很好奇這樣的話 ZeroAll() 怎麼做...
→ Dannvix:總不能只把係數設為 0 吧？
→ jhchou:zeroall我的做法是 給一個global的counter c
→ jhchou:每一個element k也給一個counter ck
→ jhchou:當呼叫zeroall的時候c++, write(k, m)的時候讓ck=c
→ jhchou:當read(k)的時候 要是ck < c 就return 0
→ jhchou:簡單的說用c表示zeroall的次數 用ck表示element k是在哪一
→ jhchou:次zeroall之後寫入的 ck < c表示k被寫入之後呼叫過zeroall
→ jhchou:所以read的時候不管他存什麼直接給0
推 VictorTom:有道理, 這個方法沒有去想到, 謝謝j大<(_ _)>
→ yauhh:jhchou這方法有問題,是zeroall之後write幾項,你把ck設為c
推 loveme00835:有點timestamp的味道
→ yauhh:意思是讓每個陣列元素都恢復為參考乘數mul,對於其他歸零卻
→ yauhh:未曾write的元素來看,就不對了.
→ yauhh:回ledia,做成分數是因為乘數累積乘了次數多了會有一點誤差..
→ yauhh:像10*0.3*3,乘數累積多了誤差就爆出來.如果這題要認真的話..
→ jhchou:把ck設為c是只讓element k恢復而已 沒有讓每個元素都恢復啊
推 ledia:乘數累積? 要解決誤差的問題應該是針對 mul 吧, 分子分母除
→ ledia:了 ouput 都不會乘到東西呀 @@
→ ledia:output*
→ ledia:推 timestamp, j 大的方法我倒沒想到
推 Dannvix:j 大的方法真是酷，推！(並且筆記 XD