わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

配列を写像として用いる例をもう一つ

昨日の授業で,簡単な単一換字暗号のプログラムを解説しました.
キーワードの一つは,「写像としての配列の利用」です.char encrypt_table[256];と配列変数を宣言して,encrypt_table['A']='I';と代入すれば,「Aを暗号化するとI」を実現したことになります*1.forやwhileの反復,そして代入文を使って,すべての文字について暗号化のルールを定めれば,配列が写像として使えるということです.
さらに,恒等写像や逆写像も必要になります.暗号化において恒等写像とは「何も変換しない写像」,あるいは,「xをxに変換する写像」です.逆写像は,「xを暗号化して,復号すると,もとのxに戻る」というものです.それぞれ,関数を定義しました.
プログラミングで,「写像としての配列の利用」をするケースは,他にもあります.2次元座標で,上下左右の4方向,または斜めを含めた8方向を表現するときです.
コードを書きましょう.

/* 4方向 */
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

こう定義したとき,dx[0]とdy[0]のペアは,右方向を表します.離散的な座標系なら「右隣」と言って差し支えありません.実座標なら,右方向を表す単位ベクトルを意味します.配列の中に入る値が1,2,3なら,それぞれ上,左,下方向となります*2
xとyに何か値が入っていて,x += dx[0]; y += dy[0]; とすると,これは x += 1; y += 0; と同じですので,「x座標を1増やして,y座標はそのまま」となり,結局,「一つ右に移動する」ことを意味します.
xとyに何か値が入っていて,方向を表す0から3までの値が変数dに格納されていれば,x += dx[d]; y += dy[d]; という書き方をすることもあります.
さらに,「座標(x,y)の上下左右の隣」は,for (d = 0; d < 4; d++)というforループの中で,x+dx[d]とy+dy[d]という二つの値によって得られます.配列を写像として用いるだけでなく,ループの中に入れて一括処理できるという,配列としてのメリットも活用しているのです.
dを方向(0から3までの値)とすると,d ^ 2は「逆方向」を表します.dが0,すなわち右のとき,d^2は2,だから左です.dが1,2,3のとき,d^2はそれぞれ3,0,1となり,やはりそれぞれ逆方向です.
斜めを含めた8方向だと,以下のようになります.方向dは,0から7までの値をとり,逆方向は,d ^ 4で求められます*3

/* 8方向 */
int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

*1:gccで-Wallオプションをつけてコンパイルすると,「array subscript has type `char'」という警告が出ます.考えてみれば,decrypt_table[ encrypt_table[i] ]=i;という代入文で,charがsigned charなら,encrypt_table[i]が負の数になり得るので,decrypt[負の数]=値;となる危険性があります.プログラムを改訂しとこう….

*2:ここでの上下は数学的な座標系によるものであり,画像や2次元のゲーム盤の上での処理だと,たいていの場合,上下が反対になります.

*3:配列の初期値を上手く並べると,4方向でも,8方向でも,逆方向は d ^ 1で求められます.