code golf入門/C言語編
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
#contents
*code golfとは [#t0360dfa]
普通のゴルフは、ボールをカップに入れるまでのストローク数...
そんなの面白いのか？と思われるかもしれませんが、やってみ...
*このページは？ [#g8ffa0d1]
このページでは、そんなcode golfのC言語での入門ページです...
ちなみに、code golfの言語はなんでもよいと書きましたが、異...
''注意！'' このページを作った人および、この後紹介するC言...
*code golfのサイト紹介 [#d7b371fa]
code golfはあまり「有用」ではないので、そのコンテストサイ...
おそらく最大級だと思われるところは次のサイトです。
>http://codegolf.com/
このサイトは各問題に対して無差別級のランキングと、言語別...
C言語を扱っていて、このページを作った人がよく遊んでいるの...
>http://golf.shinh.org/
このサイトはものすごくたくさんの言語を扱っています(2008年...
*code golfの本の紹介 [#m09e3fdf]
このページと同じくC言語でのcode golfを扱った本がすでにあ...
このページは「code golf''入門''」なので基礎的なところしか...
*コード短縮術 [#l28729e1]
**はじめに [#oa2310e3]
それでは、実際にコード短縮の方法をやっていきます。
コード短縮の方法には、主に二つあります。
-アルゴリズムを改善する
-小手先の業でちまちま削る
アルゴリズムの改善とは、例えば1からnまでの和を出せといわ...
int i,s=0;
for(i=1;i<=n;i++)
s+=i;
printf("%d",s);
とするのを、和の公式を使って
printf("%d",n*(n+1)/2);
とするようなものです(答えを出す「やり方」を変える)。
小手先の業とは、例えばさきほどのコードの for(...) の行を
for(i=n;i--;)
などとすることです。
この例でもそうですが、たいていの場合アルゴリズムを改善し...
**小手先の業 [#xd2b12dc]
***スペース、改行は削る [#x52865d9]
これは基本中の基本です。いらないスペース、改行は全てなく...
(ただし、このページでは読みやすさのためにコード例は全て改...
さて、いらないスペースを削るのは当然ですが、「いると思っ...
入力が標準入力から
1 2
と与えられるとき、scanfを使うならば(code golfではscanfは...
scanf("%d %d",&a,&b);
とすると思います。
しかし、2つの%dの間のスペースは必要なく、
scanf("%d%d",&a,&b);
でも期待通り動作します。
また、ポインタを宣言するときには、通常
int *a; // 標準的な書き方
int * a; // これもたまに見かける
int* a; // 「ポインタ型」を強く意識した書き方
のようにどこかにスペースを1つ以上いれますが、これも
int*a;
として問題ありません。
***#includeはいらない [#v0266aba]
C言語入門のときは「おまじない」といわれ、いつのまにか「ヘ...
じゃあなんのためにヘッダファイルをincludeしてるの？という...
ヘッダファイルをincludeする他の理由として、ヘッダファイル...
***mainの宣言は型なし、引数なしで [#p9262b3c]
普段まじめにプログラムを書いている方は、main関数を
int main(){
...
}
あるいは
int main(void){
...
}
などと書いていると思います(返り値の型をintではなくてvoid...
しかし、C言語の入門書の最初の方によく書いてあるように、in...
main(){
...
}
と書いても問題ありません。
***変数はグローバル宣言、うち1つはmainの仮引数に [#k92123...
さて、一つ前で関数の型が省略できると書きましたが、これは...
main(){
int i,j;
...
}
というコードは、
i,j;
main(){
...
}
としてよいことになります。残念ながら型を省略できるのはグ...
さらに、jをmainの仮引数にしてやると、こちらも型は省略でき...
i;
main(j){
...
}
となって、iとjを結んでいた , の分が1文字へります。
ちなみに、「''グローバル変数は0で初期化される''」ので、こ...
***なるべく短い名前の関数を使う [#bf3f0152]
code golfでは、安全性や統一性(読みやすさにつながる)よりも...
以下に、普段使うライブラリ関数と、それと似たような機能で...
|普段使う関数|似た関数|違い|
|printf|[[puts:http://www.linux.or.jp/JM/html/LDP_man-pag...
|fgets|[[gets:http://www.linux.or.jp/JM/html/LDP_man-page...
|strchr|[[index:http://www.linux.or.jp/JM/html/LDP_man-pa...
|strrchr|[[rindex:http://www.linux.or.jp/JM/html/LDP_man-...
|strcpy|[[strdup:http://www.linux.or.jp/JM/html/LDP_man-p...
|strncmp|[[bcmp:http://www.linux.or.jp/JM/html/LDP_man-pa...
***forはiを減らす可能性も考えて [#k5e8754b]
普通にプログラムを書く時、forループは
for(i=0;i<n;i++){
...
}
のように書くと思います。ここで、C言語の条件評価について思...
for(i=n;i;i--){
...
}
とすれば、1からnがnから0になったという違いはあるものの、...
しかし、iをグローバル変数にしていて0で初期化されている場...
***for文の i++ はムダ！ [#gc5c60bb]
次もfor文についてです。ここではiが(グローバル変数にして)0...
for(;i<n;i++)
printf("%d\n",i);
これを次のようにします。
for(;i<n;)
printf("%d\n",i++);
これで1文字減り、出力もまったく同じです。このように、for...
for(;i<n;i++)
printf("A\n");
を
for(;i++<n;)
printf("A\n");
とすることで短縮できます。
***複文 { ... } は使わない [#p9b279f4]
複文とは、{ } で囲まれた文のことです。ここでもforを例にと...
for(;i++<n;){
j--;
printf("This is the %dth loop\n",i);
}
があったとします。しかし、forの文法をよく思い出すと、
for(式;式;式)
文
なのです。しかし、通常は文1つでは収まらないので { } でく...
for(;i++<n;)
j--,printf("This is the %dth loop\n",i);
とできます。
さて、式だ文だと難しそうなことを書きましたが、基本的に評...
for(式;式;式)
文
なのに、文のところに式(j--,printf(...))を入れられるのはこ...
ややこしくなってしまいましたが、最初は「カンマでつないで...
***for文の空欄を利用する [#o487c016]
さて、さきほどの例ですが、実はもう1バイト減らせます。for(...
for(;i++<n;printf("This is the %dth loop\n",i))
j--;
これでprintのセミコロンのぶんだけ減らすことができました。...
for(a;b;)
c,d;
を
for(a;b;d)
c;
とすることで1バイト減らせます。ただし、dを入れるところが...
このように、forはあいたところにいろいろ入れることができる...
***ifは使わない [#l430a30f]
ifを使わずに条件分岐(のようなもの)を実現する方法は、二つ...
- ? を使う
- &&, || を使う
?は普通の使い方と同様なので、簡単ですね。例えば
if(x>0)
y=x;
else
y=-x;
を、
y=x>0?x:-x;
とします。通常のプログラミングなら見やすさのためにカッコ...
次に && または || を使う方法です。[[C言語のページ:http://...
if(n>0)
puts("test");
を、
n>0&&puts("test");
などとしますこれは n>0?puts("test"):0; より1文字短く、先...
*** ==演算子は使わない [#s3299e15]
前にも書いたように、「''0は偽、0以外は真''」です。これを...
a==n
の形の条件式を短くできます。具体的には、
a-n
とするのです。例えば、
a==5&&puts("5"); // aが5なら"5"と出力
を、
a-5||puts("5");
とします。ただし、a==nはaとnが等しいとき真、a-nはaとnが等...
他にも(==演算子ではありませんが)、 n<5とn-5は長さが同じで...
for(;i-->-5;)
...
を、
for(;i--+5;)
...
とできたりもします。ラッキーなことに、--と+の間にかっこは...
***文字コードは数字で直接書く [#z4bbb775]
これは非常によく使います。例えば、Xの文字コードは10進数で...
putchar('X');
よりも
putchar(88);
としたほうが1文字短くなります。
printf("X") のが短いじゃないか・・・と思われるかもしれま...
printf(i%2?"Y":"X");
putchar(i%2?89:88); // 1文字短い
putchar(88+i%2); // iが偶数なら88+0, iが奇数なら88+1=89
などのように、putcharのほうがかなり縮みます。これはprintf...
ちなみに、文字コードは
printf("%d",'調べたい文字');
で調べられます。例えば、
printf("%d",'X');
とすれば 88 が表示されます。
***gccの拡張を利用する [#m957d2a7]
gccにはさまざまな拡張(標準のCにはない機能)があり、[[こち...
数あるgcc拡張の中でも、特に有用なのは以下の二つです
-三項演算子における中間項(a?b:c の b の部分)の省略
-大きい方、小さい方を表す演算子
です。前者は、例えばnが0以上に限られているとして
a=n?:-1; // nが非0ならa=n, そうでなければa=-1
などと使えそうです。
後者は
x=i>?-i;
のようにするとiの絶対値が標準ライブラリ関数のabs()を使う...
***trueの否定の否定は1 [#hfbeab0f]
例えば、x=100のとき、xはtrue, !xはfalse, そして!!xはもち...
x: 100
!x: 0
!!x: 1
となるのです。0以外の数は真なので!0はなんでもいいのですが...
例えば、yはxがtrueなら1、falseなら0としたいとき、
y=x?1:0; // 三項演算子を利用
x&&y=1; // ifは使わない の章を参照
y=!!x;
のように、!!xを利用するのが一番短くなります。ちなみに、x...
y=x&1;
でもできますが、長さが同じですし!!xならどんなxにでも使え...
***返り値をうまく利用する [#h53cc0f1]
たいていのライブラリ関数はなんらかの値を返します。しかし...
以下に、普段は返り値を無視してしまいがちな関数をまとめま...
|関数|返り値|
|puts|非負の数とあるが、たいがいは出力した文字数(末尾の改...
|printf|出力した文字数を返す。|
|scanf|%で指定した型と一致した個数(正しく代入できた個数)...
|read, write|読み込み or 書き込みしたバイト数を返す。|
特に、scanfは、頻繁に以下のように使われます。
for(;~scanf("%d%d",&a,&b);)
...
入力が2つの整数(の複数行)の場合にこのようにするとどうなる...
***続く [#lb4e06ed]
続く
**アルゴリズムの改善 - ケーススタディ [#p801e95c]
余裕があればやります
終了行:
#contents
*code golfとは [#t0360dfa]
普通のゴルフは、ボールをカップに入れるまでのストローク数...
そんなの面白いのか？と思われるかもしれませんが、やってみ...
*このページは？ [#g8ffa0d1]
このページでは、そんなcode golfのC言語での入門ページです...
ちなみに、code golfの言語はなんでもよいと書きましたが、異...
''注意！'' このページを作った人および、この後紹介するC言...
*code golfのサイト紹介 [#d7b371fa]
code golfはあまり「有用」ではないので、そのコンテストサイ...
おそらく最大級だと思われるところは次のサイトです。
>http://codegolf.com/
このサイトは各問題に対して無差別級のランキングと、言語別...
C言語を扱っていて、このページを作った人がよく遊んでいるの...
>http://golf.shinh.org/
このサイトはものすごくたくさんの言語を扱っています(2008年...
*code golfの本の紹介 [#m09e3fdf]
このページと同じくC言語でのcode golfを扱った本がすでにあ...
このページは「code golf''入門''」なので基礎的なところしか...
*コード短縮術 [#l28729e1]
**はじめに [#oa2310e3]
それでは、実際にコード短縮の方法をやっていきます。
コード短縮の方法には、主に二つあります。
-アルゴリズムを改善する
-小手先の業でちまちま削る
アルゴリズムの改善とは、例えば1からnまでの和を出せといわ...
int i,s=0;
for(i=1;i<=n;i++)
s+=i;
printf("%d",s);
とするのを、和の公式を使って
printf("%d",n*(n+1)/2);
とするようなものです(答えを出す「やり方」を変える)。
小手先の業とは、例えばさきほどのコードの for(...) の行を
for(i=n;i--;)
などとすることです。
この例でもそうですが、たいていの場合アルゴリズムを改善し...
**小手先の業 [#xd2b12dc]
***スペース、改行は削る [#x52865d9]
これは基本中の基本です。いらないスペース、改行は全てなく...
(ただし、このページでは読みやすさのためにコード例は全て改...
さて、いらないスペースを削るのは当然ですが、「いると思っ...
入力が標準入力から
1 2
と与えられるとき、scanfを使うならば(code golfではscanfは...
scanf("%d %d",&a,&b);
とすると思います。
しかし、2つの%dの間のスペースは必要なく、
scanf("%d%d",&a,&b);
でも期待通り動作します。
また、ポインタを宣言するときには、通常
int *a; // 標準的な書き方
int * a; // これもたまに見かける
int* a; // 「ポインタ型」を強く意識した書き方
のようにどこかにスペースを1つ以上いれますが、これも
int*a;
として問題ありません。
***#includeはいらない [#v0266aba]
C言語入門のときは「おまじない」といわれ、いつのまにか「ヘ...
じゃあなんのためにヘッダファイルをincludeしてるの？という...
ヘッダファイルをincludeする他の理由として、ヘッダファイル...
***mainの宣言は型なし、引数なしで [#p9262b3c]
普段まじめにプログラムを書いている方は、main関数を
int main(){
...
}
あるいは
int main(void){
...
}
などと書いていると思います(返り値の型をintではなくてvoid...
しかし、C言語の入門書の最初の方によく書いてあるように、in...
main(){
...
}
と書いても問題ありません。
***変数はグローバル宣言、うち1つはmainの仮引数に [#k92123...
さて、一つ前で関数の型が省略できると書きましたが、これは...
main(){
int i,j;
...
}
というコードは、
i,j;
main(){
...
}
としてよいことになります。残念ながら型を省略できるのはグ...
さらに、jをmainの仮引数にしてやると、こちらも型は省略でき...
i;
main(j){
...
}
となって、iとjを結んでいた , の分が1文字へります。
ちなみに、「''グローバル変数は0で初期化される''」ので、こ...
***なるべく短い名前の関数を使う [#bf3f0152]
code golfでは、安全性や統一性(読みやすさにつながる)よりも...
以下に、普段使うライブラリ関数と、それと似たような機能で...
|普段使う関数|似た関数|違い|
|printf|[[puts:http://www.linux.or.jp/JM/html/LDP_man-pag...
|fgets|[[gets:http://www.linux.or.jp/JM/html/LDP_man-page...
|strchr|[[index:http://www.linux.or.jp/JM/html/LDP_man-pa...
|strrchr|[[rindex:http://www.linux.or.jp/JM/html/LDP_man-...
|strcpy|[[strdup:http://www.linux.or.jp/JM/html/LDP_man-p...
|strncmp|[[bcmp:http://www.linux.or.jp/JM/html/LDP_man-pa...
***forはiを減らす可能性も考えて [#k5e8754b]
普通にプログラムを書く時、forループは
for(i=0;i<n;i++){
...
}
のように書くと思います。ここで、C言語の条件評価について思...
for(i=n;i;i--){
...
}
とすれば、1からnがnから0になったという違いはあるものの、...
しかし、iをグローバル変数にしていて0で初期化されている場...
***for文の i++ はムダ！ [#gc5c60bb]
次もfor文についてです。ここではiが(グローバル変数にして)0...
for(;i<n;i++)
printf("%d\n",i);
これを次のようにします。
for(;i<n;)
printf("%d\n",i++);
これで1文字減り、出力もまったく同じです。このように、for...
for(;i<n;i++)
printf("A\n");
を
for(;i++<n;)
printf("A\n");
とすることで短縮できます。
***複文 { ... } は使わない [#p9b279f4]
複文とは、{ } で囲まれた文のことです。ここでもforを例にと...
for(;i++<n;){
j--;
printf("This is the %dth loop\n",i);
}
があったとします。しかし、forの文法をよく思い出すと、
for(式;式;式)
文
なのです。しかし、通常は文1つでは収まらないので { } でく...
for(;i++<n;)
j--,printf("This is the %dth loop\n",i);
とできます。
さて、式だ文だと難しそうなことを書きましたが、基本的に評...
for(式;式;式)
文
なのに、文のところに式(j--,printf(...))を入れられるのはこ...
ややこしくなってしまいましたが、最初は「カンマでつないで...
***for文の空欄を利用する [#o487c016]
さて、さきほどの例ですが、実はもう1バイト減らせます。for(...
for(;i++<n;printf("This is the %dth loop\n",i))
j--;
これでprintのセミコロンのぶんだけ減らすことができました。...
for(a;b;)
c,d;
を
for(a;b;d)
c;
とすることで1バイト減らせます。ただし、dを入れるところが...
このように、forはあいたところにいろいろ入れることができる...
***ifは使わない [#l430a30f]
ifを使わずに条件分岐(のようなもの)を実現する方法は、二つ...
- ? を使う
- &&, || を使う
?は普通の使い方と同様なので、簡単ですね。例えば
if(x>0)
y=x;
else
y=-x;
を、
y=x>0?x:-x;
とします。通常のプログラミングなら見やすさのためにカッコ...
次に && または || を使う方法です。[[C言語のページ:http://...
if(n>0)
puts("test");
を、
n>0&&puts("test");
などとしますこれは n>0?puts("test"):0; より1文字短く、先...
*** ==演算子は使わない [#s3299e15]
前にも書いたように、「''0は偽、0以外は真''」です。これを...
a==n
の形の条件式を短くできます。具体的には、
a-n
とするのです。例えば、
a==5&&puts("5"); // aが5なら"5"と出力
を、
a-5||puts("5");
とします。ただし、a==nはaとnが等しいとき真、a-nはaとnが等...
他にも(==演算子ではありませんが)、 n<5とn-5は長さが同じで...
for(;i-->-5;)
...
を、
for(;i--+5;)
...
とできたりもします。ラッキーなことに、--と+の間にかっこは...
***文字コードは数字で直接書く [#z4bbb775]
これは非常によく使います。例えば、Xの文字コードは10進数で...
putchar('X');
よりも
putchar(88);
としたほうが1文字短くなります。
printf("X") のが短いじゃないか・・・と思われるかもしれま...
printf(i%2?"Y":"X");
putchar(i%2?89:88); // 1文字短い
putchar(88+i%2); // iが偶数なら88+0, iが奇数なら88+1=89
などのように、putcharのほうがかなり縮みます。これはprintf...
ちなみに、文字コードは
printf("%d",'調べたい文字');
で調べられます。例えば、
printf("%d",'X');
とすれば 88 が表示されます。
***gccの拡張を利用する [#m957d2a7]
gccにはさまざまな拡張(標準のCにはない機能)があり、[[こち...
数あるgcc拡張の中でも、特に有用なのは以下の二つです
-三項演算子における中間項(a?b:c の b の部分)の省略
-大きい方、小さい方を表す演算子
です。前者は、例えばnが0以上に限られているとして
a=n?:-1; // nが非0ならa=n, そうでなければa=-1
などと使えそうです。
後者は
x=i>?-i;
のようにするとiの絶対値が標準ライブラリ関数のabs()を使う...
***trueの否定の否定は1 [#hfbeab0f]
例えば、x=100のとき、xはtrue, !xはfalse, そして!!xはもち...
x: 100
!x: 0
!!x: 1
となるのです。0以外の数は真なので!0はなんでもいいのですが...
例えば、yはxがtrueなら1、falseなら0としたいとき、
y=x?1:0; // 三項演算子を利用
x&&y=1; // ifは使わない の章を参照
y=!!x;
のように、!!xを利用するのが一番短くなります。ちなみに、x...
y=x&1;
でもできますが、長さが同じですし!!xならどんなxにでも使え...
***返り値をうまく利用する [#h53cc0f1]
たいていのライブラリ関数はなんらかの値を返します。しかし...
以下に、普段は返り値を無視してしまいがちな関数をまとめま...
|関数|返り値|
|puts|非負の数とあるが、たいがいは出力した文字数(末尾の改...
|printf|出力した文字数を返す。|
|scanf|%で指定した型と一致した個数(正しく代入できた個数)...
|read, write|読み込み or 書き込みしたバイト数を返す。|
特に、scanfは、頻繁に以下のように使われます。
for(;~scanf("%d%d",&a,&b);)
...
入力が2つの整数(の複数行)の場合にこのようにするとどうなる...
***続く [#lb4e06ed]
続く
**アルゴリズムの改善 - ケーススタディ [#p801e95c]
余裕があればやります
ページ名:
