[programming]配列の要素を回転させるプログラム

最近は友達から借りたプログラミングの本を読んで時間を潰すことが多い．どれも難しい問題ばっかりで理解するのに苦労する．今日はその中から1つ問題をチョイス．

「要素がn個の配列をi要素分だけ回転させる(後ろに持っていく）プログラムを書きなさい」っていう問題がある．ようは，

1,2,3,4,5,6,7,8,9,10

と入ってる配列を「3回転させてね♪」と指定したら，

4,5,6,7,8,9,10,1,2,3

とすればいいので，例えば以下みたいなプログラムのように，1回ずつ移動させる関数を定義し，その関数を3回呼び出せば実現できる．

・・・
int a[n];  //要素n個で配列を定義
・・・
int func(){
 int tmp = a[i];
 int i;
 for(i=0; i< n; i++){
   if(i==n-1) a[i] = tmp;
   else a[i] = a[i+1];
 }
}

しかし，問題には条件があって，「メモリを数十バイトしか使わずに実行時間もnに比例するだけ」のプログラムにしないといけない．このプログラムだとnに比例しないのでダメなのである(´・ω・｀) 配列を複数個用意するなんてもっての外である．



じゃあ実際にどうやってそれを実現するのかというと，本に書いてあるヒントでは，a[0]を1時保管用のtに入れておき，その後はa[0]にa[i]を入れる．次はa[i]にa[2i]を，a[2i]にa[3i]・・・てな感じで移していく．つまり，3つ移すのなら3つ置きにずらしていけばいいということですな，なるほどぅ

で，書いたのがこれ

 for(m=0; m< gcd(n, i); m++){
   //最大公約数に達するまでm番めのグループを移動する
   tmp = a[m]; //一時保管庫へ
   j = m;      //転送先を初期化
   while(1){
     k = j;      //転送先をセット
     j = j + i;  //転送元をセット
     if(j< n){
       a[k] = a[j];  //移す
     }else{          //転送元添字がn以上だったら
       j = j%n;
       if(j==m){     //転送元添字がmと同じなら
       a[k] = tmp; //一時保管用のを移す
       break;
     }
     a[k] = a[j];
   }
 }

なんか，もうちょっとまとまって書けないのかねぇ(´・ω・｀)
本のヒントの通りに書いたわけだが，for文で最大公約数に着目してループしている．ここがどうしても理解できないorz　確かに移動できてるんだけどねぇ

bloggerを使ってみる

ども，かわらです.

プライベートなことは今まで通りmixiでやっていくとして，自分が経験した技術関係のログは外部のブログにしようと思って，googleのbloggerを利用することにしますた．どうぞヨロシク(・∀・)

まあ，仕事が本格的になってくると書く暇がなくなる気がするので，実際にこのブログを運用していけるかどうかは不明ですががががｇ

それでは