珠玉のプログラミング 2章 問題3 回答
icfp-pcの時に個人的に出された課題図書(のうちの1冊)
珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造
- 作者: ジョンベントリー,Jon Bentley,小林健一郎
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/10
- メディア: 単行本
- 購入: 30人 クリック: 551回
- この商品を含むブログ (162件) を見る
アルゴリズムの大まかな内容は本文中に書いてあるのでコーディングだけの問題.
個人的に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))のあたりから必死さがにじみ出てますw
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; } }
こんなん思い付かないだろ….