作者suhorng (飛揚)
站內Prob_Solve
標題[問題] TIOJ1443 大數TLE
時間Sat Oct 11 12:48:47 2008
這題題目大致如下：
______
/ 0, if n=0;
f(n) = | f( [n/2] ) + (n - 2*[n/2]), otherwise;
\______
給定n，須要求出f(0)~f(n)之中的最大值。
範例輸入：2008
範例輸出：10
可以推出答案是 [log2 (n+1)]
現在問題是，數字實在是太大了， (0<=答案<=300000)
我用大數 (壓8位) 依舊TLE，
大數的部份如下：
#define SIZE 13000
#define LAST (SIZE-1)
#define EACH 100000000
typedef int BIG_TYPE;
typedef struct tagUBig {
BIG_TYPE digit[SIZE];
}ubig;
void add(ubig& A, ubig& B) {
int i, carry;
BIG_TYPE *a=A.digit, *b=B.digit;
for (i=LAST,carry=0; i>=0; i--) {
a[i] = a[i]+b[i]+carry;
if (a[i]>=EACH) {
carry = 1;
a[i] -= EACH;
} else {
carry = 0;
}
}
}
void inc(ubig& A) {
int i, carry;
BIG_TYPE *a=A.digit;
a[LAST]++;
for (i=LAST,carry=0; i>=0&&carry;i--) {
a[i] += carry;
if (a[i]>=EACH) {
carry = 1;
a[i] -= EACH;
} else {
carry = 0;
}
}
}
int cmp(ubig& A, ubig& B) {
int i;
BIG_TYPE *a=A.digit, *b=B.digit;
for (i=0; i<SIZE; i++) {
if (a[i]>b[i])
return 1;
else if(a[i]<b[i])
return -1;
}
return 0;
}
逼近的部份如下：
ubig a, b;
int main() {
int max;
while (read(a)) {
zero(b);
inc(b);
max = 0;
while (b<=a) {
max++;
add(b, b);
inc(b);
}
printf("%d\n", max);
}
return 0;
}
我在想，會不會是我這樣逼近算法太慢了？
請問大家有其他逼近的方法或想法嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.84.19
※ 編輯: suhorng 來自: 220.137.84.19 (10/11 14:05)
1F：推 LPH66:我的想法會是反過來想 用二分搜找出輸入在哪兩個2的次方中間 10/11 20:04
2F：→ suhorng:對喔，還有二分搜.....謝啦！我試試看～ 10/11 20:56
3F：推 ShaiMo:n+1一定是在某個[2^k,2^(k+1) )之間 利用二進位去看可以 10/11 21:02
4F：→ ShaiMo:發現剛好就是要你算(n+1)的二進位有幾位 然後減一 10/11 21:02
5F：→ suhorng:嗯是啊 不過2的30萬次方很大的說...... 10/11 22:55
6F：推 DJWS:問題->答案可能不好算 可以試試看答案->問題 錯誤嘗試法 10/12 10:53
7F：→ DJWS:再加上你推得的式子有遞增性質 所以就可以想到一樓所說的了 10/12 10:54
8F：推 stimim:可以用2^m進位，m是自選的適當整數 10/12 20:26