平成２８年度春期午後のC言語問題である問９の私の解き方・考え方について解説していきます。
問題
IPAの公式サイトで公開されています。このページでは問９についての解説を行います。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2016h28_1/2016h28h_fe_pm_qs.pdf
問題の概要
フラクタル図形に関する問題です。フラクタル図形とは図形の一部を拡大すると再び同じ図形が現れる特徴を持つ図形です。
下がフラクタル図形の例で、深さ１の図形が集まって深さ２、深さ３の図形が形成されていることが分かると思います。
また深さ２の図形は深さ１の図形、深さ３の図形は深さ２の図形が集まって形成されていると見ることもできるのがフラクタル図形の特徴です。
生成パターンのサイズがM x Nとした時、深さdの時のフラクタル図形のサイズはM^d x N^d となります(^は累乗を表現しています）。
問題にあるプログラムはちょうど上の例のフラクタル図形を作成するものになっています。深さ１の図形を生成パターンとして２次元配列として保持しており、それを使用して任意の深さdのフラクタル図形を生成するプログラムになっています。
スポンサーリンク
設問１
斜線部を置換した結果はどこに反映されるかが問われている問題です。
この置換の仕方は[プログラムの説明]の(2)に記載されており、今回は①のケースにあてはまります。
この置換の仕方により深さd-1の図形から深さdの図形が生成されます。
設問１では斜線部がどこに置換されるかが答えになりますが、解答①と解答④は生成パターンよりサイズが小さいので間違いです。②は斜線部のちょうど左隣の＊が置換されたものになります。ですので設問１の答えは③になります。
設問２
設問２を解答するためにはまず生成パターンを見つけ出す必要があります。
目を凝らして見てみましょう。
どの生成パターンから図形が形成されているかが見えてくるはずです。下の図で深さ１の例で青色付いている図形が生成パターンですね。
あとはこのパターンを２次元行列で表現すれば良いだけです。２次元行列で表すとpat[2][3] = { {1, 1, 1}, {1, 0, 1}};となりますので、設問２の答えはpat[2][3] = { {1, 1, 1}, {1, 0, 1}};となります。
設問３
プログラムの穴埋め問題ですね。まず[ a ]を解くためにprint_frac関数側をみていきましょう。
まずオレンジ枠部分に注目します。
ここはループ内でputchar関数等を実行していることから、行数 x 列数分の＊ or 空白を表示することで図形を生成しているプログラムと推測できます。
この処理をするためには深さdの時の行数rnと列数cnをこの処理よりも前に計算しておく必要があります。
そう考えると[ a ]が含まれる緑枠部分は行数rnと列数cnを計算している部分と推測できます。
また、問題の概要でも説明したように、生成パターンのサイズがM x Nとした時、深さdの時のフラクタル図形のサイズはM^d x N^d となります。
プログラムの青枠内で、生成パターンの行数と列数をp_rnとp_cnに格納していますので深さdの時のフラクタル図形のサイズはp_rn^d x p_cn^d で計算可能です。
このp_rn ^d は「1にp_rnをd回掛ける」ことで計算可能です。
これらを頭に置いて解答群を見てみると、
アとイは計算したいrnとcnにではなくp_rnとp_cnに結果を格納しているので間違いであり、ウは累乗を計算する処理ではないので間違いです。エは累乗を計算する処理になっています。
したがって[ a ]の答えはエとなります。
続いて[ b ]、[ c ]、[ d ]を解いていきましょう。
まず[ b ]を見ていきます。[ b ]は深さdが0の時の関数の戻り値になります。
深さが0の時はフラクタル図形は１行１列の＊からなる図形になりますので、深さ0で実行された場合はexists_at関数は必ず＊を示す1を返却する必要があります。
ですので[ b ]の答えは1となります。
続いて[ c ]を見ていきましょう。[ c ]はexists_at(i / p_rn, j / p_cn, d – 1)の戻り値が0の時に返却する値になります。
ここで(i / p_rn, j / p_cn)座標がどんな座標かについて一旦説明したいと思います。
この座標は下の図のように、(i, j)座標を置換により生成した座標(深さd-1の図形における座標)になります。ですので、i / p_rnとj / p_cnを何回も繰り返せば、置換元の座標をどんどん辿っていくことが可能です。
これを理解した上で設問を見てみると[ c ]とは、生成元の座標が空白のときのexists_at関数の戻り値となります。[プログラムの説明]の(2) – ②より、生成元が空白であれば、生成先の(i, j)座標も必ず空白となります。つまりexists_at関数は空白を表す0を返す必要があります。したがって[ c ]の答えは0となります。
[ d ]は、深さdが0以外で、(i, j)座標の生成元が空白でない場合のexists_at関数の戻り値となります。
生成元が空白の場合のフラクタル図形の生成規則が[プログラムの説明]の(2) – ②で説明されていましたが、空白以外の場合は[プログラムの説明]の(2) – ①で説明されています。ここを読めば「生成元が空白でない場合は生成パターンがそのままコピーされる」ことがわかると思います。
したがって、フラクタル図形の(i, j)座標は生成パターン上のいずれかの座標の値がコピーされて生成されたと考えられます。
なので、(i, j)座標が＊であるか空白であるかは(i, j)座標が生成パターン上のどの座標がコピーされてきたかを調べれば分かります。
生成パターンもしくは生成パターンと同じ大きさの図形がコピーされてフラクタル図形が生成されていると考えると、(i % p_rn, j % p_cn)座標が(i, j)座標にコピーされてきた生成パターン上の座標となります。
したがって、[ d ]の答えはpat[i % p_rn][j % p_cn]です。
スポンサーリンク
解いてみた感想
問題は解いていて面白かったです。フラクタル図形って名前は聞いたことがあったのですが、具体的な特徴などは知らなかったので勉強になりました。
ただ再帰処理が出てきたのでちょっと難易度高く感じました。後から考えたらなんてことはないのですが。
あとは累乗の計算や％を使った計算などは実際にプログラミングしてる人でないともしかしたら答えを導く出すの大変かもしれませんね。
割とプログラミング慣れしている人に有利な問題だと感じました。
★オススメページ★
下記ページから他の回の解説もたどれます。他の回のC言語問題の解き方がわからない場合は是非読んでみてください！
基本情報技術者試験 午後問題「C言語」過去問の解き方 解説 まとめ
本ページの図・プログラム・問題文について
図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。
出典：平成２８年度 春期 基本情報技術者試験（FE）試験区分 午後 問９
