トレースのテクニックが身につく練習問題|アルゴリズム問題を解くコツ


2020-09-08 更新

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

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

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

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

練習問題

info編集部注: スマートフォンでご覧の際は、アルゴリズムを横スクロールすると全文をご覧になれます
問4 「スタックを使って整数値を 10 進数字列に変換するプログラム」(平成 19 年度 秋期 午後)を一部改変

 スタックを使って整数値を 10 進数字列(文字列)に変換する IntFormat 関数である。 IntFormat 関数は、引数 Int で指定された整数値を 10 進数字列に変換し、その先頭の数字(文字)から 1 文字ずつ順に引数 Out[] に格納し、格納した文字数を引数 Len に格納する。整数値を 10 進数字列に変換する手順は、次のとおりである。

  1. Int の値がゼロの場合は、 Out[0] に “0” を、 Len に 1 を格納して、関数を終了する。
  2. Int の値が負の場合は、負符号を表す “-” を Out[] に格納し、 Int の値を正数に変換する。
  3. Int の 1 の位から上位に向かって、 1 けたずつ 10 進数字に変換し、 Push 関数でスタックに積む。
  4. スタックに積み終わったら、スタックに積んだ文字を順番に Pop 関数で取り出して Out[] に格納することによって、変換後の 10 進数字を正しい順序に並び替える。
  5. Len に Out[] に格納した文字数を設定して、関数を終了する。

 引数の値をスタックに積む Push 関数と、スタックから取り出した値を戻り値として返す Pop 関数は、あらかじめ用意されているとする。配列の添字は 0 から始まり、 Out[] の要素数は十分に大きいものとする。プログラム中の各演算で、あふれは生じないものとする。 IntFormat 関数の変換例を下図に示す。

図 IntFormat 関数の変換例

[プログラム]

○IntFormat(整数型:Int, 文字型:Out[], 整数型:Len)
○整数型:L, I, Idx
○文字型:Chr[] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
○文字型:T
・L ← 0
/* 引数Intがゼロの場合の処理 */
▲ Int = 0
| ・Out[L] ← Chr[Int]
| ・L ← L + 1
| ・Len ← L
| ・return
▼
/* 符号の処理 */
▲ Int < 0
| ・I ← -Int
| ・Out[L] ← "-"
| ・L ← 1 + 1
+---
| ・I ← Int
▼
/* 数値を1けたずつ数字に変換してスタックに格納する処理 */
・Push("#")	/* スタックに番兵として"#"を積む */
■ I > 0
| ・Idx ← I - (I ÷ 10)×10
| ・Push(Chr[Idx])
| ・I ← a
■
/* スタックから取り出す処理 */
・T ← Pop()
■ T ≠ "#"
| ・Out[L] ← T
| ・b
| ・T ← Pop()
■
・Len ← L
・return

設問 プログラム中のに入れる正しい答えを、解答群の中から選べ。

a に関する解答群
ア I – 10
イ I – I ÷ 10
ウ I – ( I ÷ 10 ) × 10
エ I ÷ 10

b に関する解答群
ア L ← L + 1
イ L ← L – 1
ウ I ← I + 1
エ I ← I – 1

ポイント1:数値と数字の違いを知る

数値と数字は、異なるものです。たとえば、 123 は、 1 つの数値です。これを画面に表示するときは、 “1”, “2”, “3” という 3 つの文字を表示することになります。

このように数値の 1 けたずつを 1 つの文字にしたものが数字です。

問題に示された IntFormat 関数の変換例を見てください。 IntFormat 関数は、引数 Int に指定された 123 という数値を、 “1”、”2″、”3″ という数字に変換して引数 Out[] に格納し、その文字数の 3 を引数 Len に格納するのです。

 

コンピュータの内部では、あらゆる情報を数値で表しています。したがって、 “1”, “2”, “3” という数字も、その実体は、それぞれの数字に割り当てられた文字コードの数値です。

