巡回的な添字(剰余算 % の活用)

時計の文字盤の数字のように,環状に並んだ n 個の物がある.それら一つひとつを表すデータを配列 array の各要素に入れたとする.

巡回的な物

この場合,最後の要素 array[n-1] が表す物の次には array[0] が表す物が来る. すなわち,この配列の添字は ..., n-3, n-2, n-1, 0, 1, 2, 3, ..., n-3, n-2, n-1, 0, 1, 2, 3, .... と巡回的に動くと思ったら良い.

巡回的な配列

このような巡回的な添字を扱うのに便利なものが剰余算演算子 % である.a % b は a を b で割ったときの余りとなる.

 次の問題を考えてみよう

 整数型配列 array の内容を, array[k], array[k+1], ..., array[n-2], array[n-1], array[0], array[1], ..., array[k-2], array[k-1] の順番で, array[k] から始めて一巡するように表示する.

array[k] から配列の終わりまでと,配列の最初から array[k-1] までの部分に分けて表示すると,次のように二つの for 文で書くことになる.

    for (i = k; i < n; i++) {
        printf("%d ", array[i]);
    }
    for (i = 0; i < k; i++) {
        printf("%d ", array[i]);
    }

ところが,これと同じことが,剰余演算子 % を用いると,次のように一つの for 文でできる.

    for (i = 0; i < n; i++) {
        printf("%d ", array[(k+i) % n]);
    }

または、次のようにも書ける。

    for (i = k; i < k+n; i++) {
        printf("%d ", array[k % n]);
    }

 上の問題では,% の有り難みが良く分からないが,次の問題を考えてみると,良く分かる.

 長さ n の整数型配列 array の array[k] から始めて,d ごとの要素を e 個,すなわち array[k], array[k+d], array[k+d*2], array[k+d*3], ..., array[k+d*(e-1)] を表示する.ただし,添字は巡回的であるとする.

巡回的な配列

これを行おうとするとき,配列の添字 k+d*i が末尾の添字 n-1 を超えるのはどれからか,ということが重要なこととなるが,それを表すのは面倒なことである.しかし,% を使うとそれを気にすることなく,次のように簡単に書き表わせる.

    for (i = 0; i < e; i++) {
        printf("%d ", array[(k + d*i) % n]);
    }

 このように, % は便利な演算子ではあるが,これを使うときに大切な注意事項がある.それは a % b の a や b が負の値であるときである.

 次のプログラムを実行してみよう。

main()
{
    int a;

    for (a = -10; a <= 10; a ++) {
        printf("%d ", a % 4);
    }
}

結果は,多分次のようになる(結果はコンパイラに依存する)。

 -2 -1  0 -3 -2 -1  0 -3 -2 -1  0  1  2  3  0  1  2  3  0  1  2

 ここで, a が負の数のときには, a % 4 の値は負の数になっていることに注意しよう.このことより, array[(.... ) % n] と書いたときには ... の部分が負にならないように注意する必要がある。

 先ほどの, array[k] から始めて d ごとの要素を e 個だけ表示する,ということをするとき, d が負の値だったとする.すなわち,配列中を,後ろに進むのではなくて前に進みながら表示するわけである.この場合,先ほどの array[(k + d*i) % n] では k + d*i の値が負となりえるので,うまく行かない.そのようなときには, 次のいずれかのようにすると良い.

array[((k + d*i) % n + n) % n]
array[(k + (d+n)*i) % n]

 ただし,二つ目のものは, -n <= d であるときに限る.

アドバンスドプログラミングのTOPページに戻る