ルールに従って検査文字(チェックディジット)を求めるプログラム|アルゴリズムとプログラミング問題を解くコツ


2022-11-28 更新
info2022 年 11 月

科目 B 問題の新しい擬似言語に合わせて、プログラムを変更しました。
なお、本記事では過去問題を一部改変しています。

この連載では、基本情報技術者試験で、多くの受験者が苦手意識を持っている科目 B 試験 アルゴリズムとプログラミング分野の「アルゴリズム穴埋め問題」に的を絞って、正解を見出すポイントを詳しく説明します。

苦手を克服するには、短いプログラムを何度も練習して、穴埋めに慣れることが重要です。

そのために、実際の試験問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。

練習問題

問 8 (平成 29 年度 春期 午後)を一部改変

 関数 calcCheckCharacter は、引数 input[] で指定された文字列の誤りを検出するための検査文字を返す。文字列は、以下に示した N 種類 (ここでは N = 30 )の文字から構成され、それぞれに数値が割り当てられている。空白文字は “△” と表記する。文字列の長さは、引数 len( 1 以上とする)で指定される。

swipe表やプログラムは横スクロールできます

文字 . , ? 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 1 20 21 22 23 24 25 26 27 28 29
[検査文字の生成の手順]
looks_one 文字列の末尾の文字を 1 番目の文字とし、文字列の先頭に向かって奇数番目の文字に割り当てた数値を 2 倍して N で割り、商と余りの和を求め、全て足し合わせる。
looks_two 偶数番目の文字に割り当てた数値は、そのまま全て足し合わせる。
looks_3 looks_onelooks_two の結果を足し合わせる。
looks_4 N から、 looks_3 で求めた総和を N で割った余りを引く。さらにその結果を、 N で割り、余りを求める。求めた数値に対応する文字を検査文字とする。
[検査文字の生成例]
文字列 “ipa△△” に対し、生成される検査文字は “f” である。

 プログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、 a1 と a2 に入れる答えは、 a に関する解答群の中から組合せとして正しいものを選ぶものとする。関数 caclCheckCharacter の中で使われている関数 getValue は、引数に与えられた文字に割り当てられた数値を返し、関数 getChar は、引数に与えられた数値に対応する文字を返す。配列の添字は、 1 から始まるとする。

[プログラム]

◯文字型: calcCheckCharacter(文字型の配列: input, 整数型: len)
  整数型: N, sum, i, value, check_value
  論理型: is_even

  N ← 30
  sum ← 0
  is_even ← a1

  for (i を len から 0 より大きい間 -1 ずつ減らす )
    value ← getValue(input[i])

    if ( is_even が a2 と一致)
      sum ← sum + value
    else
      sum ← sum + (value × 2) ÷ N + (value × 2) mod N
    endif

    is_even ← not is_even
  endfor

  check_value ← b
  return getChar(check_value)

a に関する解答群

  a1 a2
false false
false true
true false
true true

b に関する解答群

ア N - sum mod N
イ sum mod N
ウ ( N - sum mod N ) mod N
エ ( sum - N ) mod N

ポイント1: 問題に示された具体例で自分の解釈が正しいことを確認する

この問題を解くには「検査文字の生成の手順」を正しく解釈できなければなりません。もしも「自分の解釈が正しいのだろうか?」と心配になったら、問題に「検査文字の生成例」が示されているので、それを使って確認してください。

この例では、文字列 “ipa△△” に対し、生成される検査文字は “f” です。自分の解釈で検査文字を求めて、例と同じ結果が得られれば OK です。筆者は、以下のように解釈しました。

手順looks_one
文字列の末尾の文字を 1 番目の文字とし、文字列の先頭に向かって奇数番目の文字に割り当てた数値を 2 倍して N で割り、商と余りの和を求め、全て足し合わせる。
解釈
末尾を 1 番目として “ipa△△” の奇数番目の文字は、 “△” , “a” , “i” です。これらに割り当てた数値は、0, 4, 12 です。これらを 2 倍すると、0, 8, 24 です。 N = 30 で割った商と余りは、 0 と 0 、 0 と 8 、0 と 24 です。商と余りの和は、 0, 8, 24 です。全て足し合わせると、32 です。
手順looks_two
偶数番目の文字に割り当てた数値は、そのまま全て足し合わせる。
解釈
“ipa△△” の奇数番目の文字は、 “△” , “p” です。これらに割り当てた数値は、 0, 19 です。そのまま足し合わせると、 19 です。
手順looks_3
looks_onelooks_two の結果を足し合わせる。
解釈
looks_one の 32 と looks_two の 19 を足し合わせると、51 です。
手順looks_4
N から、looks_3 で求めた総和を N で割った余りを引く。さらにその結果を、 N で割り、余りを求める。求めた数値に対応する文字を検査文字とする。
解釈
N = 30 から、looks_3 で求めた 51 を N = 30 で割った余りの 21 を引くと、 9 です。さらに 9 を N = 30 で割った余りを求めると、9 です。 9 に対応する検査文字は、 “f” です。

