Re: [問題] ACM 254 TLE
※ 引述《lions0164 (LionsHeart)》之銘言：
: http://paste.plurk.com/show/399701/
: 但這樣的寫法在處理大數時 一定會TLE
: 想請問有沒有辦法用這方法但是能夠讓他不TLE呢?
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
不確定你的方法是個好方法，只針對「硬用」這方法解釋 -
加速大數運算。
1. 將 element 儲存範圍變大
目前你使用的是每個 element 範圍是 0~9, 資料型態為 int
可將 element 範圍調至 10 / 100 / 1000 / 10000
#define CAP 10000
void add(int *result, int *a, int *b, int n)
{
int i=0;
int carry=0;
memset((void*)c, 0, n*sizeof(int));
for(i=0; i!=n; ++i){
c[i] = (a[i]+b[i]+carry) % CAP;
carry = c[i] / CAP;
}
}
相對的，這樣在陣列大小n之選取上也可變得較小,這速度上差異看得出來。
減法再自己想
2. 增寫 大數 op 一般整數
這部份不知道你有沒有考慮，不過增寫這部份應會快一點，
因大多情形，似乎仍是大數 op 一般整數。
3. 記錄每個大數使用位數
假設 int a[32], b[32]; a 實際用了 10 位， b 用了 4 位
for loop 根本不用跑 32 次，加法、減法只需跑 11 次(包含進位那次)
若大數常用的話，這也是可以加速的地方
於是 "我以為" 或許考濾類似這樣的結構效果可能不錯
#define SIZE 20
#define CAP 10000
typedef struct tagBigNum{
int zero; // 判斷是否為0, 因 +-*/ 對於 0 這個數很敏感
int used_dig; // 判斷已使用位數
int negative; // 這個無號數的話就不用考慮
int num_array[SIZE];
}BigNum;
以上提供做意見, 我想如果可以有其它解決,
大數或許不會是首先考量的吧...
--
YouLoveMe() ? LetItBe() : LetMeFree();
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.142
→
03/17 15:58, , 1F
03/17 15:58, 1F
→
03/17 16:50, , 2F
03/17 16:50, 2F
討論串 (同標題文章)