何という数値が割り当てられるかは、使用する文字コード体系によって異なりますが、たとえば JIS X 0201 という文字コード体系では、
“1” は 49、
“2” は 50、
“3” は 51
です。 49、50、51 を文字型として画面に出力すると、それぞれに対応した “1”, “2”, “3” という数字が表示されるのです。

 

この問題では、文字コードは示されていません。その代わりに、

文字型:Chr[] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}

という文字の配列を用意しています。

配列の添字が 0 から始まるとしているので、 Chr[0] ~ Chr[9] は、 0 から 9 の数値に対応する “0” ~ “9” という数字になります。

たとえば、変数 Idx の値が 5 なら、 Char[Idx] は、数値 5 に対応する “5” という数字になります。

ポイント2: コメントをヒントにして、問題文の説明とプログラムを対応付ける

この問題のように、処理の手順が示されている場合は、手順とプログラムを対応付けることで、空欄で行う処理がわかる場合がよくあります。

その際に、プログラムの中にあるコメントも大いに参考にしてください。試験問題のプログラムのコメントは、コメント(注釈)というよりは、ヒントだからです。

 

手順の説明の(1)は、プログラムで

/* 引数 Int がゼロの場合の処理 */

というコメントに対応した処理です。

ここには、空欄がないので(1)に示されている

Int の値がゼロの場合は、 Out[0] に “0” を、 Len に 1 を格納して、関数を終了する

という処理をやっているのだ、と考えるだけで OK です。プログラムの内容を詳しく見る必要はありません。

 

同様に、手順の説明の(2)は、プログラムの

/* 符号の処理 */

の部分に対応し、ここにも空欄がないので、プログラムの内容を詳しく見る必要はありません。

ポイント3: 具体的な数値を想定して処理の流れをトレースする

手順の説明の(3)は、プログラムの

/* 数値を1けたずつ数字に変換してスタックに格納する処理 */

に対応し、ここには空欄 a があるので、

Int の 1 の位から上位に向かって、 1 けたずつ 10 進数字に変換し、 Push 関数でスタックに積む

という説明と対応付けて、プログラムの内容を詳しく見てみましょう。

以下に、該当するプログラムの部分を示します。

/* 数値を1けたずつ数字に変換してスタックに格納する処理 */
・Push("#")	/* スタックに番兵として"#"を積む */
■ I > 0
| ・Idx ← I - (I ÷ 10)×10
| ・Push(Chr[Idx])
| ・I ← a

プログラムを見る(読み取る)コツは、わかりやすい具体例を想定することです。

ここでは、変換する数値を格納している変数 I に 123 が格納されていることを想定してみましょう。

Int の 1 の位から上位に向かって、 1 けたずつ 10 進数字に変換し、 Push 関数でスタックに積む

という説明なので、 123 という数値を、 3, 2, 1 の順に、 “3”, “2”, “1” という数字に変換して、 Push 関数でスタックに積みます。

スタックに積むのは、”3″, “2”, “1” の順に変換しただけでは順序が逆だからです。
“1”
“2”
“3”
の順に変換してスタックに積み、それをスタックから取り出すと
“1”, “2”, “3”
という正しい順序にできます。スタックでは、積んだときと逆の順序で取り出すことになるからです。

それでは、プログラムを見てみましょう。

まず、

|・Idx ← I - (I ÷ 10) × 10

という処理の I に 123 を想定すると、

|・Idx ← 123 - (123 ÷ 10) × 10

になります。

123 ÷ 10 は、整数同士の割り算なので、
小数点以下がカットされて(これは、とっても重要なことなので必ず覚えておいてください)、
12 になります。
× 10 で、それを 10 倍するので、
(123 ÷ 10) × 10 は、120 になります。

したがって、

123 - (123 ÷ 10) × 10

は、 123 – 120 = 3 になって、変数 Idx には、 123 の最下位けたの 3 が得られます。

