作者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