応用情報技術者 試験情報＆徹底解説

誕生、生存、死滅は現在のマスの状態と隣接する生のマスの数によって決定されます。ライフゲームの条件を決定木として整理したものが下図です。〔アについて〕
図1の第2世代を見ると[ア]は生のマスであり、隣接する生のマスは1つ、死のマスは4つであることがわかります。条件に当てはめると"過疎"に該当するため、第3世代では死のマスになります。よって、[ア]には死のマスを表す「×」が入ります。

〔イについて〕
図1の第2世代を見ると[イ]は生のマスであり、隣接する生のマスは4つ、死のマスは4つであることがわかります。条件に当てはめると"過密"に該当するため、第3世代では死のマスになります。よって、[イ]には死のマスを表す「×」が入ります。

〔ウについて〕
第2世代の[ウ]は生のマスであり、隣接する生のマスは3つ、死のマスは5つです。条件に当てはめると"生存"に該当するため、第3世代でも生のマスになります。よって、[ウ]には生のマスを表す「○」が入ります。

〔エについて〕
第2世代の[エ]は死のマスであり、隣接する生のマスは3つ、死のマスは3つです。条件に当てはめると"誕生"に該当するため、第3世代では生のマスになります。よって、[エ]には生のマスを表す「○」が入ります。

∴ア＝×
　イ＝×
　ウ＝○
　エ＝○

〔オについて〕
図2を参考に空欄に入る字句を考えます。
まず、図2の3行目N列目について考えます。2行目N列目が m[2×N] であり、そこからNだけ進んだ場所になるので、3行目N列目は m[3×N] であることがわかります。同様に、4行目N列目は m[4×N]、5行目1列目は m[5×N] …となります。すなわち、kの1つ前の行である(k-1)行目N列目は m[(k－1)×N] と表すことができます。よって配列の添字は になります。[オ]のあるk行目j列目は、m[(k－1)×N] から j だけ進んだ場所になるので、配列上の位置は m[(k－1)×N＋j] になります。よって配列の添字である[オ]には「(k－1)×N＋j」が入ります。∴オ＝(k－1)×N＋j

〔カについて〕
図3のプログラムは、配列mを次世代にupdateする関数です。
17～29行目は、m[i]のマスに隣接する生のマスの数を求める処理です。プログラム中の変数cは隣接するマスの添字を表します。また、変数eは隣接する生のマスの数を表します。
[カ]の条件を満たすとき、eの値を＋1する処理を行っていることから、[カ]に入る条件式は「隣接するマスが生のマスであるとき」であることがわかります。配列mは2行目の処理で初期化されているため、隣接するマスの確認には配列mのコピーである配列tempを使います。配列tempの値は、対応するマスが生の場合は1、死の場合は0ですので、[カ]には「temp[c]と1が等しい」が入ります。

なお、プログラムの最初に配列mを配列tempにコピーしているのは、次世代への状態の更新を現在の状態に基づいて同時に行うためです。

∴カ＝temp[c]と1が等しい

〔キについて〕
[キ]と[ク]を含む5行の処理はコメント部に説明されているように、現在参照しているマスの情報から次世代の生死を判定して、その結果を配列mに書き込む処理です。

[キ]の条件を満たすとき、「m[i] ← 1」という処理を行っています。"1"は生のマスを表すので、これは「m[i]のマスの次世代を生にする」処理に相当します。次の世代が生のマスになる条件は次の2つです。

1. 前の世代が死のマス、かつ、隣接する生のマスの数が3つである
2. 前の世代が生のマス、かつ、隣接する生のマスの数が2つまたは3つである

これを疑似言語のプログラムとして表現すると次のようになります。
※プログラム中盤のif文の条件式を参照すると、条件式が複数から成るときには個々の式を()で括ること、及び"かつ"と"または"は、それぞれ"and"と"or"で表現するルールになっていることがわかります。

1. (temp[i]が0と等しい) and (eが3と等しい)
2. (temp[i]が1と等しい) and ((eが2と等しい) or (eが3と等しい))

②の条件判定は[ク]の1行前で行われているので、[キ]には①の条件を満たしているかどうかを判定する式が入ります。よって、[キ]には「(temp[i]と0が等しい) and (eと3が等しい)」が入ります。

∴キ＝(temp[i]と0が等しい) and (eと3が等しい)

〔クについて〕
[ク]の処理は、上記①の条件が真であるときに実行されます。つまり、「前の世代が生のマス、かつ、隣接する生のマスの数が2つまたは3つである」ときの処理です。この条件を満たすマスは"生存"に当てはまるため、次の世代は生のマスになります。よって、[ク]には m[i] に"1"を代入する処理が入ります。

∴ク＝m[i] ← 1

αを含む一連の処理は、aとbの値を調整する処理です。aとbは、その後のfor文でx(列)の開始位置と終了位置を指定する変数です。なぜこのような処理をしなければならないのかというと、チェックするマスの隣接するマスの数と位置が、中心となるマスの位置によって変わるからです。上記のように、現在チェックしているマスが盤上の1列目ないしN列目に位置するときは、隣接するマスの数が少なくなります。具体的には、中心となるマスがどの列に位置するかによって開始位置と終了位置の調整が行われます。

1列目のとき

隣接するマスは1列目と2列目なので、a←0、b←1 にする

N列目のとき

隣接するマスはN－1列目とN列目なので、a←-1、b←0 にする

その他(x列目のとき)

隣接するマスはx－1列目、x列目、x＋1列目なので、a←-1、b←1 にする

これを踏まえて、αの2つの条件のいずれかを満たすのはどのような場合かを考えていきます。

まず、「i-1がNで割り切れる」場合を考えます。仮に N＝5 だとすると、i-1 が N で割り切れるときの i は、6、11、16、21、…です。これは i×N＋1 の数であり、どれも盤上の1列目に対応します。
次に、「iがNで割り切れる」場合を考えます。先程と同様に N＝5 だとすると、i が N で割り切れるときの i は、5、10、15、20、…です。これは i×N の数であり、どれも盤上のN列目に対応します。

よって、αの2つの条件を満たすのは、「チェックするマスが盤の第1列又は第N列の場合」となります。

∴チェックするマスが盤の第1列又は第N列の場合

update関数は配列mを次世代に更新する関数です。最初の世代（第1世代）に対してupdate関数を1回実行すると、配列mは第2世代に更新されます。

図3のテストプログラムでは、第p世代が正しい結果であることを確認するためのプログラムです。仮に第5世代を検証したい場合、p＝5ですので、2行目のfor文内のupdate関数は(i=1…5までの)5回実行されます。第1世代にupdate関数を5回適用すると配列mは第6世代になります。検証したいのは第5世代の配列mですが、図3のプログラムでは第6世代の配列mと第5世代の配列rを比較することになってしまいます。

配列mを第p世代にしたいときには、update関数をp-1回実行しなければなりません。図3のプログラムではp回実行してしまうので、テストは常に失敗します。つまり、誤りがあるのは2行目のfor文の継続条件です。

これを改善するには、update関数がp-1回実行されるようにプログラムを変更する必要があります。for文の「1からpまで」を「2からpまで」若しくは「1から(p-1)まで」に変更することでこの目的を達成できます。模範解答では「2からpまで」の方が採用されていますが、for文内でiが使用されているわけではないため、プログラム的にはどちらでも構わないと思います。

∴(1) ケ＝2
　(2) for (iを2からpまで1ずつ増やす)