応用情報技術者 2016年 春期 午後 問03
ライフゲームに関する次の記述を読んで、設問1〜5に答えよ。
ライフゲームとは、数学者コンウェイが考案した、生命の誕生、生存、死滅などを再現したシミュレーションゲームである。マス目状の盤上の各マスに生命が存在でき、そのマス自身及び隣接するマスの状態によって次世代の誕生、生存、死滅が決まる。その条件を表1に示す。
なお、隣接するマスには、斜め方向のマスも含む。また、生命が存在するマスを“生のマス”、生命が存在しないマスを“死のマス”と呼ぶ。
〔4×4マスのシミュレーション〕
4×4マスの盤上における第3世代までのシミュレーションを図1に示す。
第1世代は、初期値として設定されたものである。例として、第1世代の2行目1列目のマスを考える。現在、このマスは死のマスである。このマスに隣接するマスを網掛けで示す。これら五つのマスの中に生のマスが三つある。これは表1の“誕生”の条件に該当するので、第2世代の2行目1列目のマスは生のマスになる。同様に、第1世代の各マスについて、そのマス自身及び隣接するマスの状態を確認することで第2世代が決まる。次の世代への状態の更新は、全てのマスについて同時に行われる。
〔盤上のマスのデータ構造〕
N×Nマスの盤上の状態を表現するデータ構造を考える。多次元配列が利用できないプログラム言語を考慮し、盤上の各マスの生死状態を管理するデータ構造として1次元配列mを用いる。配列mのデータ構造のイメージを図2に示す。
〔配列mを次世代に更新するプログラム〕
使用する定数、配列及び関数を表2に、配列mを次世代に更新する関数updateを図3に示す。
なお、関数に配列を引数として渡すときの方式は参照渡しである。
〔テストプログラム〕
図3のプログラムをテストするために、配列mに第1世代が与えられたときの第p世代が、机上で作成した正しい結果である配列rと等しいことを確認するプログラムを作成した。作成した関数shouldBeを図4に示す。ここで、pには2以上の整数が入る。
図3のプログラムが正しく動作する状態で図4のプログラムを実行したところ、テストが失敗した。原因を調査した結果、図4のケ行目に問題があることが判明したので、①プログラムを修正してテストを成功させることができた。
設問1：
問題文を見る模範解答
ア：×
イ：×
ウ：○
エ：○
解説
解答の論理構成
-
各マスに隣接する“生”マスの個数を数えます（上下左右斜めの8方向。盤端は盤外を数えません）。
- ア 周囲の“生”マス＝4個
- イ 周囲の“生”マス＝4個
- ウ 周囲の“生”マス＝3個
- エ 周囲の“生”マス＝3個
-
【問題文 表1】の規則を適用します。引用中の数字・語句は原文そのままです。
- 誕生規則 「死のマスに隣接する生のマスが三つならば、死のマスは次の世代では生のマスとなる。」
- 生存規則 「生のマスに隣接する生のマスが二つ又は三つならば、生のマスは次の世代でも生のマスである。」
- 過密規則 「生のマスに隣接する生のマスが四つ以上ならば、生のマスは過密によって次の世代では死のマスとなる。」
- 過疎規則は今回は該当なし（“一つ以下”のマスはない）
-
判定結果
- ア は“死”で4個 → 誕生条件を満たさず“死”のまま（×）。
- イ は“生”で4個 → 過密で“死”になる（×）。
- ウ は“生”で3個 → 生存し続ける（○）。
- エ は“死”で3個 → 誕生して“生”になる（○）。
以上より
ア：× イ：× ウ：○ エ：○
ア：× イ：× ウ：○ エ：○
誤りやすいポイント
- 盤端のマスは盤外を含めて8個そろわないため、実際に存在するマスだけを数えます。盤外を“死”として数えてしまうと誤判定になります。
- “誕生”と“生存”を混同しやすいです。誕生は“死”マス限定、かつ隣接“生”マスが「三つ」のみ。
- “生”マスの「三つ」は生存でも条件に含まれるため、現在の状態（生／死）を先に確認しないと判定を取り違えます。
FAQ
Q: 同時更新とは何を意味しますか？
A: 【問題文】にある「次の世代への状態の更新は、全てのマスについて同時に行われる。」のとおり、ある世代nの判定には世代nの状態だけを用い、途中で変化した結果を使ってはいけません。
A: 【問題文】にある「次の世代への状態の更新は、全てのマスについて同時に行われる。」のとおり、ある世代nの判定には世代nの状態だけを用い、途中で変化した結果を使ってはいけません。
Q: “過疎”と“過密”のどちらを優先しますか？
A: 優先順位はなく、条件を満たすかどうかで決まります。生マスで4個以上なら即“過密”、1個以下なら即“過疎”です。
A: 優先順位はなく、条件を満たすかどうかで決まります。生マスで4個以上なら即“過密”、1個以下なら即“過疎”です。
Q: 4×4以外のサイズでも規則は同じですか？
A: はい。【問題文 表1】の規則はN×Nどのサイズでも共通に適用されます。
A: はい。【問題文 表1】の規則はN×Nどのサイズでも共通に適用されます。
関連キーワード: セルオートマトン, 同時更新, 近傍数, 過密死, 誕生条件
設問2：
問題文を見る図2中のオに入れる適切な字句を答えよ。
模範解答
オ：(k−1)×N＋j
解説
解答の論理構成
- 【問題文】の図2には「行1・列1 m[1]」「行1・列2 m[2]」「行1・列N m[N]」「行2・列1 m[N+1]」「行2・列N m[2×N]」と具体例が列挙されています。
- これらを行番号 、列番号 で一般化すると、配列mの添字は
・行が1増えるごとに ずつ増加
・同じ行内では列番号に一致
という規則で並んでいると分かります。 - したがって基準位置（行1）の先頭m[1] から 行下へ移動すると を 回加算し、列位置は を足す形になります。
- 以上より「行k・列j」の要素は
と表されます。これが図2の オ に入る符号です。
誤りやすいポイント
- 0始まりと1始まりの添字を混同し、(k×N)+jや (k-1)×N+(j-1) とずらしてしまう。
- 行を先に掛けるとき括弧を忘れ、k-1×Nと計算順序を誤る。
- 行・列を逆に解釈してj×N+(k-1) としてしまう。
FAQ
Q: 行列を一次元配列に写像するときは常に になりますか？
A: 配列を1始まりで管理し、行を上から、列を左から増やす一般的な「行優先 (row-major)」配置ならば成立します。0始まりや列優先配置では式が変わります。
A: 配列を1始まりで管理し、行を上から、列を左から増やす一般的な「行優先 (row-major)」配置ならば成立します。0始まりや列優先配置では式が変わります。
Q: (k−1)×N＋jとN×(k−1)+jは同じですか？
A: 乗算は可換なので結果は同じですが、試験解答では【問題文】の記述に合わせて と書くのが安全です。
A: 乗算は可換なので結果は同じですが、試験解答では【問題文】の記述に合わせて と書くのが安全です。
Q: 行数や列数が可変でも式は変わりませんか？
A: はい。盤の一辺の大きさを表す定数Nをそのまま用いれば盤の拡大・縮小に関係なく同じ式で添字を計算できます。
A: はい。盤の一辺の大きさを表す定数Nをそのまま用いれば盤の拡大・縮小に関係なく同じ式で添字を計算できます。
関連キーワード: 配列添字, 行優先配置, 一次元配列化, オフバイワン, インデックス計算
設問3：
問題文を見る模範解答
カ：temp[c]と1が等しい
キ：(temp[i]と0が等しい)and(eと3が等しい)
ク：m[i] ← 1
解説
解答の論理構成
-
周囲の生きているマス数を数える部分
- 図3では隣接 8 マスを走査し、生きている場合に e ← e + 1 で加算します。
- “生きている”かどうかの判断は、更新前状態を退避したtempを参照すべきであり、式は
temp[c]と1が等しい
となります。これが[カ]です。
-
誕生判定（死→生）
- 表1の“誕生”条件は「死のマスに隣接する生のマスが三つならば、死のマスは次の世代では生のマスとなる。」
- i番目のマスが死（temp[i]と0が等しい）かつ生きている隣接マス数eが3のとき生にするので
(temp[i]と0が等しい)and(eと3が等しい)
が[キ]になります。
-
生存判定（生→生）
- 表1の“生存”条件は「生のマスに隣接する生のマスが二つ又は三つならば、生のマスは次の世代でも生のマスである。」
- 既に生（temp[i]と1が等しい）の場合はif-elseifのelseif節で処理され、条件式はコード内で既に与えられています。
- 条件を満たしたとき、新世代配列mに生を設定する文が必要であり、字句は
m[i] ← 1
となります。これが[ク]です。
-
以上より
- [カ] temp[c]と1が等しい
- [キ] (temp[i]と0が等しい)and(eと3が等しい)
- [ク] m[i] ← 1
が模範解答と一致します。
誤りやすいポイント
- 退避配列tempを使わずにmを参照してしまう
（同時更新を壊し、世代計算が逐次更新になってしまう）。 - “誕生”と“生存”の条件を混同し、e=3なのに元が生のマスだけを対象にしてしまう。
- “生存”条件でe=2 or 3の判定は正しくても、新世代配列mに値を代入し忘れる。
FAQ
Q: 退避用配列tempは必ずコピーでなくスワップでも良いですか？
A: はい。性能を優先する実装ではポインタを入れ替えても構いませんが、本問は“参照渡し”前提でコピーを採用しています。
A: はい。性能を優先する実装ではポインタを入れ替えても構いませんが、本問は“参照渡し”前提でコピーを採用しています。
Q: 盤面端のマスで配列外アクセスが起きませんか？
A: cが1以上 かつcがN×N以下 のチェックを行っているため安全です。
A: cが1以上 かつcがN×N以下 のチェックを行っているため安全です。
Q: “過疎”と“過密”を個別にコード化しない理由は？
A: 生存条件（e=2 or 3）を満たさない生マスは自動的に死へ更新されるので、過疎・過密を区別して書く必要がありません。
A: 生存条件（e=2 or 3）を満たさない生マスは自動的に死へ更新されるので、過疎・過密を区別して書く必要がありません。
関連キーワード: 隣接マス探索, 一次元配列インデックス変換, 同時更新, セルオートマトン, 条件分岐
設問4：
問題文を見る図3中のαの二つの条件のいずれかを満たすのはどのような場合か。単語“盤”及び“マス”を用いて30字以内で述べよ。
模範解答
チェックするマスが盤の第1列又は第N列の場合
解説
解答の論理構成
- ライフゲームの隣接判定では、対象マスが盤の端にある場合は左右方向に存在しないマスが出るので、走査範囲を制限する必要があります。
- 図3の α 部分では、端判定のために次の2行が使われています。
- if( i-1がNで割り切れる )
- elseif( iがNで割り切れる )
- 1行目は「i-1がNで割り切れる」――すなわちiが1, N+1, 2N+1 … という配列先頭列に対応するインデックスである場合です。これは「盤の第1列」に相当します。
- 2行目は「iがNで割り切れる」――すなわちiがN, 2N, 3N … という末尾列に対応するインデックスである場合で、「盤の第N列」を表します。
- いずれかに該当すれば左右どちらかが盤外になるため、図3ではaとb （横方向の探索開始・終了）の値を調整し、配列境界を越えないようにしています。
- したがって α の2条件をまとめると「チェック対象が盤の左右端のマスである場合」となり、模範解答「チェックするマスが盤の第1列又は第N列の場合」が導かれます。
誤りやすいポイント
- i-1とiのどちらで割り切り判定しているかを取り違え、左端と右端を逆に解釈してしまう。
- 行端だけでなく行頭・行末の「列」端を問う設問であることを見落とし、「第1行・第N行」と答えてしまう。
- 1次元配列の線形番号をそのまま行番号と誤読し、Nで割り切れる条件を「最下行」と解釈してしまう。
FAQ
Q: i-1がNで割り切れる が第1列になる理由は？
A: 配列は1始まりです。列1のインデックスは1, N+1, 2N+1 … であり、それぞれi-1が0, N, 2N … とNの倍数になります。
A: 配列は1始まりです。列1のインデックスは1, N+1, 2N+1 … であり、それぞれi-1が0, N, 2N … とNの倍数になります。
Q: 行端（上端・下端）の処理はどこで行っていますか？
A: 上下方向は for( y を -1 から 1 まで … ) 内で c ← i + y × N + x を計算した後、( c が 1 以上 ) and ( c が N×N 以下 ) という範囲チェックで盤外かを判定しています。
A: 上下方向は for( y を -1 から 1 まで … ) 内で c ← i + y × N + x を計算した後、( c が 1 以上 ) and ( c が N×N 以下 ) という範囲チェックで盤外かを判定しています。
Q: 仮に盤外をチェックしなかったらどうなりますか？
A: 線形インデックスが0やN×N+1など実配列外を指し、実行時エラーや誤った隣接数カウントを招きます。
A: 線形インデックスが0やN×N+1など実配列外を指し、実行時エラーや誤った隣接数カウントを招きます。
関連キーワード: 一次元配列, 端判定, 余り演算, 隣接探索, ライフゲーム
設問5：〔テストプログラム〕について、(1)、(2)に答えよ。
問題文を見る（1）本文中のケに入れる適切な数値を答えよ。
模範解答
ケ：2
解説
解答の導き方
結論：ケ：2
-
初期世代の確認
「第1世代は、初期値として設定されたものである。」とあるので、引数として与えられた配列mは第1世代を表していることがわかります。 -
update関数の意味の確認
問題文に「配列mを次世代に更新する関数updateを図3に示す。」とある通り、update(m) を1回呼べばmは「次の世代」に更新されます。すなわち、ある世代を とするとupdateを 回呼ぶと世代は になります。ここでは初期が第1世代なので、 回の呼出し後の世代は です。 -
比較対象rの意味の確認
図4の説明では、配列rは「第p世代が、机上で作成した正しい結果である配列r」としてあるので、最終的にmが指す世代は「第p世代」でなければなりません。 -
必要なupdateの回数を求める
第1世代から第p世代にするには を満たす 回のupdate呼出しが必要で、つまり 回呼べばよいことになります。 -
現状コードの問題点の特定
図4の2行目は「for( iを1からpまで1ずつ増やす )」となっており、ループ内で毎回update(m) が呼ばれているためupdateを 回実行してしまいます。初期が第1世代なので 回実行すると最終的に第世代になり、比較対象の第世代（配列r）と1世代ずれて不一致になります。したがって不具合のある行は2行目であり、ケ に入る数値は2です。 -
修正方法（参考）
ループ回数を にすればよいので、例えば次のいずれかにすれば正しい動作になります。
「for( iを1からp-1まで1ずつ増やす )」または「for( iを2からpまで1ずつ増やす )」。
以上より、ケ：2。
誤りやすいポイント
- 初期世代の番号を0と考えてしまう誤り：本文は「第1世代は、初期値として設定されたものである。」と明示しているので、ここを見落として0始まりで考えるとoff-by-oneを起こします。
- updateの意味を取り違える誤り：update(m) は「次世代に更新する」関数なので、呼ぶ回数がそのまま世代の進み数になります。
- ループの境界を見落とす誤り：「1からpまで」と「1からp-1まで」の差は回数で1回分の差になるため、テスト比較では即座に不一致になります。
- 言語依存のforスコープに注目しすぎる誤り：ループ変数のスコープや初期化の問題は言語による違いはありますが、本問の原因は単純な回数の誤り（オフバイワン）です。
- 配列のインデックス基準（1始まり／0始まり）混同：図2によれば配列はm[1] からm[N×N] を使っているため、問題文の基準に従って考える必要があります。
FAQ
Q: なぜ図4の2行目自体が悪い行なのですか？
A: 図4の2行目「for( iを1からpまで1ずつ増やす )」はupdate(m) をループごとに呼んでいるので、ループ回数がそのままupdateの呼出回数になります。初期が第1世代のため、p回呼ぶと第世代になり、比較対象の第世代（配列r）とずれてしまうからです。
A: 図4の2行目「for( iを1からpまで1ずつ増やす )」はupdate(m) をループごとに呼んでいるので、ループ回数がそのままupdateの呼出回数になります。初期が第1世代のため、p回呼ぶと第世代になり、比較対象の第世代（配列r）とずれてしまうからです。
Q: 初期状態を第0世代にすれば元のコードのままで良くなりませんか？
A: 理論上は初期を第0世代に定義すればupdateをp回呼んで第p世代になりますが、問題文は明確に「第1世代は、初期値として設定されたものである。」と定めているため、仕様に合わせてループの境界を直す方が正しい修正です。
A: 理論上は初期を第0世代に定義すればupdateをp回呼んで第p世代になりますが、問題文は明確に「第1世代は、初期値として設定されたものである。」と定めているため、仕様に合わせてループの境界を直す方が正しい修正です。
Q: ループをどう直せば良いですか？
A: 代表的な修正は次のどちらかです。
・「for( iを1からp-1まで1ずつ増やす )」にする（updateを 回呼ぶ）。
・「for( iを2からpまで1ずつ増やす )」にする（同じく 回呼ぶ）。どちらでも期待する第世代になります。
A: 代表的な修正は次のどちらかです。
・「for( iを1からp-1まで1ずつ増やす )」にする（updateを 回呼ぶ）。
・「for( iを2からpまで1ずつ増やす )」にする（同じく 回呼ぶ）。どちらでも期待する第世代になります。
関連キーワード: オフバイワン、配列、参照渡し、ループ境界、更新処理
設問5：〔テストプログラム〕について、(1)、(2)に答えよ。
問題文を見る（2）本文中の下線①の修正後のケ行目のプログラムを答えよ。
模範解答
for(iを2からpまで1ずつ増やす)
解説
解答の論理構成
- 初期値として与えられている配列mは “第1世代” である
― 【問題文】「第1世代は、初期値として設定されたものである。」 - 関数updateは1回呼び出すごとに “次の世代” を作る
― 【問題文】「次の世代への状態の更新は、全てのマスについて同時に行われる。」 - p世代を得るには、第1世代から (p-1) 回のupdateが必要
― 例えばp＝2ならupdateを1回、p＝3なら2回で第3世代になる。 - 図4の元の ケ 行は
「2: for( iを1からpまで1ずつ増やす )」
これではupdateがp回実行され、第(p+1)世代になってしまう。 - 最初の1回目を飛ばし、i＝2からpまで回せばupdateの総回数は (p-1) 回になる。
よって修正後の ケ 行は
「for(iを2からpまで1ずつ増やす)」
誤りやすいポイント
- 「第1世代＝0回更新」と数え間違え、p回updateしてしまう。
- updateに副作用があるため、ループ条件を誤ると一気に全要素がずれる。
- p＝2の最小ケースでテストせず、バグを見逃しやすい。
FAQ
Q: p＝1のときはどうしますか？
A: 問題文に「pには2以上の整数が入る」とあるので想定外です。特別な処理は不要です。
A: 問題文に「pには2以上の整数が入る」とあるので想定外です。特別な処理は不要です。
Q: ループ変数を0-basedにしても良いですか？
A: 可能ですが、その場合は開始値と比較値の両方を0-basedに合わせ、(p-1) 回の実行になるよう調整してください。
A: 可能ですが、その場合は開始値と比較値の両方を0-basedに合わせ、(p-1) 回の実行になるよう調整してください。
Q: updateの戻り値を使う方法ではダメですか？
A: 今回の仕様ではupdateは副作用型（参照渡し）で設計されています。戻り値に変えるとテスト関数側を全面的に書き換える必要があり、本設問の趣旨から外れます。
A: 今回の仕様ではupdateは副作用型（参照渡し）で設計されています。戻り値に変えるとテスト関数側を全面的に書き換える必要があり、本設問の趣旨から外れます。
関連キーワード: ライフゲーム, 世代カウント, テストループ, オフバイワンエラー
