長さ n の配列 a の内容を,要素 k 個分だけ後ろにずらす関数 arrayRotate(int a[], int n, int k) を作れ。ただし,長さ n の配列の終端からはみ出た部分は,ずらすことによって出来た先頭の空き部分にもってくることとする。
すなわちa[0], a[1], ..., a[n-k-1] の内容をそれぞれ a[k], a[k+1], ..., a[n-1] へ移し,a[n-k], a[n-k+1], ..., a[n-1] の内容をそれぞれ a[0], a[1], ..., a[k-1] へ移す。
この問題は,以外と難問である.二つの変数 x, y の値を交換するには,値の待避場所 z を用意して, z = x; x = y; y = z; と,3回の代入が必要であるが,この問題は,それよりもさらに複雑である.
a[0] の値を a[k] に移すには,その前に a[k] の値を a[k+k] に移すか,あるいはどこかに待避させる必要がある.a[k+k] に移すとすると,その前に a[k+k] の値を a[k+k+k] に移すか,あるいは待避させる必要がある....これを最後まで続けるのは大変である
この堂々回りを回避して、簡単にコーディングする一つの方法は,配列 a の内容を直接 a 自身に書き込むのではなく,他の配列,たとえば b に移してから a に書き込むことである.この部分だけをコーディングすると次のようになる.
for (i = 0; i < n-k; i++) { b[i+k] = a[i]; } for (i = n-k; i < n; i++) { b[i-n+k] = a[i]; } for (i = 0; i < n; i++) { a[i] = b[i]; }
しかし,これを関数 arrayRotate の一部分としてみたとき,配列 b
(これは当然,関数のローカル変数である)の大きさをどのようにとれば良いのかが問題となる.C言語では,配列のサイズはコンパイル時に決まる定数でなければならないから,この問題に対処するには,無駄かも知れないけど十分に大きなサイズをとっておくか,
malloc などを用いて,動的にメモリを割り当てるか,どちらかしかない.
(みなさんが使っている gcc では,配列のサイズを変数で指定することが許されているが,他の一般的なCコンパイラでは許されない)
そこで,このような待避のための配列を用いない方法を考える.
その一つの方法は,練習問題1で作成した,配列の内容を逆順に並べ替える関数 arrayReverse を用いることである.次の図で見る通り,まず,全体を逆順に並び変えて,次に,前部の k 個を逆順に並べ替え,そして,後部の n-k 個を逆順に並び替えると,目的の操作が得られる.
この方法で,目的の関数を作ると,待避のための配列が不要だし,コーディングも次のように驚くほど簡単になる.
void arrayRotate(int a[], int n, int k) { arrayReverse(a, n); arrayReverse(a, k); arrayReverse(a+k, n-k); }
ここで,a は a[0] を指すポインタであり, a+k は a[k] を指すポインタである.したがって, arrayReverse(a, k) は a[0] から k 個の部分を逆順にして, arrayReverse(a+k, n-k) は a[k] から n-k 個の部分を逆順にする.
先ほどの,arrayReverse を用いて作成した関数は,非常に簡潔であり,待避用の配列も不要であることから,優れたコーディングと言える.しかし,その動作を詳しく見てみると,たとえば a[0] を一度 a[n] に移した後 a[k] に移すという,無駄な動きが見られる.
そこで,配列要素の代入が全体で何度行われているかを数えてみる.arrayReverse(a, n) 内には代入が約 n 回あり, arrayReverse(a, k) には約 k 回,arrayReverse(a+k, n-k) には約 n-k 回あり,計約 2n 回の代入が行われている.
このレポート問題の場合には,データ型が int なので,代入の時間は気にするほどではない.しかし,データ型によっては,代入に非常に多くの時間がかかることもある.
配列要素の代入の回数を最小にするには,配列要素の内容が,どのように動くのかを,理論的に追って行く必要があり,それのコーディングは,
n と k との最大公約数を用いた,複雑なものになる.
int gcd(int x, int y) { int r; while (y != 0) { r = x % y; x = y; y = r; } return x; } void arrayRotate(int a[], int n, int k) { int d, i, j, mk; int b; if (n == 0 || k == 0) return ; d = gcd(n, k); mk = (n-k) % n; /* mk = -k (mod n) */ for (i = 0; i < d; i++) { b = a[i]; for (j = 1; j < n/d; j++) { a[(i + (j-1)*mk) % n] = a[(i + j*mk) % n]; } a[(i + k) % n] = b; } }
gcd(x, y) は整数 x, y の最大公約数を返す関数である.この関数は,ユークリッドの互除法と呼ばれるアルゴリズムを使用している.
arrayRotate の中には二つの for 文がある.外側の for 文は d 回の繰り返しを行う.その中で配列要素の代入が n/d + 1 回行われている.したがって,全体として d( n/d + 1 ) = n + d 回の代入が行われている.通常,二つの整数の最大公約数はそれほど大きくはない(たとえば, 100 以下の二つ整数の最大公約数は,平均 3.1 )ので,代入の回数は約 n 回であると言える.
プログラム中の mk = (n-k) % n という値をもった変数 mk は,-k (mod n) の値である.C言語の剰余演算子 x % y は,x の値が負のときには負の値を返すので,注意が必要である.