今週の午後問題〔問題〕アルゴリズム 文字列の誤りの検出 2017 年度 秋期

今週の午後問題

このコーナーでは毎週月曜に午後の必須選択問題から 1 問ピックアップして出題し、 解答欄 を設け、読者の皆さまも参加して解答できます! その週の金曜にはその解答と 矢沢久雄 さんによる 解説 ページを公開し、皆さんの正解率も発表します。

今回が「アルゴリズム特集」、最後の出題です!また今週の午後問も受験締切が近づいたので、一旦、お休みします。

最後を飾るのは 「 2017 年度 秋期 文字列の誤りの検出」です。

ぜひ腕試しにお使い下さい!

今週の午後問題
2017 年度 秋期 アルゴリズム 文字列の誤りの検出

問 1

 次のプログラムの説明及びプログラムを読んで,設問 1 ~ 4 に答えよ。

 文字列の誤りを検出するために, N 種類の文字に 0,1,… , N – 1 の整数値を重複なく割り当て,検査文字を生成するプログラムと,元となる文字列の末尾に検査文字を追加した検査文字付文字列を検証するプログラムである。ここで扱う 30 種類の文字,及び文字に割り当てた数値を,表 1 に示す。空白文字は “␣” と表記する。

infoスマートフォンをご覧の際、表は右にスクロールできます

表 1  文字,及び文字に割り当てた数値
文字 . , ? a b c d e f g h i j k
数値 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
文字 l m n o p q r s t u v w x y z
数値 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

〔プログラムの説明〕

 検査文字の生成と検査文字付文字列の検証の手順を示す。

  1. 検査文字の生成
    1. 文字列の末尾の文字を 1 番目の文字とし,文字列の先頭に向かって奇数番目の文字に割り当てた数値を 2 倍して N で割り,商と余りの和を求め,全て足し合わせる。
    2. 偶数番目の文字に割り当てた数値は,そのまま全て足し合わせる。
    3. 01 と 02 の結果を足し合わせる。
    4. N から 03 で求めた総和を N で割った余りを引く。さらにその結果を, N で割り,余りを求める。求めた数値に対応する文字を検査文字とする。
  2. 検査文字付文字列の検証
    1. 検査文字付文字列の末尾の文字を 1 番目の文字とし,文字列の先頭に向かって偶数番目の文字に割り当てた数値を 2 倍して N で割り,商と余りの和を求め,全て足し合わせる。
    2. 奇数番目の文字に割り当てた数値は,そのまま全て足し合わせる。
    3. 01 と 02 の結果を足し合わせる。
    4. 03 で求めた総和が N で割り切れる場合は,検査文字付文字列に誤りがないと判定する。 N で割り切れない場合は,検査文字付文字列に誤りがあると判定する。

〔検査文字付文字列の生成例〕

 表 1 及び検査文字の生成の手順を用いることによって,文字列 ipa␣␣ に対し,生成される検査文字は f である。

 検査文字付文字列は,文字列の末尾に検査文字を追加し, ipa␣␣f となる。

〔プログラムの仕様〕

各関数の仕様を 1. ~ 4.に示す。ここで,配列の添字は 1 から始まるものとする。

  1. 関数 calcCheckCharacter は,文字列及び文字列長を用いて生成した検査文字を返す。関数 calcCheckCharacter の引数及び返却値の仕様は,表 2 のとおりである。
    表 2  関数 calcCheckCharacter の引数及び返却値の仕様
    引数/返却値 データ型 入力/出力 説明
    input[] 文字型 入力 文字列が格納されている 1 次元配列
    len 整数型 入力 文字列の文字列長( 1 以上)
    返却値 文字型 出力 生成した検査文字を返す。

     関数 calcCheckCharacter は,関数 getValue, 関数 getChar を使用する。

  2. 関数 validateCheckCharacter は,検査文字付文字列を検証し,検証結果を返す。関数 validateCheckCharacter の引数及び返却値の仕様は,表 3 のとおりである。
    表 3  関数 validateCheckCharacter の引数及び返却値の仕様
    引数/返却値 データ型 入力/出力 説明
    input[] 文字型 入力 検査文字付文字列が格納されている 1 次元配列
    len 整数型 入力 検査文字付文字列の文字列長 ( 2 以上)
    返却値 論理型 出力 検査文字付文字列に誤りがないと判定した場合は true ,
    誤りがあると判定した場合は false を返す。

     関数 validateCheckCharacter は,関数 getValue を使用する。

  3. 関数 getValue は,表 1 に従い,引数として与えられた文字に割り当てた数値を返す。
  4. 関数 getChar は,表 1 に従い,引数として与えられた数値に対応する文字を返す。

設問 1

 プログラム中のに入れる正しい答えを,解答群の中から選べ。ここで, a1 と a2 に入れる答えは, a に関する解答群の中から組合せとして正しいものを選ぶものとする。

codeプログラム

infoスマートフォンをご覧の際、プログラムは右にスクロールできます

