Re: [問題] 資料結構 陣列
※ 引述《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)
→
02/24 03:11, , 1F
02/24 03:11, 1F
→
02/24 03:54, , 2F
02/24 03:54, 2F
推
02/24 12:28, , 3F
02/24 12:28, 3F
推
02/24 15:11, , 4F
02/24 15:11, 4F
→
02/24 15:12, , 5F
02/24 15:12, 5F
→
02/24 15:33, , 6F
02/24 15:33, 6F
→
02/24 15:33, , 7F
02/24 15:33, 7F
→
02/24 15:34, , 8F
02/24 15:34, 8F
→
02/24 15:36, , 9F
02/24 15:36, 9F
→
02/24 15:37, , 10F
02/24 15:37, 10F
→
02/24 15:38, , 11F
02/24 15:38, 11F
→
02/24 15:39, , 12F
02/24 15:39, 12F
推
02/24 15:58, , 13F
02/24 15:58, 13F
→
02/24 16:22, , 14F
02/24 16:22, 14F
推
02/24 16:23, , 15F
02/24 16:23, 15F
→
02/24 16:23, , 16F
02/24 16:23, 16F
→
02/24 16:24, , 17F
02/24 16:24, 17F
→
02/24 16:25, , 18F
02/24 16:25, 18F
→
02/24 16:26, , 19F
02/24 16:26, 19F
→
02/24 17:03, , 20F
02/24 17:03, 20F
推
02/24 18:12, , 21F
02/24 18:12, 21F
→
02/24 18:12, , 22F
02/24 18:12, 22F
→
02/24 18:12, , 23F
02/24 18:12, 23F
→
02/24 18:13, , 24F
02/24 18:13, 24F
推
02/24 20:39, , 25F
02/24 20:39, 25F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章