やねう企画入社試験・自分の解答と解説

http://d.hatena.ne.jp/yaneurao/20051006#p1
解禁になったようなのでオレの入社試験の解答を公開。
問１

//
//	問1.
//	次のC言語のプログラムを最適化せよ。
//	ただしint型は無限長のbitを持つと仮定して良い。
//

//----
//	この結果は関数gとfが引数を2進数のビットの立っている位置として、
//	その立っているビットの位置に対応するビット値を返す関数と判断しました。
//	その考えに基づき、シフトを使用して処理を単純化することとしました。
//----

#include 

int g(int N){

	// 引数が0の時はビットシフトしない（ビットが立っていない）ので0をリターン
	if(N == 0){
		return 0;
	} else {
		// スタートがすでに1ビットなので引数が0以上の場合はN-1で”シフトするビット数”を実現する
		return 1 << (N-1);
	}
}

int main(){

	return g(10000); 

}

　解説：簡単な数を関数gの引数として渡すと、リターンされる値が 1, 2, 4, 8 ...となることに気が付いた。
この動きはとどのつまり二進数の桁上がりなわけで、二進数ならばビットシフトでこの処理は最適化されるであろう。
と、考えた。
……が、どうもやね師匠の解説を読むともっと数学的な証明が必要らしい……。たしかに、ある現象を処理するプロセスの最適化はキチンとできたが、やね師匠の見たかったであろう数学的な思考はできていなかったと＿|￣|○

問２（再帰版）

//
//	問２
//	いま、aを迷路と見立てる。a[x,y]が0の箇所は歩けて、1の箇所は歩けない。
//	迷路の外周は1であることが保証されているとする。
//	a[x,y]をスタート地点として、この迷路を歩いていくときの、
//	歩ける箇所の数を求める関数W(a,x,y)を書け。(上の例では、W(a,1,1)=15)
//	ただし、再帰を使ったプログラム、再帰を使わないプログラムを用意すること。
//	また、配列aの内容は破壊しても構わない。
//
//	【再帰プログラム版】
//

//----
//このプログラムの条件
//・ x y に関しては0・7の値をとらない（外周が初期値にこない）こと
//----


#include 

int W(int a[][7], int x, int y) {
	
	if(a[x][y] == 0){
		// 調査対象のの領域を-1とすることで「調査済み」とする
		a[x][y] = -1;
		// 調査対象の領域の周囲を調査対象として再帰呼び出しを行う
		return 1 + W(a, x + 1, y) + W(a, x - 1, y) + W(a, x, y + 1) + W(a, x, y - 1);
	} else {
		return 0;
	}

}


int main(void) {

	int a[7][7] ={
		{1,1,1,1,1,1,1},
		{1,0,0,0,0,0,1},
		{1,0,1,1,1,0,1},
		{1,0,0,0,1,1,1},
		{1,0,0,1,0,0,1},
		{1,0,0,0,1,0,1},
		{1,1,1,1,1,1,1}
	};
	
	W(a, 1, 1);
	
	return 0;
}

　迷路の探索。まず、与えられた座標の周りに進める道があるかどうかを考えた。そうすると、自分を中心に上下左右が動ける。そして、そのなかで道（0）があるのならばそこを中心にして、先ほどの座標以外で通れる道（0）があるかどうかを探索すれば歩ける道のみをカウントできるであろうと考えた。
あとはそれを再帰呼び出しし、注目した座標は道ではない（＝0ではない）という目印をつければそれでいいだろう。
という結論に達した。これが一番ラクだったな。。。

ここまでがオレの解けた解答。
これが採点されたのだが……。
ほぼドンピシャなソースコードのため添削されず＿|￣|○
再帰版ができているのならば非再帰版も書けて欲しかったという言葉を頂いた。
もっと精進せねば……。