132件中 1-5件目     [ 1 2 3 4 5 6 7 8 9 10 ... ]

標準入力に何かを入力させて処理をするプログラムをデバッグする場合、何度も同じ入力を繰り返すことがよくある。そんなときには入力データをファイルとして用意して、パイプとリダイレクションを使ってファイルに入出力をすると便利だが、それ以外にもfreopen関数を使う方法もある。Windows上でVisual Studioのような統合開発環境を使って開発をしている場合には、こちらの方が便利かもしれない。


シェルソートは挿入ソートを改良したソートアルゴリズムで、データを間隔hごとのグループに分けてそれぞれ挿入ソートを行うという操作を、hを徐々に減らしながら繰り返しデータ全体をソートする。

シェルソートの実行例

単純に考えるとシェルソートは挿入ソートを繰り返し実行しているので挿入ソートよりも遅くなりそうだが、交換回数が少なくなるので高速にソートすることができる。 シェルソートでは間隔hの決め方が重要で、実際に実験してみたところ間隔hを変えるだけで実行速度に10倍以上の差が出た。


数値と文字を一対一で対応させ、数値を文字に変換したい場合、アルファベット(A~Z)を使うのであればC言語では以下のように書くことになる。

#include <stdio.h>

int main(){
	// A~Zを出力
	int i;
	for(i=0; i<=('Z'-'A'); ++i){
		printf("%c", 'A'+i); // 数値をアルファベットに変換
	}
	printf("\n");

	return 0;
}
ABCDEFGHIJKLMNOPQRSTUVWXYZ

与えられる数値が25以下であれば上記のコードで問題ないが、もっと大きい数値が与えられることも考えらるため、アルファベット小文字(a~z)やギリシャ文字(α~ω)、ひらがな(あ~ん)、カタカナ(ア~ン)などにも対応させたいことがある。

しかし、ギリシャ文字やひらがなのような2バイト文字でもアルファベットと同じように「'α'+i」や「'あ'+i」として文字が表示できるのか?という点が気になったので調べてみた。


今回はコンテスト終了まで残り24時間の時点で総合8位くらい(973852点)だったのでTOP3に入るのは無理だと思って諦めていたが、意外とスコアが伸びて最終的に学生部門で2位、総合部門で3位となった。

記念品と賞状

ソースコードはコンテストの結果発表ページに掲載されているのでそちらを参照。 (ソースコード上部のコメント内にアルゴリズムの解説あり。)

去年もコンテスト終了後に次回の参加者向けにアドバイスを書いたが、今年新しく学んだこともあるので今年も少し書いておこうと思う。


星のカービィやスマッシュブラザーズで有名なハル研究所の学生向けプログラミングコンテスト(公式ページ)が今年も開催される。今年の開催期間は、本日11月26日の12時から来年1月8日までとなっている。途中から参加することもできるので、興味のある学生は参加してみるといい経験になると思う。

(※私が去年参加した後の感想やアドバイスなどは『ハル研究所 プログラミングコンテスト2008で一位になった』を参照。)

私は、今年は忙しいのであまり時間を使えないと思うが、今年が参加できる最後のチャンスなので今年も参加しようと思う。参加名は、去年上位に入っておきながら変更するのもどうかと思ったが、今年は「nyama++」にした。


132件中 1-5件目     [ 1 2 3 4 5 6 7 8 9 10 ... ]