○文字型関数 : calcCheckCharacter(文字型: input[], 整数型: len)
○整数型: N, sum, i, value, check_value
○論理型: is_even
・ N ← 30
・ sum ← 0
・ is_even ← false
■ i: len, i > 0, -1
| ・ value ← getValue(input[i])
| ▲ is_even = a1
| | ・ sum ← sum + value
|-+---
| | sum ← sum + (value × 2) ÷ N + (value × 2) % N
| ▼
| ・ is_even ← not is_even
■
・ check_value ← b
・ return getChar(check_value)
○論理型関数: validateCheckCharacter(文字型: input[], 整数型: len)
○整数型: N, sum, i, value
○論理型: is_odd, ret_value
・ N ← 30
・ sum ← 0
・ is_odd ← true
・ ret_value ← true
■ i: len, i > 0, -1
| ・ value ← getValue(input[i])
| ▲ is_odd = a2
| | ・ sum ← sum + value
|-+---
| | ・ sum ← sum + (value × 2) ÷ N + (value × 2) % N
| ▼
| ・ is_odd ← not is_odd
■
▲ c
| ・ ret_value ← false
▼
return ret_value

a に関する解答群

al a2
false false
false true
true false
true true

b に関する解答群

ア N – sum % N
イ sum % N
ウ (N – sum % N) % N
エ (sum – N) % N

c に関する解答群

ア sum ÷ N = 0
イ sum ÷ N ≠ 0
ウ sum % N = 0
エ sum % N ≠ 0

設問 2

 次の記述中のに入れる正しい答えを,解答群の中から選べ。

 本プログラムでは,検査文字付文字列の誤りが 1 文字であれば,誤りを検出できる。しかし,複数の文字に誤りがある場合には,誤りがないと判定されることがある。例えば,関数 validateCheckCharacter で表 4 に示す検査文字付文字列を検証した場合,誤りがないと判定されるケースは,d。ここで,文字列 ipa␣␣ に対し生成される検査文字は f である。

表 4  検査文字付文字列
ケース 検査文字付文字列
1 ipb␣␣f
2 api␣␣f
3 pia␣␣f
4 ␣␣apif

d に関する解答群

ア 1 と 2 と 3 と 4 である
イ 2 である
ウ 2 と 3 である
エ 2 と 3 と 4 である
オ 2 と 4 である
カ ない

設問 3

 次の記述中のに入れる正しい答えを,解答群の中から選べ。

 本プログラムを文字列長が同じである複数の文字列に対して適用することを考える (図 1 参照)。

図 1  作成中の検査文字付表

〔考え方〕

 文字列長が n である m 個の文字列について考える。文字列に対して, (m + 1) 行 (n + 1) 列の表を用意する。以後,この表を検査文字付表という。

1. 検査文字の生成
 例えば,文字列長が 5 である 4 個の文字列 ipa␣␣ ,tests , make␣ ,it.␣␣ を,図 1 の太枠内のように,各文字列の先頭の位置を最左列に揃え,各文字列を上の行から順に格納して,表を作成する。この表の太枠内の各行各列をそれぞれ文字列とみなして検査文字を生成し,最右列と最下行に格納する。

 この手順で作成した検査文字付表を図 2 に示す。作成した検査文字付表の 5 行 5 列目 (網掛け部分) の検査文字はeである。

図 2  完成した検査文字付表
2. 検査文字付表の検証
 1. で作成した検査文字付表の,最下行を除く各行と最右列を除く各列を文字列とみなし,それぞれ関数 validateCheckCharacter で検証した結果,全て誤りがないと判定された場合には,検査文字付表に誤りがないと判定する。一つでも誤りがあると判定された場合は,検査文字付表に誤りがあると判定する。

e に関する解答群

ア j  イ k  ウ l  エ m

設問 4

 次の記述中のに入れる正しい答えを,解答群の中から選べ。

 図 2 の 1 行目の検査文字付文字列を取り除いた,図 3 の検査文字付表について考える。表 4 のケース 1 ~ 4 の検査文字付文字列を順に,図 3 の 1 行目に格納して検証した場合,検査文字付表に誤りがないと判定されるケースは,f

注記 5 行 5 列目 (網掛け部分) には、設問 3 の正しい答えが入っているものとする。
図 3  1 行目を取り除いた検査文字付表

f に関する解答群

ア 1 と 2 と 3 と 4 である
イ 2 である
ウ 2 と 3 である
エ 2 と 3 と 4 である
オ 2 と 4 である
カ ない

問題のヒント

文字列の誤りを検出するために、検査文字の生成および検証を行うプログラムです。データの誤りの検出方法には、チェックサム、チェックディジット、ハミング符号、 CRC などがありますが、ここでは、出題者独自の方法が使われています。

問題の前半部は、プログラムの穴埋めです。

検査文字の生成と検証の手順が詳しく示されているので、その手順とプログラムを対応付ければ、穴埋めができるでしょう。その際に、プログラムの変数名に注目してください。

たとえば、 is_even は「偶数である」という意味で、 is_odd は「奇数である」という意味です。これらの変数名が、プログラムを読み取るヒントになります。

 

問題の後半部は、検査文字の生成と検証の手順に従って、具体的な文字列で検査文字の生成と検証を行う、という内容です。少し時間がかかると思いますが、手作業で丁寧に検査文字の生成と検証を行ってください。

全体として、問題に示された手順を読み取ることが重要な問題です。

みんなの解答欄

こちらから解答できます!

今週の金曜に解答解説ページを、ご解答頂いた方の正解率とともに公開します !!

 

label 関連タグ
Q. 午前試験を
『免除』するには?
A. 独習ゼミで午前免除制度を活用しましょう。
免除試験を受けた 86% の方が、
1 年間の午前免除資格を得ています。
2022 年 下期 試験向け
コース資料公開中!
info_outline
2022 年 下期 試験向け
コース資料公開中!
詳しく見てみるplay_circle_filled
label これまでの『今週の午後問題』の連載一覧 label 著者