珠玉のプログラミング 2章 問題3 回答

icfp-pcの時に個人的に出された課題図書(のうちの1冊)

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

の,「配列の要素を任意の数だけ左にずらすコードを二通り書け」という問題を解いてみた.
アルゴリズムの大まかな内容は本文中に書いてあるのでコーディングだけの問題.
個人的にSTL禁止なので手書きした.

int gcd(int x, int y){
	while(x!=y){
		if(x>y) { x-=y; }
		else    { y-=x; }
	}
	return (x);
}

bool array_rotation1(int * xs, int n, int i){
	if(n==i || i==0){
		return true;
	}
	i %= n;
	for(int m=0; m<n/(n/gcd(n,i)); m++){
		int temp = xs[m];
		int j;
		for(j=1; (i*j+m)%n!=m; j++){
			xs[(i*(j-1)+m)%n] = xs[(i*j+m)%n];
		}
		xs[i*(j-1)%n+m] = temp;
	}
	return true;
}

大体本家と同じになったけど,n/(n/gcd(n,i))のあたりから必死さがにじみ出てますｗ
gcd(n,i)と同じだからそれ…

bool array_rotation2(int * xs, int n, int i){
	if(n==i || i==0){
		return true;
	}
	i %= n;
	int les;
	int offset;
	if( i<=n/2 ){
		offset = 0;
		les = i;
	}else{
		offset = n-i;
		les = n-i;
	}

	int temp;
	for(int j=0; j<les; j++){
		temp    = xs[j];
		xs[j]   = xs[n-les+j];
		xs[n-les+j] = temp;
	}

	if(i*2==n){
		return true;
	}else{
		if(i<=n/2){
			return array_rotation2(xs+offset, n-les, les);
		}else{
			return array_rotation2(xs+offset, n-les, n-les-les);
		}
	}
}

やっぱり本家の記述の方がかなり簡素に書かれてたorz(特にarray_rotation2の方)
素直にやるなら引数が4つ必要だったけど,
呼び出す側に一段関数を挟むのがイヤだったので無理矢理呼び分けてる.
本家のコードのキモは配列用のswapを使うことだけど,

void swap(int * xs, int a, int b, int m){
    for(int i=0; i<m; i++){
        int temp = xs[a+i];
        xs[a+i] = xs[b+i];
        xs[b+i] = temp;
    }
}

こんなん思い付かないだろ….