本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

令和3年度 技術士第一次試験問題【専門科目】

V−2

以下の無向グラフと隣接行列において、0から3へ至るパスを検索するプログラムを考える。下線部の【ア】に入るプログラム片のうち、最も適切なものはどれか。


〔プログラム〕
mm=[[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]
def gsearch(l, r):
 for i, c in enumerate(l):
  if     【ア】    
   if i==3:
    print(r+[i])
   else:
    gsearch(mm[i], r+[i])
gsearch(mm[0], [0])

〔実行結果〕
[0, 1, 2, 3]
[0, 1, 3]
[0, 2, 1, 3]
[0, 2, 3]

@ (c==1) or (i not in r):

A (c==0) and (i in r):

B (c==0) or (i in r):

C (c==1) and (i not in r):

D (c==1) or (i in r):


正解

C


解説

隣接行列は、頂点同士が辺でつながっているかどうかを表す行列である。
例えば、頂点0の隣接行列は、は頂点1と頂点2につながっているので、
[0, 1, 1, 0]と表せる。

0から3へ至るパスは以下の4通りある。
0 ⇒ 1 ⇒ 2 ⇒ 3
0 ⇒ 1 ⇒ 3
0 ⇒ 2 ⇒ 1 ⇒ 3
0 ⇒ 2 ⇒ 3
これらを正しく出力できるようにプログラムを考える。

配列mmが定義され、次に
def gsearch(l, r)
 〜
gsearch(mm[i], r+[i])

引数が l と rの関数grearchを定義する。


プログラムは
gsearch(mm[0], [0]) から実行し、gsearch関数内で再帰的に呼び出される。

なお、enumerate関数は for文でインデックスと要素を同時に取得する関数である。for i, c in enumerate(l): によって、引数のmmのリストを i と c に以下のように 取り出していく。
mm[0]のとき: (i, c) ⇒ (0, 0), (1, 1), (2, 1), (3, 0)

また、r+[i]は、リスト r の最後に i を加えたリストとなる。

これらを踏まえ、gsearch(mm[0], [0]) をトレースすると次のようになる。

for 1回目 (r=[0])
 (i, c) = (0, 0)
  ここで、c = 0ということは隣接していないため、処理する必要がない。また、リストr の中に自分自身や、すでに検索した点があれば、処理する必要がない。この時点で 正解はCと予想できる。

for 2回目 (r=[0])
 (i, c) = (1, 1) ・・・ 0が1と隣接していることが分かる。
 gsearch(mm[1], [0]+[1]) = gsearch(mm[1], [0, 1])
  for 1回目 (r = [0, 1])
   (i, c) = (0, 1)
 ・・・i = 0はがリスト r の中にある。
  for 2回目 (r = [0, 1])
   (i, c) = (1, 0)

  for 3回目 (r = [0, 1])
   (i, c) = (2, 1)

    gsearch(mm[2], [0, 1]+[2])
       for 1回目 (r = [0, 1, 2])
       (i, c) = (0, 1)

       for 2回目 (r = [0, 1, 2])
       (i, c) = (1, 1)
       for 3回目 (r = [0, 1, 2])
       (i, c) = (2, 0)

       for 4回目 (r = [0, 1, 2])
       (i, c) = (3, 1)
        
print([0, 1, 2]+[3]) ・・・[0, 1, 2, 3]を出力
  for 4回目 (r = [0, 1])
   (i, c) = (3, 1)
    print([0,1]+[3]) ・・・
[0, 1, 3]を出力
for 3回目 (r=[0])
 (i, c) = (2, 1)
 gsearch(mm[2], [0]+[2]) = gsearch(mm[2], [0, 2])
  for 1回目 (r = [0, 2])
   (i, c) = (0, 1)
  for 2回目 (r = [0, 2])
   (i, c) = (1, 1)

    gsearch(mm[1], [0, 2]+[1])
       for 1回目 (r = [0, 2, 1])
       (i, c) = (0, 1)

       for 2回目 (r = [0, 2, 1])
       (i, c) = (1, 0)
       for 3回目 (r = [0, 2, 1])
       (i, c) = (2, 1)

       for 4回目 (r = [0, 2, 1])
       (i, c) = (3, 1)
        print([0, 2, 1]+[3]) ・・・
[0, 2, 1, 3]を出力
  for 3回目 (r = [0, 2])
   (i, c) = (2, 0)
  for 4回目 (r = [0, 2])
   (i, c) = (3, 1)

    print([0,2]+[3]) ・・・[0, 2, 3]を出力
for 4回目 (r=[0])
 (i, c) = (3, 0)
     

V−1 目次 V−3