2016年 春期 応用情報技術者試験 問3

ライフゲーム

ライフゲームとは，数学者コンウェイが考案した，生命の誕生，生存，死滅などを再現したシミュレーションゲームである。マス目状の盤上の各マスに生命が存在でき，そのマス自身及び隣接するマスの状態によって次世代の誕生，生存，死滅が決まる。その条件を表1に示す。

なお，隣接するマスには，斜め方向のマスも含む。また，生命が存在するマスを"生のマス"，生命が存在しないマスを"死のマス"と呼ぶ。

【4×4マスのシミュレーション】

4×4マスの盤上における第3世代までのシミュレーションを図1に示す。

<figure>
  <div style="display: flex; justify-content: space-between; align-items: center;">
    <div style="text-align: center;">
      <div style="border: 1px solid black; display: inline-block;">
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
      </div>
      <p>第1世代</p>
    </div>

    <div style="font-size: 24px;">→</div>

    <div style="text-align: center;">
      <div style="border: 1px solid black; display: inline-block;">
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
      </div>
      <p>第2世代</p>
    </div>

    <div style="font-size: 24px;">→</div>

    <div style="text-align: center;">
      <div style="border: 1px solid black; display: inline-block;">
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">ア</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">イ</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">ウ</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
        <div style="display: flex;">
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">○</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">エ</span>
          <span style="border: 1px solid black; width: 20px; height: 20px; display: flex; align-items: center; justify-content: center;">×</span>
        </div>
      </div>
      <p>第3世代</p>
    </div>
  </div>
  <div style="margin-top: 10px;">
    <p><strong>凡例</strong></p>
    <p>○…生のマス</p>
    <p>×…死のマス</p>
  </div>
  <figcaption>図1 4×4マスの盤上における第3世代までのシミュレーション</figcaption>
</figure>

第1世代は，初期値として設定されたものである。例として，第1世代の2行目1列目のマスを考える。現在，このマスは死のマスである。このマスに隣接するマスを網掛けで示す。これら五つのマスの中に生のマスが三つある。これは表1の"誕生"の条件に該当するので，第2世代の2行目1列目のマスは生のマスになる。同様に，第1世代の各マスについて，そのマス自身及び隣接するマスの状態を確認することで第2世代が決まる。次の世代への状態の更新は，全てのマスについて同時に行われる。

【盤上のマスのデータ構造】

N×Nマスの盤上の状態を表現するデータ構造を考える。多次元配列が利用できないプログラム言語を考慮し，盤上の各マスの生死状態を管理するデータ構造として1次元配列mを用いる。配列mのデータ構造のイメージを図2に示す。

<figure>
  <div style="text-align: center;">
    <div style="border: 1px solid black; display: inline-block;">
      <div style="display: flex; border-bottom: 1px solid black;">
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">列</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">1</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">2</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">j</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center;">N</div>
      </div>
      <div style="display: flex; border-bottom: 1px solid black;">
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">1</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">m[1]</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">m[2]</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center;">m[N]</div>
      </div>
      <div style="display: flex; border-bottom: 1px solid black;">
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">2</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">m[N+1]</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center;">m[2×N]</div>
      </div>
      <div style="display: flex; border-bottom: 1px solid black;">
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">⋮</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center;">...</div>
      </div>
      <div style="display: flex; border-bottom: 1px solid black;">
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">行</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">m[<span class="blank-box">オ</span>]</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center;">...</div>
      </div>
      <div style="display: flex; border-bottom: 1px solid black;">
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">k</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center;">...</div>
      </div>
      <div style="display: flex; border-bottom: 1px solid black;">
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">⋮</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center;">...</div>
      </div>
      <div style="display: flex;">
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">N</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center; border-right: 1px solid black;">...</div>
        <div style="width: 40px; text-align: center;">m[N×N]</div>
      </div>
    </div>
  </div>
  <figcaption>図2 配列mのデータ構造のイメージ</figcaption>
</figure>

【配列mを次世代に更新するプログラム】

使用する定数，配列及び関数を表2に，配列mを次世代に更新する関数updateを図3に示す。

なお，関数に配列を引数として渡すときの方式は参照渡しである。

function update(m)
    copy(m, temp)      // 配列mを配列tempにコピーして退避する
    clear(m)           // 配列mの全ての要素の値を0にする
    for( iを1からN×Nまで1ずつ増やす )
    
        if( i-1がNで割り切れる )    ┐
            a ← 0                   │
            b ← 1                   │
        elseif( iが1がNで割り切れる ) ├ α
            a ← -1                  │
            b ← 0                   │
        else                        │
            a ← -1                  │
            b ← 1                   │
        endif                       ┘
        
        e ← 0
        for( yを-1から1まで1ずつ増やす )
            for( xをaからbまで1ずつ増やす )
                if( (yと0が等しくない) or (xと0が等しくない) )
                    c ← i + y×N + x
                    if( (cが1以上) and (cがN×N以下) )
                        if( カ )
                            e ← e+1
                        endif
                    endif
                endif
            endfor
        endfor
        
        // 生死を判定する
        if( キ )
            m[i] ← 1
        elseif( ク )
            ク
        endif
        
    endfor
endfunction

【テストプログラム】

図3のプログラムをテストするために，配列mに第1世代が与えられたときの第p世代が，机上で作成した正しい結果である配列rと等しいことを確認するプログラムを作成した。作成した関数shouldBeを図4に示す。ここで，pには2以上の整数が入る。

1: function shouldBe( m, p, r )
2:     for( iを1からpまで1ずつ増やす )
3:         update(m)
4:     endfor
5:     for( iを1からN×Nまで1ずつ増やす )
6:         if( m[i]とr[i]が等しくない )
7:             return false    // テスト失敗
8:         endif
9:     endfor
10:    return true           // テスト成功
11: endfunction

図3のプログラムが正しく動作する状態で図4のプログラムを実行したところ，テストが失敗した。原因を調査した結果，図4のケ行目に問題があることが判明したので，①プログラムを修正してテストを成功させることができた。

設問1　図1中のア～エに入れる適切な生死状態を，図1の凡例に倣い答えよ。

設問2　図2中のオに入れる適切な字句を答えよ。

設問3　図3中のカ～クに入れる適切な字句を答えよ。

設問4　図3中のαの二つの条件のいずれかを満たすのはどのような場合か。単語"盤"及び"マス"を用いて30字以内で述べよ。

設問5　【テストプログラム】について，(1)，(2)に答えよ。

(1)　本文中のケに入れる適切な数値を答えよ。

(2)　本文中の①の修正後のケ行目のプログラムを答えよ。