平成21年春期試験午後問題 問8
問8 データ構造及びアルゴリズム
次のプログラムの説明及びプログラムを読んで,設問に答えよ。
〔プログラムの説明〕
64(8×8)画素からなる表示領域がある。この表示領域中の一つの画素を指定して,その画素を含む同じ色の領域を,指定した色で塗り替えるプログラムである。
ある一つの画素について,その画素の上下左右の4方向に隣接した画素の中に同じ色のものがあれば,それらの画素は同じ色の領域内にあるものと判定する。このようにして領域内にあると判定された隣接する各画素について,同様の判定を繰り返し,指定した色で塗り替えていく。
〔プログラムの説明〕
64(8×8)画素からなる表示領域がある。この表示領域中の一つの画素を指定して,その画素を含む同じ色の領域を,指定した色で塗り替えるプログラムである。
ある一つの画素について,その画素の上下左右の4方向に隣接した画素の中に同じ色のものがあれば,それらの画素は同じ色の領域内にあるものと判定する。このようにして領域内にあると判定された隣接する各画素について,同様の判定を繰り返し,指定した色で塗り替えていく。
- 大きさ10×10の2次元配列 Image (各添字の範囲は0~9)を用意する。各画素の色は,配列 Image の一部(各添字の範囲は1~8)に保持する。
- 色は,黒( ),灰( ),白( )の3色で,それぞれを値1,2,3で表す。
- 塗り替えたい領域中の開始点を示す一つの画素を,変数 VS と HS で指定する。VSとHSは,その画素に対応する配列 Image の要素の縦と横方向の添字である。
- 塗り替えたい色を,変数 NC で指定する。
- プログラムは,Image[VS,HS] から現在の画素の色を取得し,その画素を含む同じ色の領域を,色 NC で塗り替える。
- 大域変数 Image,NC,VS,HS には,正しい値が設定されているものとする。
- 配列 VPos,HPos の添字は,1から始まる。
- 図1は,VS=5,HS=3として,Image[5,3] を塗り替えたい領域内の開始点に指定し,NC=1として,塗り替える色を黒( )に指定した場合の,プログラムの実行例である。
広告
設問
次の記述中の に入れる正しい答えを,解答群の中から選べ。
このプログラムに関する先輩技術者(以下,先輩という)と新入技術者(以下,新人という)の会話である。
このプログラムに関する先輩技術者(以下,先輩という)と新入技術者(以下,新人という)の会話である。
- 先輩:
- プログラムの動作を理解するには,処理の流れを追跡してみることが大切です。まず,画素の色がどのような順序で塗り替えられていくか,図1のデータが与えられたものとして,最初の五つが塗り替えられる順序を1,2,…,5で示してみてください。
- 新人:
- はい。追跡してみます。結果は,aのようになりました。
- 先輩:
- そうですね。では,プログラムを検討していきましょう。まず,元の画素数は8×8ですが,配列 Image の大きさは10×10で,行番号15~23で最外周の配列要素に値0を設定しています。これは何のための処理でしょうか。
- 新人:
- はい,bからです。しかし,表示領域の要素数64に対して,32の配列要素に値を設定するのは,随分無駄な処理のように思えます。
- 先輩:
- では,一般にm×n画素からなる表示領域を考えたとき,行番号15~23で値を設定する要素数は,どういう式で表せますか。
- 新人:
- はい,cとなります。ということは,表示領域の画素数m×nが大きくなるほど,この要素数は相対的に小さくなっていくのですね。
- 先輩:
- 次に,最外周の配列要素に設定する値について考えてみましょう。行番号15では,変数 Wall に値0を設定しています。与えられた仕様では,画素の色を表す値は1~3の範囲だからこれでよいのですが,もしも,符号なし8ビットで表せる値0~255がすべて色の指定に使えるとした場合,行番号15をどう変更したらよいですか。例を一つ挙げてみてください。
- 新人:
- 行番号15をdと変更するのも一つの方法です。
- 先輩:
- 次は,行番号12~14について考えてみます。これは何の処理ですか。
- 新人:
- 現在の色と同じ色で塗り替えようとしているなら,以降の処理をせずに呼出し元に戻ります。塗り替えても,結局元どおりなので無駄ですから。
- 先輩:
- それも理由の一つではあるけれど。では,このプログラムから行番号12~14を取り去ってみましよう。そして,図2の①~③に示す,1画素,2画素,3画素からなる三つの白色の領域の例について,同じ色で塗り替えようとした場合のプログラムの動作を追跡してみてください。変数 VS,HS には,太枠で示した画素を指定するものとします。
- 新人:
- では,追跡してみます。結果は,次の表のとおりです。この結果から,行番号12~14は省略できない必要な処理であることが分かりました。
a に関する解答群
b に関する解答群
- これらの要素が参照されることはないが,添字から表示領域内かどうかが分かる
- これらの要素も色NCでの塗替えの対象とすることで,処理を簡素化できる
- 配列Imageの各添字の範囲チェックを省略できる
- 配列VPosとHPosの各添字の範囲チェックを省略できる
c に関する解答群
- 2(m+1)(n+1)
- 2(m+n)
- 2(m+n+2)
- 2(m+n-2)
d に関する解答群
- ・Wall ← CC
- ・Wall ← NC
- ・Wall ← 256-CC
- ・Wall ← 255-NC
e,f に関する解答群
- 仕様どおりに同じ色で塗り替えて正しく終了する。
- 塗替えは一度も実行せずに終了する。
- 塗り替えるべき領域に含まれない周辺の画素まで塗り替えて終了する。
- 変数Moreの値が増加していき配列の添字の上限を超える。
- 変数Moreの値は一定値以下であるが処理が無限にループする。
解答選択欄
- a:
- b:
- c:
- d:
- e:
- f:
- a=イ
- b=ウ
- c=イ
- d=イ
- e=ア
- f=オ
解説
この設問の解説はまだありません。広告