Morris' Blog

2013-03-09 09:53:05Morris

如何加快 printf("%d") 在解題時的使用

留言 0 收藏 0 推薦 0

今日探討：「如何加快 printf("%d") 在解題時的使用？」

必要條件：假如的數字相當頻繁且重複，而且小於某個定值。

使用 char [max_number][max_digit] 記錄所有可能輸出。
最後使用 printf("%s") 速度快 10 ms 不到。
用一堆 if，取代 printf，用一堆 putchar() 輸出一個數字，速度再快 10 ms 不到。
使用一個 BUFFER，取代 putchar()，寫一個指標*p指向 BUFFER，
然後將輸出存 BUFFER，最後再輸出答案，速度再快 10 ms 不到。

範例題目：UVa 583 - Prime Factors

參考程式碼

#include <stdio.h>
int p[5500], pt = 0;
char pstr[5500][7];
void sieve() {
    int i, j;
    char mark[50000] = {};
    for(i = 2; i < 46340; i++)
        if(!mark[i]) {
            for(j = i+i; j < 46340; j += i)
                mark[j] = 1;
            sprintf(pstr[pt], "%d", i);
            p[pt++] = i;
        }
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    sieve();
    int n, i, j;
    char buf[1005], *pb;
    while(ReadInt(&n) && n) {
        printf("%d = ", n);
        if(n == 1) {
            puts("1");
            continue;
        }
        if(n == -1) {
            puts("-1");
            continue;
        }
        int first = 0;
        if(n < 0)
            printf("-1"), first = 1, n = -n;
        pb = buf;
        for(i = 0; i < pt && p[i]*p[i] <= n; i++) {
            while(n%p[i] == 0) {
                if(first)
                    *pb++ = ' ', *pb++ = 'x', *pb++ = ' ';
                //putchar(' '), putchar('x'), putchar(' ');
                else first = 1;
                if(pstr[i][1] == '\0')
                    *pb++ = pstr[i][0];
                    //putchar(pstr[i][0]);
                else if(pstr[i][2] == '\0')
                    *pb++ = pstr[i][0], *pb++ = pstr[i][1];
                    //putchar(pstr[i][0]), putchar(pstr[i][1]);
                else if(pstr[i][3] == '\0')
                    *pb++ = pstr[i][0], *pb++ = pstr[i][1], *pb++ = pstr[i][2];
                    //putchar(pstr[i][0]), putchar(pstr[i][1]), putchar(pstr[i][2]);
                else if(pstr[i][4] == '\0')
                    *pb++ = pstr[i][0], *pb++ = pstr[i][1], *pb++ = pstr[i][2],
                    *pb++ = pstr[i][3];
                    //putchar(pstr[i][0]), putchar(pstr[i][1]), putchar(pstr[i][2]),
                    //putchar(pstr[i][3]);
                else
                    *pb++ = pstr[i][0], *pb++ = pstr[i][1], *pb++ = pstr[i][2],
                    *pb++ = pstr[i][3], *pb++ = pstr[i][4];
                    //putchar(pstr[i][0]), putchar(pstr[i][1]), putchar(pstr[i][2]),
                    //putchar(pstr[i][3]), putchar(pstr[i][4]);
                n /= p[i];
            }
        }
        if(n != 1) {
            if(first)
                *pb++ = ' ', *pb++ = 'x', *pb++ = ' ';
                //putchar(' '), putchar('x'), putchar(' ');
            else first = 1;
            sprintf(pb, "%d", n);
        } else
            *pb = '\0';
        puts(buf);
    }
    return 0;
}

上一篇：[分析] 生成排列大車拼

下一篇：[討論][技巧深入] 100 - The 3n + 1 problem

Morris' Blog

如何加快 printf("%d") 在解題時的使用

你可能感興趣的文章

懷念的味道 - 勺勺客

小事小事

~.~

半信半疑

小統計