次に、

|・Push(Chr[Idx])

という処理の Idx に 3 を想定すると、

|・Push(Chr[3])

となります。 Chr[3] は “3” なので、これによって 3 という数値が “3” という数字に変換されて、スタックにプッシュされます。

次に、

|・I ← a

という処理に空欄 a があります。これは、次に同じ処理(最下位けたの数値を取り出して、それを数字に変換してスタックに積む)に合わせて、変数 I の値を更新する処理です。

この処理の前で、変数 I の値は 120 になっています。これを 12 に変換すれば、最下位けたが 2 になります。さあ、空欄 a では、どのような処理を行えばよいのでしょう?

searchタグで関連記事をチェックスタックテクニック 具体的な値を想定

ポイント4: 選択肢の変数に具体的な値を設定する

こういうことは、空欄を眺めて腕を組んで考えることではありません。基本情報技術者試験の問題は、すべて選択問題なのですから、必ず選択肢を見て考えてください。

以下に、空欄 a の選択肢を示します。

a に関する解答群
ア I – 10
イ I – I ÷ 10
ウ I – ( I ÷ 10 ) × 10
エ I ÷ 10

現時点で、変数 I は 120 です。これを 12 にしたいのですから、選択肢の変数 I に 120 を代入して、 12 になるものが正解です。

以下のように、選択肢エが正解です。繰り返しますが、整数の割り算では、小数点以下がカットされることに注意してください。

a に関する解答群
ア 120 – 10 = 110
イ 120 – 120 ÷ 10 = 120 – 12 = 108
ウ 120 – (120 ÷ 10) × 10 = 120 – 120 = 0
エ 120 ÷ 10 = 12

ポイント5: 同様の処理をしている部分と見比べる

手順の説明の(4)は、プログラムの

/* スタックから取り出す処理 */

に対応し、ここには空欄 b があるので、

スタックに積み終わったら、スタックに積んだ文字を順番に Pop 関数で取り出して Out[] に格納することによって、変換後の 10 進数字を正しい順序に並び替える

という説明と対応付けて、プログラムの内容を詳しく見てみましょう。

以下に、該当するプログラムの部分を示します。

/* スタックから取り出す処理 */
・T ← Pop()
■ T ≠ "#"
| ・Out[L] ← T
| ・b
| ・T ← Pop()
■

まず、

・T ← Pop()

の部分でスタックから取り出した数字を変数Tに格納しています。

次に、

■ T ≠ "#"

は、スタックの末尾を示す番兵(目印となるデータのことで、ここでは “#” という文字です)を取り出すまで繰り返す、つまりスタックに積まれたデータをすべて取り出すまで繰り返すということです。

次に、

| ・Out[L] ← T

で、取り出した数字TをOut[L]に格納しています。

次に、

| ・b

という空欄 b があります。

空欄bの穴埋めは、以下の解答群から選びます。さあ、どれでしょう?

b に関する解答群
ア L ← L + 1
イ L ← L – 1
ウ I ← I + 1
エ I ← I – 1

ここでは、プログラムの中で、同様の処理をしている部分と見比べる、ということをしてみましょう。

以下のオレンジ色文字の部分で、同様の処理をしています。

/* 引数 Int がゼロの場合の処理 */
▲ Int = 0
| ・Out[L] ← Chr[Int]
| ・L ← L + 1
| ・Len ← L
| ・return
▼
/* 符号の処理 */
▲ Int < 0
| ・I ← -Int
| ・Out[L] ← "-"
| ・L ← 1 + 1
+---
| ・I ← Int
▼

これらを見ると、 Out[L] にデータを格納したら、次の格納に備えて L の値を 1 増やす処理をしていることがわかります。空欄 b も同じはずです。

したがって、選択肢アの L ← L + 1 が正解です。

 

解答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ラーニング

人気記事

人気のタグ