例に示された “f” と同じ “f” という結果が得られたので、筆者の解釈は正しいようです。

もしも、同じ結果が得られなかった場合は、どこかに解釈の間違いがあるので、手順をよく見直してください。「あっ! そういう意味だったのか」と気付くはずです。

ポイント2: 変数名をヒントにして変数の役割を見出す

a1a2は、変数 is_even への代入と比較です。
bは、変数 check_value への代入です。

これらの穴埋めをするには、変数の役割がわからなければなりません。

これらの変数の役割は、問題文に示されていませんが、変数名をヒントにすればわかるでしょう。

 

is_even の、 even は偶数という意味です。
is は「 is this a pen ? (これはペンですか?) 」という疑問文の is であり、「~ですか?」という意味です。

つまり、is_even は「偶数ですか?」を意味する変数であり、論理型で定義されているので、値が true なら偶数であり、 false なら奇数です。

 

「 even が偶数なんて知らない!」という人は、プログラムに登場する変数名や関数名で使われる英単語の意味を覚える習慣を持ってください。

筆者は、英語が得意なわけではありません。英検が 3 級で、 TOEIC が 400 点台という、英語のできない典型的な日本人です。そうであっても、プログラムに登場する変数名や関数名で使われる英単語は、意味を覚えるようにしています。

even が「偶数」で、 odd が「奇数」 であることは、かつて何らかのプログラムで見たときに覚えました。

プログラムには、難しい英単語は登場しません。もしも、変数名や関数名にわからない英単語が登場したら、面倒くさがらずに意味を調べてください。

 

check_value の意味は、調べなくてもわかるでしょう。

check は「検査」で、 value は「値」です。 calcCheckCharacter 関数は、戻り値として検査文字を返すので、プログラムの最後の処理が、

return getChar(check_value)

になっています。

「検査値」の check_value を、 getChar 関数で文字 (検査文字) に変換して返すのです。

ポイント3: 問題に示された手順とプログラムを対応付ける

この問題のように、手順が丁寧に示されている場合には、それぞれの手順とプログラムを対応付けると「この穴埋めで行う処理はこれだ!」とわかることがよくあります。

a1は、変数 is_even に代入する初期値です。

looks_one 文字列の末尾の文字を 1 番目の文字とし、文字列の先頭に向かって」

とあるので、最初に処理する末尾の文字は 1 番目であり奇数です。したがって、変数 is_even (偶数ですか?) の初期値は、 false だとわかります。

変数 is_even がa2と等しいときに、sum ← sum + value という処理を行います。これは、

looks_two 偶数番目の文字に割り当てた数値は、そのまま全て足し合わせる」

に該当するので、変数 is_even (偶数ですか?) が true と等しいだとわかります。

a1が false で、a2が true なので、 a の正解はイです。

 

bは、最終的に得られる検査値を変数 check_value に代入しています。

その前までの処理で、変数 sum ( 変数名から「和」を意味することがわかります ) の値を集計しているので、ここでは

looks_4 N から、looks_3 で求めた総和を N で割った余りを引く。さらにその結果を、N で割り、余りを求める」

を行えばよいことがわかります。

bの選択肢を見てみましょう。

b に関する解答群

ア N - sum mod N
イ sum mod N
ウ ( N - sum mod N ) mod N
エ ( sum - N ) mod N

この手順に該当するのは、

「 N から、looks_3 で求めた総和を N で割った余りを引く」

「 N – sum mod N」

であり、

「さらにその結果を、 N で割り、余りを求める」

「 ( N – sum mod N ) mod N 」

なので、選択肢ウです。

 

解答a - イ, b - ウ

「習うより慣れろ」ということわざがあります。アルゴリズム穴埋め問題の克服に関しては、正にその通りでしょう。

この連載では、これからも短い練習問題を掲載していきますので、穴埋めに慣れることを目指してください。

正解を見出すポイントとして、同じことが示されることもあると思いますが、それは、多くの問題に共通したポイントがあるからです。

それでは、またお会いしましょう!

label 関連タグ
科目A試験は、
免除できます。
独習ゼミで科目A試験を1年間免除して、科目B試験だけに集中しましょう。
免除試験を受けた 74.9% の方が、
科目A免除資格を得ています。
科目A免除試験 最大 2 回の
受験チャンス !
info_outline
科目A免除試験 最大 2 回の
受験チャンス !
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズムとプログラミング問題を解くコツ』の連載一覧 label 著者