かいせつ('A`) 投下用作成中
ソースコードでの回答ありがとうございます。
http://q.hatena.ne.jp/1207585413
できれば説明がほしかったのですが、自分への試練と思い勉強します。
がーん('A`)手段が目的にナッテタヨ
3のつく数字を判定する方法は関数 itoa(num,buf,10) (既に用意されている関数)用意されていないらしいで
10進数であると仮定して文字列に変換した後
strchr (こちらも用意されている関数)で文字 '3' をサーチすればいいと思います('A`)
#include <stdio.h> #include <stdlib.h> #include <string.h> char buf[99]; int ahoninarukazu = 3337; itoa(ahoninarukazu ,buf,10); // buf に "3337" が入る if( strchr(buf,'3') != NULL ) printf("あほになるー"); // '3' を含む
以下は投下したコードのコメント？つき
/* -------------------------------------------------------------------- gcc で itoaを呼んでもまともにコール出来ない 実際にないらしい。MSCがおまけでつけてるだけだったらしい */ /* -------------------------------------------------------------------- ↓返値 変換された文字へのポインタ char* buf そのもの char * itoa( ↓変換する数値 const int num , ↓変換された文字を格納するメモリへのポインタ char* buf, ↓無視します(stdlibにあるものは8,10,16などを指定しほげほげ進数に変換できます) const int ignore ) */ char *itoa( const int num ,char* buf, const int ignore ) { /* -------------------------------------------------------------------- 文字のテーブルです。 ここから字引みたいなことやります。 簡単化のためこんな文字列の感じで書かれていますが、 これは // [要素] ------------- 0 1 2 3 4 5 6 7 8 9 10 ---- const char table[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '\0' }; のことです。 数値 0など を 文字 '0'など に変換するときに使います。 */ const char table[] = "0123456789"; /* -------------------------------------------------------------------- ポインタ *p はバッファ buf の先頭 まずは自分のいる位置をポインタさんに教えます「buf の先頭」 e.g.: num = 12345 buf p ZZZZZZZZZZZZXXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZZ.... */ char *p = buf; /* -------------------------------------------------------------------- num を持っておきたいためtmpを用意 */ int tmp; /* -------------------------------------------------------------------- 数値の尻から判定していくので書き込みポインタを 数値の桁数分すすめます e.g.: num = 12345 buf >>>>>p ZZZZZZZZZZZZXXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZZ.... */ for(tmp=num;tmp>0;tmp /= 10) *p++; /* -------------------------------------------------------------------- 文字の終端は\0 である これがないと表示するときにバッファオーバ e.g.: num = 12345 >>>>>p buf | ZZZZZZZZZZZZXXXXX0XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXX" 注意: \0 を 0として表示してます */ *p='\0'; /* -------------------------------------------------------------------- 数値の尻(一桁目)から数値を判定していく 1. tmp%10: tmp%10 で一番下桁めの数 がわかる 0 1 2 3 4 5 6 7 8 9 2. table[tmp%10]: table から文字を得る tmp%10 が0 のとき table[0] = '0' tmp%10 が1 のとき table[1] = '1' tmp%10 が2 のとき table[2] = '2' tmp%10 が3 のとき table[3] = '3' tmp%10 が4 のとき table[4] = '4' tmp%10 が5 のとき table[5] = '5' tmp%10 が6 のとき table[6] = '6' tmp%10 が7 のとき table[7] = '7' tmp%10 が8 のとき table[8] = '8' tmp%10 が9 のとき table[9] = '9' 3. *--p= pを一つ前にもってく ポインタ*p に ↑で得た文字を突っ込んで 4. tmp /= 10 で次の桁を処理する というのを 最後の桁 tmp>0になるまで繰り返す e.g.: num = 12345 >>>>>p buf ZZZZZZZZZZZZXXXXX0XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXX" (--p) num = 12345 >>>>p b | ZZZZZZZZZZZZXXXXX0XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXX" (*p = table[tmp%10]) num = 12345 tmp = 12345 tmp % 10= 5 table[5]= '5' >>>>p b | ZZZZZZZZZZZZXXXX50XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXX5" (--p) num = 12345 >>>p b | ZZZZZZZZZZZZXXXX50XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXX5" (*p = table[tmp%10]) num = 12345 tmp = 1234 tmp % 10= 4 table[4]= '4' >>>p b | ZZZZZZZZZZZZXXX450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXX45" (--p) num = 12345 >>p b | ZZZZZZZZZZZZXXX450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXX45" (*p = table[tmp%10]) num = 12345 tmp = 123 tmp % 10= 3 table[3]= '3' >>p b | ZZZZZZZZZZZZXX3450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XX345" (--p) num = 12345 >p b| ZZZZZZZZZZZZXX3450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XX345" (*p = table[tmp%10]) num = 12345 tmp = 12 tmp % 10= 2 table[2]= '2' >p b| ZZZZZZZZZZZZX23450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "X2345" (--p) num = 12345 p | ZZZZZZZZZZZZX23450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "X2345" (*p = table[tmp%10]) num = 12345 tmp = 1 tmp % 10= 1 table[3]= '1' p | ZZZZZZZZZZZZ123450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "12345" */ for(tmp=num;tmp>0;tmp /= 10) *--p=table[tmp%10]; /* -------------------------------------------------------------------- バッファ buf を返して 数値から文字列変換したものを返す */ return buf; } /* -------------------------------------------------------------------- ここからのコメントはネタです。 */ int main() { /* -------------------------------------------------------------------- buf が 99 なのは、 99桁もある数値で実行しないであろうという 希望からこのような実装にした。 本音はキーボードを打つ回数が少なく それなりに数値としては大きい値のため採用した e.g.: 1 文字 - 9 2 文字 - 99 3 文字 - 0xF (16) 3 文字 - 999 4 文字 - 0xFF (255) 4 文字 - 9999 */ char buf[99]; /* -------------------------------------------------------------------- 要求のある数値の要件は 整数であることのみであるため int を採用した */ int aho; /* -------------------------------------------------------------------- 1 から 50未満 までを変数 aho にいれて 繰り返す */ for(aho=1; aho<50; aho++){ /* -------------------------------------------------------------------- 3 の倍数 か 5の倍数 か 3がつく数 とき 数値を表示 || (論理or) により どれか一つが 0以外なら if(){ .... の中身を実行する e.g.: 1 || 0 || 0 => 1 0==0 は正しいので => 0以外の数値が返る 1==0 は違うので => 0が返る aho%3 は 3で割ったときの余り (0か3の倍数のとき答えは 0) aho%3==0 (3の倍数のとき) 0以外が返る itoa(aho,buf,10) は aho に入っている数値を文字列に変換する関数 buf は おまじない 場所 住み家 10 は 10進数を表す (がここでは無視してるのでなんでもいい itoa から返ってくるのはaho に入っている数値を文字列にしたもの(bufのポインタ)返る strchr は 文字列から 1文字を捜す strchr( 文字列, '3' ) == NULL 以外のとき 文字列に'3'が含まれている ( '3' が含まれている文字列の位置をポインタとして返す) ないとき != 0 としている (正しくは==NULL しないといけない 通例的に NULL == 0 だと仮定してしまっていたが危険であった) */ if( aho%3==0 || aho%5==0 || strchr(itoa(aho,buf,10),'3')) printf("%d\n",aho); } /* -------------------------------------------------------------------- 0 をなにげに返しているのは プログラムが成功したという希望から */ return 0; } /* -------------------------------------------------------------------- */
itoa の使い方説明終わり。
んでこれを最適化してみます。
まず文字に変換する処理は遅くなるので消します
消した関数が以下の char *search_3( const int num )です
http://codepad.org/2epZT4W8
#define TRUE 1 #define FALSE 0 char *search_3( const int num ) { int tmp; for(tmp=num;tmp>0;tmp /= 10) if( tmp%10 == 3 ) return TRUE; return FALSE; } int main() { int aho; for(aho=1; aho<50; aho++){ if( aho%3==0 || aho%5==0 || search_3(aho) ) printf("%d\n",aho); } return 0; }
他のitoa はどんなのだろう...
- Base = 10 のとき 10 余り出して 10 で割っていっている系
ライセンス不明 よい
16進のときにつぶしが利かない
X/OPEN 文字テーブル使用
GPL さすがGPL これはひどい
switch内 case〜break文 #defineしてる....
もっと素直にかけないものか...
GPL さすがGPL 問題外...
swapの仕方は悪くない
char s[]、char *sなら暗示的に \0 と考えていいと思うので
番人付けてstrlen(s)いらんはずだが...
- こちらは逆に、大きい桁から判定して行っている
GPL 桁数決め打ち(__int32や __int64なんて高々 4294967295や
9223372036854775807 なんだし、決め打ちでいいな..)
というわけで作成
/* keta_v2 */ int map_keta[] = { 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, /* 4294967295 */ 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000, /* 9223372036854775807 */ -1, }; int keta_v1( const int num ) { int tmp, n = 0; for(tmp=num;tmp>0;tmp /= 10) n++; return n; } int keta_v2( const int num ) { int tmp, n = 0; for(n=0;map_keta[n] != -1;n++) if(map_keta[n] > num) break; return n; } int main() { int i; for(i=0; i<50; i++) printf("%d: %d\n",i*i*i , keta_v2(i*i*i)); return 0; }
> time keta_v1.c
0.000u 0.006s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
> time keta_v2.c
0.000u 0.003s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
桁計算ルーチンが50% 速くなったコトがわかる
const int map_keta[] = { 3, 30, 300, 3000, 30000, 300000, 3000000, 30000000, 300000000, 3000000000, /* 4294967295 */ -1, }; int search_3_v1( const int num ) { int tmp, n = 0; for(tmp=num;tmp>0; tmp /= 10) { if( tmp % 10 == 3 ) return num; } return 0; } /* 1 〜 29 までは 一桁目しか見ない版 */ int search_3_v2( const int num ) { int tmp, n = 0; for(n=0, tmp=num;map_keta[n] != -1 || tmp>0;n++, tmp /= 10) { if(map_keta[n] > num) break; /* printf( "\t%d = %d = %d\n", num , map_keta[n], tmp % 10) ;*/ if( tmp % 10 == 3 ) return num; } return 0; } int main() { int i; for(i=0; i<50; i++) printf("%d: %d\n",i , search_3_v2(i)); return 0; }
- 0〜49
> time ./search_3_v1
0.000u 0.006s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
> time ./search_3_v2
0.000u 0.006s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
- 0〜4999
> time ./search_3_v1
0.084u 0.124s 0:00.24 83.3% 6+3014k 0+0io 0pf+0w
> time ./search_3_v2
0.084u 0.110s 0:00.22 86.3% 6+2974k 0+0io 0pf+0w
4999回ループならsearch_3_v2 の方が2秒程度速い
3 < A
13
23
30
31
32
33
34
35
36
37
38
39
43
53
63
73
83
93 < B
103 < 1A
113
123
130
131
132
133
134
135
136
137
138
139
143
153
163
173
183
193 < 1B
203 < 2A
213
:
283
293 < 2B
300 < 3X
:
399 < 3X
403 < 4A
413
:
483
493 < 4B
403 < 4A
413
:
483
493 < 4B
503 < 5A
513
:
583
593 < 5B
603 < 6A
613
:
683
693 < 6B
703 < 6A
713
:
783
793 < 7B
803 < 7A
813
:
883
893 < 8B
903 < 9A
913
:
983
993 < 9B
1003 < 10A
:
1093 < 10B
1,2桁目が A〜Bパターン以外の数値で3が憑くのは
387
1307
2309...
しかし、3, 13, 23, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 43, 53, 63, 73, 83, 93,のいづれかがかかる。
int map_3[] = { 3, 13, 23, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 43, 53, 63, 73, 83, 93, 0}; int search_3_v3( const int num ) { int tmp, n = 0; for(tmp=num;tmp>0; tmp /= 100) { for(n=0;;n++) { if(map_3[n] == 0) break; if(map_3[n] == tmp % 100) return num; // printf( "\t%d = %d = %d\n", num , map_3[n], tmp % 100); } } return 0; } int main() { int i; for(i=0; i<5000; i++) printf("%d: %d\n",i , search_3_v3(i)); return 0; }
- 0〜4999
> time ./search_3_v1
0.084u 0.124s 0:00.24 83.3% 6+3014k 0+0io 0pf+0w
> time ./search_3_v2
0.084u 0.110s 0:00.22 86.3% 6+2974k 0+0io 0pf+0w
> time ./search_3_v3
0.085u 0.106s 0:00.22 81.8% 6+2826k 0+0io 0pf+0w
v2 よりも 4ミリ秒速くなった。
この場合 v1の派生だから、v1 と比べるベきだが
> ./1 > 1out.txt
> ./2 > 2out.txt
> mv a.out 3
> ./3 >3out.txt
> diff 1out.txt 2out.txt
> diff 3out.txt 2out.txt
v2とv3の対策をくっつけた v4
const int map_keta[] = { 3, 30, 300, 3000, 30000, 300000, 3000000, 30000000, 300000000, 3000000000, /* 4294967295 */ -1, }; int map_3[] = { 3, 13, 23, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 43, 53, 63, 73, 83, 93, 0 }; int search_3_v4( const int num ) { int tmp, n, m; for(n=0, tmp=num;map_keta[n] != -1 || tmp>0;n++, tmp /= 100) { if(map_keta[n] > num) break; /* printf( "\t%d = %d = %d\n", num , map_keta[n], tmp % 100) ;*/ for(m=0;;m++) { if(map_3[m] == 0) break; if(map_3[m] == tmp % 100) return num; // printf( "\t%d = %d = %d\n", num , map_3[m], tmp % 100); } } return 0; } int main() { int i; for(i=0; i<5000; i++) printf("%d: %d\n",i , search_3_v4(i)); return 0; }
- 0〜4999
> time ./search_3_v1
0.084u 0.124s 0:00.24 83.3% 6+3014k 0+0io 0pf+0w
> time ./search_3_v2
0.084u 0.110s 0:00.22 86.3% 6+2974k 0+0io 0pf+0w
> time ./search_3_v3
0.085u 0.106s 0:00.22 81.8% 6+2826k 0+0io 0pf+0w
> time ./search_3_v4
0.059u 0.131s 0:00.21 85.7% 22+3019k 0+0io 0pf+0w
1秒速くなった気がする
オチ
> time ./search_3_v1 > /dev/null 0.000u 0.005s 0:00.00 0.0% 0+0k 0+0io 0pf+0w > time ./search_3_v2 > /dev/null 0.000u 0.005s 0:00.00 0.0% 0+0k 0+0io 0pf+0w > time ./search_3_v3 > /dev/null 0.000u 0.004s 0:00.00 0.0% 0+0k 0+0io 0pf+0w > time ./search_3_v4 > /dev/null 0.000u 0.006s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
printしなければ速い
ps: table[2]が3になってたの修正、tmp , tmp%10 ウォッチ式追加。 インデント修正
