發表新討論
#3830: 要怎麼加速呢?


xatier (一串電研的阿飄先生)

學校 : 國立臺中第一高級中學
編號 : 4282
來源 : [140.113.17.175]
最後登入時間 ：
2014-12-09 21:57:44
d471. 0 與 1 的遊戲 -- 葆葆 | From: [163.28.80.40] | 發表日期 : 2010-06-05 12:42
我試了三種寫法
 
第一種用一個函數把轉二進位包起來
 
第二種用一維陣列建表
 
第二種改成二維陣列建表 
 
好像都差不多快(4X ms) 
 
我看有人可以加快到10ms以內
 
是怎麼做到的呢? 
 
//============================== 
 
#include <stdio.h>
#include <string.h>


void two (int X, bool *B) {
for (int i = 0; i < 31; i++) {
B[i] = 0;
}
    int now, bottom;
    now = X;
    bottom = 0;
    while (now != 0) {
        B[bottom] = now % 2;
        now /= 2;
        bottom++;
    }
}

int main () {
int n, i, j;
bool bit[32];
while (scanf("%d", &n) != EOF) {
for (i = 0; i < 1<<n; i++) {
two(i, bit);
for (j = n-1; j >= 0; j--) {
printf("%d", bit[j]);
}
puts("");
}
}
return 0;
}
 
 
 
//====================================== 
 
#include <stdio.h>
#define BASE 2

int main () {
    int n, i, j;
    int bit[32];
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < 32; i++) {
            bit[i] = 0;
        }
        for (i = 0; i < 1<<n; i++) {
            for (j = n-1; j >= 0; j--) {
                printf("%d", bit[j]);
            }
            puts("");
            bit[0]++;
            for (j = 0; j < 32; j++) {
                if (bit[j] > BASE-1) {
                    bit[j+1] += (bit[j] / BASE);
                    bit[j] %= BASE;
                }
            }
        }
    }
    return 0;
}
 
//============================
 
#include <stdio.h>
#define BASE 2

int bit[32768][32] = {0};

int main () {
    int n, i, j;
    
bit[0][0] = 0;
for (i = 1; i < 1<<14; i++) {
for (j = 0; j < 32; j++) {
bit[i][j] = bit[i-1][j];
}
bit[i][0]++;
for (j = 0; j < 32; j++) {
if (bit[i][j] > BASE-1) {
bit[i][j+1] += (bit[i][j] / BASE);
bit[i][j] %= BASE;
}
}
}

    while (scanf("%d", &n) != EOF) {
for (i = 0; i < 1<<n; i++) {
for (j = n-1; j >= 0; j--) {
printf("%d", bit[i][j]);
}
puts("");
}
    }
    return 0;
} 
 
 
#4240: Re:要怎麼加速呢?


minuteC (minuteC)

學校 : 不指定學校
編號 : 12792
來源 : [140.118.234.158]
最後登入時間 ：
2011-09-30 23:00:48
d471. 0 與 1 的遊戲 -- 葆葆 | From: [140.118.232.24] | 發表日期 : 2010-09-13 19:38
我試了三種寫法
 
第一種用一個函數把轉二進位包起來
 
第二種用一維陣列建表
 
第二種改成二維陣列建表 
 
好像都差不多快(4X ms) 
 
我看有人可以加快到10ms以內
 
是怎麼做到的呢? 
 
//============================== 
 
#include
#include


void two (int X, bool *B) {
for (int i = 0; i < 31; i++) {
B[i] = 0;
}
    int now, bottom;
    now = X;
    bottom = 0;
    while (now != 0) {
        B[bottom] = now % 2;
        now /= 2;
        bottom++;
    }
}

int main () {
int n, i, j;
bool bit[32];
while (scanf("%d", &n) != EOF) {
for (i = 0; i < 1<
two(i, bit);
for (j = n-1; j >= 0; j--) {
printf("%d", bit[j]);
}
puts("");
}
}
return 0;
}
 
 
 
//====================================== 
 
#include
#define BASE 2

int main () {
    int n, i, j;
    int bit[32];
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < 32; i++) {
            bit[i] = 0;
        }
        for (i = 0; i < 1<
            for (j = n-1; j >= 0; j--) {
                printf("%d", bit[j]);
            }
            puts("");
            bit[0]++;
            for (j = 0; j < 32; j++) {
                if (bit[j] > BASE-1) {
                    bit[j+1] += (bit[j] / BASE);
                    bit[j] %= BASE;
                }
            }
        }
    }
    return 0;
}
 
//============================
 
#include
#define BASE 2

int bit[32768][32] = {0};

