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

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

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

〔プログラムの説明〕

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

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 に関する解答群の中から組合せとして正しいものを選ぶものとする。

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

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

d に関する解答群

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

設問 3

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

e に関する解答群

ア　j　　イ　k　　ウ　l　　エ　m

設問 4

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

f に関する解答群

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