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


2020-09-08 更新

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

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

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

info編集部注: 本記事では過去問題を一部改変しています。

練習問題

info編集部注: スマートフォンでご覧の際は、アルゴリズムや表を横スクロールすると全文をご覧になれます
問 8 (平成 29 年度 春期 午後)を一部改変

 関数 calcCheckCharacter は、引数 input[] で指定された文字列の誤りを検出するための検査文字を返す。文字列は、以下に示した N 種類 (ここでは N = 30 )の文字から構成され、それぞれに数値が割り当てられている。空白文字は “△” と表記する。文字列の長さは、引数 len( 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 1 20 21 22 23 24 25 26 27 28 29
[検査文字の生成の手順]
(1) 文字列の末尾の文字を 1 番目の文字とし、文字列の先頭に向かって奇数番目の文字に割り当てた数値を 2 倍して N で割り、商と余りの和を求め、全て足し合わせる。
(2) 偶数番目の文字に割り当てた数値は、そのまま全て足し合わせる。
(3) (1) と(2) の結果を足し合わせる。
(4) N から、(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 
■ i:len, i > 0, -1
| ・value ← getValue(input[i])
| ▲ is_even =  a2 
| |・sum ← sum + value
| +―――
| |・sum ← sum + (value × 2) ÷ N + (value × 2) % N
| ▼
| ・is_even ← not is_even
■
・check_value ←  b 
・return getChar(check_value)

a に関する解答群

  a1 a2
false false
false true
true false
true true

b に関する解答群

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

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

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

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

【手順】(1)
文字列の末尾の文字を 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 です。
【手順】(2)
偶数番目の文字に割り当てた数値は、そのまま全て足し合わせる。
【解釈】
“ipa△△” の奇数番目の文字は、 “△” , “p” です。これらに割り当てた数値は、 0, 19 です。そのまま足し合わせると、19 です。
【手順】(3)
(1) と(2) の結果を足し合わせる。
【解釈】
(1) の 32 と (2) の 19 を足し合わせると、51 です。
【手順】(4)
N から、(3) で求めた総和を N で割った余りを引く。さらにその結果を、 N で割り、余りを求める。求めた数値に対応する文字を検査文字とする。
【解釈】
N = 30 から、(3) で求めた 51 を N = 30 で割った余りの 21 を引くと、 9 です。さらに 9 を N = 30 で割った余りを求めると、9 です。 9 に対応する検査文字は、 “f” です。

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

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

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

 a1  a2 は、変数 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 に代入する初期値です。

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

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

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

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

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

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

 

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

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

「 (4) N から、(3) で求めた総和を N で割った余りを引く。さらにその結果を、N で割り、余りを求める」

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

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

b に関する解答群

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

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

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

「 N – sum % N」

であり、

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

「 ( N – sum % N ) % N 」

なので、選択肢ウです。

 

解答a - イ, b - ウ

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

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

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

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

label 関連タグ
実は、午前試験を『免除』できます 独習ゼミで午前免除試験を受けた 86% の方が、
午前試験を免除しています。
2021 年度 春期試験 向け
最大 20 % OFF!
info_outline
2021年度 春期試験向け
最大 20 % OFF!
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズム問題を解くコツ』の連載一覧 label 著者

『プログラムはなぜ動くのか』(日経BP)が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでPCの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識0ベースのITエンジニアや一般書店フェアなどの一般的なPCユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

  • 「プログラムはなぜ動くのか」(日経BP)
  • 「コンピュータはなぜ動くのか」(日経BP)
  • 「出るとこだけ! 基本情報技術者」 (翔泳社)
  • 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」(翔泳社)
  • 「ifとelseの思考術」(ソフトバンククリエイティブ) など多数

grade IPA認定
午前免除制度対応
eラーニング

人気記事

人気のタグ