基本情報技術者 2016年 春期 午後 問09
次のCプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
〔プログラムの説明〕
図形の一部を拡大すると、再び同じパターンの図形が現れる自己相似性をもつ図形を、フラクタル図形と呼ぶ。関数print_fracは、文字“*”及び空白文字を二次元の格子状に並べてフラクタル図形を描画するプログラムである。
(1) 関数print_fracが描画するフラクタル図形の例を、図1に示す。
① 深さが0の図形は、1行1列の文字“*”から成る図形である。
② 深さが1以上の図形は、深さが0の図形に対して、(2)で説明する生成規則を、深さの回数だけ繰返し適用して得られる図形である。
(2) 深さがd（1以上）の図形は、深さがd−1の図形を構成する一つ一つの文字を、文字“*”であるか空白文字であるかに応じて、図2に示す生成規則のとおりに、文字の行列で置換したものである。
① 文字“*”の部分は、生成パターンと呼ぶ文字の行列で置換する。
② 空白文字の部分は、生成パターンと同じ大きさで全ての要素が空白文字の行列で置換する。
(3) 生成パターンは、二次元の配列変数patによって与える。patの各要素の値は、空白文字を表す0、又は文字“*”を表す1である。patの行数、列数及び内容を変更することで、異なるフラクタル図形を描画することができる。
(4) 関数print_fracの仕様は次のとおりである。
機能：深さがdのフラクタル図形を描画する。
引数：d フラクタル図形の深さ
(5) 関数print_fracで使用している関数exists_atの仕様は次のとおりである。
機能：深さがdのフラクタル図形のi行j列目が空白文字であるか文字“*”であるかを判定する。
引数：i 行数（一番上の行を0行目とする）
j 列数（一番左の列を0列目とする）
d フラクタル図形の深さ
返却値：判定結果（0：空白文字、1：文字“*”）
ここで、関数の引数に誤りはないものとする。
設問1：
問題文を見る 深さが2の図形と深さが3の図形は次のとおりである。深さが3の図形において、深さが2の図形の斜線部を置換した部分として正しい答えを、解答群の中から選べ。
解答群
ア：①
イ：②
ウ：③
エ：④
模範解答
ウ
解説
解答の導き方
深さが2の図形で斜線が付いているのは、3行2列目の「*」です。この1つの文字が、深さが3の図形のどこに移るかを考えます。
- 深さが2の3行目は、深さが3では5行目と6行目に対応します。
- 深さが2の2列目は、深さが3では3列目と4列目に対応します。
したがって、斜線部を置き換えた部分は、深さが3の5～6行目、3～4列目にある2行2列の範囲です。
斜線部は「」なので、図2の生成パターンで置き換えます。パターンの左上、右上、左下には「」があり、右下は空白です。深さが3の図形でも、該当範囲は上の行が「」「」、下の行が「*」「空白」になっています。この位置を示すものは ウ（③） です。
誤りやすいポイント
- 斜線部を深さが2の図形の中で探すだけでなく、深さが3の図形に置き換えた後の位置まで追う必要があります。
- 深さが2から深さが3への置換は1回分です。したがって、斜線部1マスは2行2列に置き換わります。4行4列ではありません。
- 空白も同じ大きさの範囲に置き換わりますが、その範囲はすべて空白になります。斜線部は「*」なので、生成パターンが現れます。
FAQ
Q: 深さが2の3行目は、深さが3の何行目に対応しますか？
A: 1行が2行に置き換わるため、深さが2の3行目は深さが3の5行目と6行目に対応します。
A: 1行が2行に置き換わるため、深さが2の3行目は深さが3の5行目と6行目に対応します。
Q: 深さが2の2列目が、深さが3の3列目と4列目に対応するのはなぜですか？
A: 1列が2列に置き換わるためです。深さが2の1列目は深さが3の1～2列目、2列目は3～4列目に対応します。
A: 1列が2列に置き換わるためです。深さが2の1列目は深さが3の1～2列目、2列目は3～4列目に対応します。
関連キーワード: フラクタル、自己相似性、生成規則、二次元配列、行列
設問2：
問題文を見る 配列変数patを変更して、深さが3の図形を描画したところ、次のとおりになった。配列変数patの変更内容として正しい答えを、解答群の中から選べ。
解答群
ア：int pat[2][3] = { { 0, 1, 0 }, { 1, 0, 1 } };
イ：int pat[2][3] = { { 1, 1, 1 }, { 1, 0, 1 } };
ウ：int pat[3][3] = { { 0, 1, 0 }, { 1, 1, 1 }, { 1, 0, 1 } };
エ：int pat[3][3] = { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 0, 1 } };
模範解答
イ
解説
解答の導き方
まず、描画結果の大きさから、配列変数patの行数と列数を絞ります。
生成パターンが縦に行、横に列だとします。深さが1増えるたびに、各マスが行列のマスに置き換わります。そのため、深さが3の図形は縦に行、横に列になります。
問題の図形は8行×27列です。したがって、
- なので、
- なので、
となります。配列が2行3列なのは、アとイです。3行3列のウとエでは、深さが3の図形は27行27列になるため、図形の大きさと合いません。
次に、アとイのどちらかを、描画結果の並び方で判定します。
深さが3の図形は、1行目の27列すべてが「＊」です。生成パターンの一番上の行に0があると、その位置に対応する部分は空白になります。1行目には空白がないので、生成パターンの一番上の行はすべて1でなければなりません。
アの一番上の行は「0、1、0」ですが、イの一番上の行は「1、1、1」です。よって、一番上の行の条件に合うのはイです。
また、深さが3の5行目は、1～9列と19～27列が「＊」で、10～18列が空白です。これは、生成パターンの下の行が「1、0、1」である形と合います。アとイはどちらもこの下の行が同じなので、1行目の結果で区別できます。
誤りやすいポイント
- 行数と列数を同じものとして考えないようにします。生成パターンが2行3列なら、深さが3の図形は縦に行、横に列です。
- 1行目のマスがすべて「＊」だからといって、生成パターンのすべてのマスが1とは限りません。この条件から分かるのは、生成パターンの一番上の行がすべて1だということです。
- 深さが3の図形では、生成パターンを3回使います。1回目だけで図形全体の形が決まるわけではありません。
FAQ
Q: なぜ生成パターンが2行3列だと、深さが3の図形は8行27列になるのですか？
A: 置き換えを1回行うごとに、行数は2倍、列数は3倍になります。3回繰り返すので、行数は、列数はです。
A: 置き換えを1回行うごとに、行数は2倍、列数は3倍になります。3回繰り返すので、行数は、列数はです。
Q: 1行目がすべて「＊」なら、生成パターンの一番上の行がすべて1だと分かるのはなぜですか？
A: 一番上の行を作るときは、生成パターンの一番上の行が使われます。その一部に0があれば、出力にも空白ができます。図の1行目には空白がないため、一番上の行はすべて1です。
A: 一番上の行を作るときは、生成パターンの一番上の行が使われます。その一部に0があれば、出力にも空白ができます。図の1行目には空白がないため、一番上の行はすべて1です。
Q: アとイは、どこが違いますか？
A: どちらも2行3列で、下の行は「1、0、1」です。違うのは一番上の行で、アは「0、1、0」、イは「1、1、1」です。1行目がすべて「＊」という結果に合うのはイです。
A: どちらも2行3列で、下の行は「1、0、1」です。違うのは一番上の行で、アは「0、1、0」、イは「1、1、1」です。1行目がすべて「＊」という結果に合うのはイです。
関連キーワード: フラクタル、二次元配列、配列の添字、再帰処理、整数除算
設問3：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：p_rn += rn; p_cn += cn;
イ：p_rn *= rn; p_cn *= cn;
ウ：rn += p_rn; cn += p_cn;
エ：rn *= p_rn; cn *= p_cn;
b〜dに関する解答群
ア：0
イ：1
ウ：pat[i][j]
エ：pat[i % d][j % d]
オ：pat[i / d][j / d]
カ：pat[i % p_rn][j % p_cn]
キ：pat[i / p_rn][j / p_cn]
模範解答
a：エ、b：イ、c：ア、d：カ
解説
解答の導き方
まず、関数print_fracは、深さに応じて図形の行数と列数を決め、その後、各マスが文字「*」か空白かを調べて描画します。ここでは、図形の大きさと、各マスの状態の調べ方を分けて考えます。
1. 図形の行数と列数を求める
プログラムでは、行数と列数をそれぞれ、とし、最初はどちらもにしています。深さがの図形は1行1列だからです。
生成パターンは、配列patの行数、列数でできています。この問題では、どちらもです。図形を1段階深くするたびに、それまでの各マスが、行方向に個、列方向に個のマスへ置き換わります。
そのため、行数と列数は、それぞれ生成パターンの行数・列数を掛けて求めます。
したがって、繰返しの中ではにを掛け、にを掛けます。空欄aには、行数と列数を掛け算で更新する処理が入ります。
2. 深さが0のときの値を決める
関数exists_atは、指定したマスが空白なら、文字「*」ならを返します。
深さがの図形は、1マスだけの文字「*」です。したがって、のときはを返します。空欄bは、解答群のイです。
3. 深さが1以上のとき、対応するマスを調べる
問題文には、深さがの図形は、深さがの図形の各文字を、生成規則に従って置き換えて作るとあります。そこで、まず、調べたいマスが、深さの図形のどのマスから作られたかを調べます。
現在の行番号をで割った整数部分が、置き換え前の図形での行番号です。同じように、列番号をで割った整数部分が、置き換え前の図形での列番号です。プログラムの再帰呼出し（関数が自分自身を呼び出す処理）は、この対応を使っています。
次に、置き換え前のマスが空白だった場合を考えます。問題文には、空白文字は「全ての要素が空白文字の行列」で置き換えるとあります。つまり、置き換え前のマスが空白なら、その中のどの位置も空白です。空欄cにはが入ります。解答群のアです。
置き換え前のマスが文字「*」なら、現在のマスは生成パターンpatのどの位置に当たるかを調べます。現在の行番号をで割った余りが、生成パターンの行番号です。列番号をで割った余りが、生成パターンの列番号です。
したがって、調べる値はです。空欄dには、解答群のカが入ります。
4. 座標を使って動きを確かめる
深さがの図形で、3行目・2列目、つまり、のマスを調べます。配列の添字は、問題文の説明どおり、最上段と最左列をとして数えます。
- 置き換え前の位置は、行目、列目なので、深さのです。
- 深さのは、深さのから作られています。深さのは文字「*」なので、深さでは生成パターンのを調べます。この値はです。
- 置き換え前のマスが文字「*」なので、深さでは生成パターンの位置を調べます。位置は行目、列目で、の値はです。
このため、深さのは文字「*」になります。
一方、深さのでは、置き換え前の位置である深さのが空白です。そのため、深さのそのマスも空白になり、生成パターンの値を調べる前にを返します。
誤りやすいポイント
- 行数・列数を増やすとき、生成パターンの大きさを足すのではなく、現在の行数・列数に掛けます。各マスがパターン全体に置き換わるためです。
- 親に当たるマスの位置と、生成パターン内の位置を混同しないようにします。割り算の商で親の位置を求め、余りでパターン内の位置を求めます。
- 親のマスが空白なら、子のマスも必ず空白です。この場合、生成パターンの要素を調べる必要はありません。
- 深さがの図形は空白ではなく、1マスの文字「*」です。再帰呼出しの終点となるため、ここでを返します。
FAQ
Q: なぜ現在の座標を割り算と余りで分けるのですか？
A: 割り算の商から、置き換え前の図形のどのマスに当たるかが分かります。余りから、そのマスを置き換えた生成パターン内のどの位置に当たるかが分かります。
A: 割り算の商から、置き換え前の図形のどのマスに当たるかが分かります。余りから、そのマスを置き換えた生成パターン内のどの位置に当たるかが分かります。
Q: 親のマスが空白なら、なぜ生成パターンを調べないのですか？
A: 空白のマスは、全てが空白の行列に置き換わるからです。生成パターンのどの位置に対応していても、結果は空白です。
A: 空白のマスは、全てが空白の行列に置き換わるからです。生成パターンのどの位置に対応していても、結果は空白です。
Q: 再帰呼出しは、いつ終わりますか？
A: 呼び出すたびに深さがずつ小さくなり、に達すると文字「*」を示すを返します。これが再帰呼出しの終了条件です。
A: 呼び出すたびに深さがずつ小さくなり、に達すると文字「*」を示すを返します。これが再帰呼出しの終了条件です。
関連キーワード: フラクタル、自己相似性、二次元配列、再帰呼出し、整数除算、剰余