int main () {
    int n, i, j;
    
bit[0][0] = 0;
for (i = 1; i < 1<<14; i++) {
for (j = 0; j < 32; j++) {
bit[i][j] = bit[i-1][j];
}
bit[i][0]++;
for (j = 0; j < 32; j++) {
if (bit[i][j] > BASE-1) {
bit[i][j+1] += (bit[i][j] / BASE);
bit[i][j] %= BASE;
}
}
}

    while (scanf("%d", &n) != EOF) {
for (i = 0; i < 1<
for (j = n-1; j >= 0; j--) {
printf("%d", bit[i][j]);
}
puts("");
}
    }
    return 0;
} 
 


我10ms過

原本在自己電腦測的時候以為會TLE

作一個轉換函數把10進制的數字轉成2進制的字串

外迴圈是從0~n^2-1

內迴圈是輸出n個位元

程式給你參考一下

 #include <stdio.h>

int ipow(int a,int b){
    int t,i;
    for(t=1,i=0;i<b;i++)
        t*=a;
    return t;
}
void dtob(int a,char *b,int n){
    int i;
    for(i=0;i<n;i++){
        if(a<=0){
            b[i]='0';
            continue;
        }
        b[i]=a%2+'0';
        a/=2;
    }
}

int main(){
    int n,i,j,p;
    char str[18];
    while(scanf("%d",&n)!=EOF){
        p=ipow(2,n);
        for(i=0;i<p;i++){
            dtob(i,str,n);
            for(j=n-1;j>=0;j--)
                printf("%c",str[j]);
            printf("\n");
        }
    }
    return 0;
}

 
#6689: Re:要怎麼加速呢?


jghs1328 (Danny 渣渣)

學校 : 臺北市立建國高級中學
編號 : 20366
來源 : [111.184.42.115]
最後登入時間 ：
2014-02-26 17:38:36
d471. 0 與 1 的遊戲 -- 葆葆 | From: [58.114.211.6] | 發表日期 : 2012-06-14 19:32
我試了三種寫法
 
第一種用一個函數把轉二進位包起來
 
第二種用一維陣列建表
 
第二種改成二維陣列建表 
 
好像都差不多快(4X ms) 
 
我看有人可以加快到10ms以內
 
是怎麼做到的呢? 
 
//============================== 
 
#include
#include


void two (int X, bool *B) {
for (int i = 0; i < 31; i++) {
B[i] = 0;
}
    int now, bottom;
    now = X;
    bottom = 0;
    while (now != 0) {
        B[bottom] = now % 2;
        now /= 2;
        bottom++;
    }
}

int main () {
int n, i, j;
bool bit[32];
while (scanf("%d", &n) != EOF) {
for (i = 0; i < 1<
two(i, bit);
for (j = n-1; j >= 0; j--) {
printf("%d", bit[j]);
}
puts("");
}
}
return 0;
}
 
 
 
//====================================== 
 
#include
#define BASE 2

int main () {
    int n, i, j;
    int bit[32];
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < 32; i++) {
            bit[i] = 0;
        }
        for (i = 0; i < 1<
            for (j = n-1; j >= 0; j--) {
                printf("%d", bit[j]);
            }
            puts("");
            bit[0]++;
            for (j = 0; j < 32; j++) {
                if (bit[j] > BASE-1) {
                    bit[j+1] += (bit[j] / BASE);
                    bit[j] %= BASE;
                }
            }
        }
    }
    return 0;
}
 
//============================
 
#include
#define BASE 2

int bit[32768][32] = {0};

int main () {
    int n, i, j;
    
bit[0][0] = 0;
for (i = 1; i < 1<<14; i++) {
for (j = 0; j < 32; j++) {
bit[i][j] = bit[i-1][j];
}
bit[i][0]++;
for (j = 0; j < 32; j++) {
if (bit[i][j] > BASE-1) {
bit[i][j+1] += (bit[i][j] / BASE);
bit[i][j] %= BASE;
}
}
}

    while (scanf("%d", &n) != EOF) {
for (i = 0; i < 1<
for (j = n-1; j >= 0; j--) {
printf("%d", bit[i][j]);
}
puts("");
}
    }
    return 0;
} 
 


我10ms過

原本在自己電腦測的時候以為會TLE

作一個轉換函數把10進制的數字轉成2進制的字串

外迴圈是從0~n^2-1

內迴圈是輸出n個位元

程式給你參考一下

 #include

int ipow(int a,int b){
    int t,i;
    for(t=1,i=0;i        t*=a;
    return t;
}
void dtob(int a,char *b,int n){
    int i;
    for(i=0;i        if(a<=0){
            b[i]='0';
            continue;
        }
        b[i]=a%2+'0';
        a/=2;
    }
}

int main(){
    int n,i,j,p;
    char str[18];
    while(scanf("%d",&n)!=EOF){
        p=ipow(2,n);
        for(i=0;i

            dtob(i,str,n);
            for(j=n-1;j>=0;j--)
                printf("%c",str[j]);
            printf("\n");
        }
    }
    return 0;
}

 


2^16 = 65536

先離線做好，然後直接印出ok嗎?

 
ZeroJudge Forum