PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] TIOJ1443 大數TLE

看板Prob_Solve (計算數學 Problem Solving)作者suhorng (飛揚)時間16年前 (2008/10/11 12:48)推噓4(4推 0噓 4→)

留言8則, 5人參與討論串1/1

這題題目大致如下： ______ / 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)