[問題] TIOJ1443 大數TLE
這題題目大致如下：
______
/ 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)
推
10/11 20:04, , 1F
10/11 20:04, 1F
→
10/11 20:56, , 2F
10/11 20:56, 2F
推
10/11 21:02, , 3F
10/11 21:02, 3F
→
10/11 21:02, , 4F
10/11 21:02, 4F
→
10/11 22:55, , 5F
10/11 22:55, 5F
推
10/12 10:53, , 6F
10/12 10:53, 6F
→
10/12 10:54, , 7F
10/12 10:54, 7F
推
10/12 20:26, , 8F
10/12 20:26, 8F