[問題] TIOJ1443 大數TLE

[suhorng (飛揚)]

這題題目大致如下：
        ______
       /  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)
推 LPH66:我的想法會是反過來想 用二分搜找出輸入在哪兩個2的次方中間
→ suhorng:對喔，還有二分搜.....謝啦！我試試看～
推 ShaiMo:n+1一定是在某個[2^k,2^(k+1) )之間 利用二進位去看可以
→ ShaiMo:發現剛好就是要你算(n+1)的二進位有幾位 然後減一
→ suhorng:嗯是啊 不過2的30萬次方很大的說......
推 DJWS:問題->答案可能不好算  可以試試看答案->問題  錯誤嘗試法
→ DJWS:再加上你推得的式子有遞增性質  所以就可以想到一樓所說的了
推 stimim:可以用2^m進位，m是自選的適當整數