2022年4月25日公開分 [科目B]問4

 次の記述中のacに入れる正しい答えの組合せを,解答群の中から選べ。ここで,配列の要素番号は1から始まる。

 要素の多くが0の行列を疎行列という。次のプログラムは,二次元配列に格納された行列のデータ量を削減するために,疎行列の格納に適したデータ構造に変換する。関数 transformSparseMatrix は,引数 matrix で二次元配列として与えられた行列を,整数型配列の配列に変換して返す。関数 transformSparseMatrix を transformSparseMatrix({{3,0,0,0,0},{0,2,2,0,0},{0,0,0,1,3},{0,0,0,2,0},{0,0,0,0,1}})として呼び出したときの戻り値は,{{a},{b},{c}} である。

〔プログラム〕
b04_1.png

b04_2.png
正解 問題へ
分野:アルゴリズムとプログラミング
カテゴリ:プログラミングの諸分野への適用
解説
引数 matrix は以下の5つの配列を要素として保持する二次元配列です。
matrix = {
 1: {3, 0, 0, 0, 0},
 2: {0, 2, 2, 0, 0},
 3: {0, 0, 0, 1, 3},
 4: {0, 0, 0, 2, 0},
 5: {0, 0, 0, 0, 1}
}
この配列を引数としてプログラムを呼び出すと、以下のように処理されていきます。
  • sparseMatrix ← {{}, {}, {}}
  • matrix[1] = {3, 0, 0, 0, 0}の要素ひとつずつ(matrix[1, j])を見て、値が0でなければ以下を行う。
    • sparseMatrix[1]の末尾にiの値を追加する
    • sparseMatrix[2]の末尾にjの値を追加する
    • sparseMatrix[3]の末尾にmatrix[i, j]の値を追加する
    matrix[1]のうち0でないのは1番目の要素"3"だけなので、i、j、matrix[1, j]の値をそれぞれ配列 sparseMatrix に追加する。
    sparseMatrix[1] に i=1 を追加 ⇒ {1}
    sparseMatrix[2] に j=1 を追加 ⇒ {1}
    sparseMatrix[3] に matrix[1, 1]=3 を追加 ⇒ {3}
  • matrix[2] = {0, 2, 2, 0, 0}の要素ひとつずつ(matrix[2, j])を見て、2.と同じ処理を行う。matrix[2]のうち0でないのは2番目の要素"2"および3番目の要素"2"だけなので、i、j、matrix[2, j]の値をそれぞれ配列 sparseMatrix に追加する。
    //j = 2 のときの処理
    sparseMatrix[1] に i=2 を追加 ⇒ {1, 2}
    sparseMatrix[2] に j=2 を追加 ⇒ {1, 2}
    sparseMatrix[3] に matrix[2, 2]=2 を追加 ⇒ {3, 2}
    //j = 3 のときの処理
    sparseMatrix[1] に i=2 を追加 ⇒ {1, 2, 2}
    sparseMatrix[2] に j=3 を追加 ⇒ {1, 2, 3}
    sparseMatrix[3] にmatrix[2, 3]=2 を追加 ⇒ {3, 2, 2}
    ここまでの処理で、空欄aの先頭が{1, 2, 3, …}となっている「ウ」「エ」は誤りだとわかります。
  • matrix[3] = {0, 0, 0, 1, 3}の要素ひとつずつ(matrix[3, j])を見て、2.と同じ処理を行う。matrix[3]のうち0でないのは4番目の要素"1"および5番目の要素"3"だけなので、i、j、matrix[3, j]の値をそれぞれ配列 sparseMatrix に追加する。
    //j = 4 のときの処理
    sparseMatrix[1] に i=3 を追加 ⇒ {1, 2, 2, 3}
    sparseMatrix[2] に j=4 を追加 ⇒ {1, 2, 3, 4}
    sparseMatrix[3] に matrix[3, 4]=1 を追加 ⇒ {3, 2, 2, 1}
    //j = 5 のときの処理
    sparseMatrix[1] に i=3 を追加 ⇒ {1, 2, 2, 3, 3}
    sparseMatrix[2] に j=5 を追加 ⇒ {1, 2, 3, 4, 5}
    sparseMatrix[3] に matrix[3, 5]=3 を追加 ⇒ {3, 2, 2, 1, 3}
    ここまでの処理で、空欄cの先頭が{{3, 2, 2, 1, 2, …}となっている「ア」は誤りであるとわかります。よって、消去法により正解は「イ」と判断できます。一応、この後の処理を最後までみていきましょう。
  • matrix[4] = {0, 0, 0, 2, 0}の要素ひとつずつ(matrix[4, j])を見て、2.と同じ処理を行う。matrix[4]のうち0でないのは4番目の要素"2"だけなので、i、j、matrix[4, j]の値をそれぞれ配列 sparseMatrix に追加する。
    sparseMatrix[1] に i=4 を追加 ⇒ {1, 2, 2, 3, 3, 4}
    sparseMatrix[2] に j=4 を追加 ⇒ {1, 2, 3, 4, 5, 4}
    sparseMatrix[3] に matrix[4, 4]=2 を追加 ⇒ {3, 2, 2, 1, 3, 2}
  • matrix[5] = {0, 0, 0, 0, 1}の要素ひとつずつ(matrix[5, j])を見て、2.と同じ処理を行う。matrix[5]のうち0でないのは5番目の要素"1"だけなので、i、j、matrix[5, j]の値をそれぞれ配列 sparseMatrix に追加する。
    sparseMatrix[1] に i=5 を追加 ⇒ {1, 2, 2, 3, 3, 4, 5}
    sparseMatrix[2] に j=5 を追加 ⇒ {1, 2, 3, 4, 5, 4, 5}
    sparseMatrix[3] に matrix[5, 5]=1 を追加 ⇒ {3, 2, 2, 1, 3, 2, 1}
したがって正しい組合せは「イ」です。

Pagetop