2.2 AOJ-0000 to 0005 - 技術的なやつ

POJが重すぎて繋がらないので、AOJ(http://judge.u-aizu.ac.jp/onlinejudge/index.jsp)に浮気した。問題文も日本語だし、難易度も低いし。あの会津大学が主催してるらしい。

で、練習問題を数問解いた後、レーティングに反映される問題を6問ほど解いた。

0000

九九の表を出力する問題。懐かしい。

0001

入力された10整数のうち、大きいものから3つ出力する問題。
バブルソートをちゃちゃっと書けるようになっておけば楽勝。バブルソートは4行で書けるので、それで解ける問題なら実装が面倒なクイックソートとかより経済的。ただ、ライブラリは存在する気がする。
大きい順でソートするバブルソート。

void bubble_sort(int *data, const int data_num){
	for(int i=0; i<data_num; ++i){
		for(int j=0; j<data_num-i-1; ++j){
			if(data[j] < data[j+1])	swap(data[j], data[j+1]);
		}
	}
}

0002

入力した2整数の和の桁数を表示する問題。
以下の関数で8ケタまで求められる。

int check_keta(int n){
	int i;
	for(i=1; i<9; ++i){
		if(n/(int)pow(10, i) == 0)	break;
	}
	return i;
}

ホントはbreakをreturnに変えて、intをforの中で宣言してもっとスマートにしたかったが、「returnせずに終了する可能性がある」ってg++に怒られた(警告)ので泣く泣く書き換えた。

0003

入力した3整数で直角三角形が作れるか、という問題。
最も大きい数を斜辺とした直角三角形を考えれば良い。バブルソートで3整数を整理すればスムーズに処理できる。

0004

$ax+by=c, dx+ey=f$
連立方程式を解いてください。ただし、解は一意に与えられますよ、とのこと。
行列使って計算するのが早い。即座に、以下のように解が導き出せる。
$x=\frac{ce-bf}{ae-bd}$
$y=\frac{-cd+af}{ae-bd}$
解は一意に与えられるとのことなので、ae-bd=0は無いと考えれば良い。
さて、解は小数第3位まで表示するのだが、その関係で「-0.000」なる出力が為されることがある。これはWrong Answerとなるので、abs(x) < 0.0005のときはx=0とするなどすると良い。

0005

GCDとLCMを求める問題。
GCDに関しては、ユークリッドの互除法が有名なので、それを使う。
LCMに関しては、2数をA,B、GCD=Gとすると、
$L=\frac{AB}{G}$
となることを用いて導出する。

GCDは再帰関数の良い練習問題として有名。
LCMのこの計算順序は、オーバーフローを防ぐため。

int gcd(int a, int b){
	if(b == 0)	return a;
	else	return gcd(b, a%b);
}

int lcm(int a, int b){
	return a/gcd(a,b)*b;
}