トレースのテクニックが身につく練習問題｜アルゴリズムとプログラミング問題を解くコツ
2022-11-28 更新
科目 B 問題の新しい擬似言語に合わせて、プログラムを変更しました。
なお、本記事では過去問題を一部改変しています。
この連載では、基本情報技術者試験で、多くの受験者が苦手意識を持っている科目 B 試験 アルゴリズムとプログラミング分野の「アルゴリズム穴埋め問題」に的を絞って、正解を見出すポイントを詳しく説明します。
苦手を克服するには、短いプログラムを何度も練習して、穴埋めに慣れることが重要です。
そのために、実際の試験問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。
もくじ
練習問題
スタックを使って整数値を 10 進数字列（文字列）に変換する IntFormat 関数である。 IntFormat 関数は、引数 Int で指定された整数値を 10 進数字列に変換し、その先頭の数字（文字）から 1 文字ずつ順に引数 Out[] に格納し、格納した文字数を引数 Len に格納する。整数値を 10 進数字列に変換する手順は、次のとおりである。
- Int の値がゼロの場合は、 Out[0] に “0” を、 Len に 1 を格納して、関数を終了する。
- Int の値が負の場合は、負符号を表す “-” を Out[] に格納し、 Int の値を正数に変換する。
- Int の 1 の位から上位に向かって、 1 けたずつ 10 進数字に変換し、 Push 関数でスタックに積む。
- スタックに積み終わったら、スタックに積んだ文字を順番に Pop 関数で取り出して Out[] に格納することによって、変換後の 10 進数字を正しい順序に並び替える。
- Len に Out[] に格納した文字数を設定して、関数を終了する。
引数の値をスタックに積む Push 関数と、スタックから取り出した値を戻り値として返す Pop 関数は、あらかじめ用意されているとする。配列の添字は 0 から始まり、 Out[] の要素数は十分に大きいものとする。プログラム中の各演算で、あふれは生じないものとする。 IntFormat 関数の変換例を下図に示す。
［プログラム］
◯IntFormat(整数型: Int, 文字型の配列: Out, 整数型: Len)
整数型: L, I, Idx
文字型の配列: Chr ← {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
文字型: T
L ← 0
/* 引数 Int がゼロの場合の処理 */
if (Int が 0 )
Out[L] ← Chr[Int]
L ← L + 1
Len ← L
return
endif
/* 符号の処理 */
if (Int が 0 より小さい)
I ← -Int
Out[L] ← "-"
L ← 1 + 1
else
I ← Int
endif
/* 数値を 1 けたずつ数字に変換してスタックに格納する処理 */
Push("#") /* スタックに番兵として "#" を積む */
while (I が 0 より大きい)
Idx ← I - (I ÷ 10) × 10
Push(Chr[Idx])
I ← a
endwhile
/* スタックから取り出す処理 */
T ← Pop()
while (T が "#" でない)
Out[L] ← T
b
T ← Pop()
endwhile
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("#") /* スタックに番兵として "#" を積む */
while (I が 0 より大きい)
Idx ← I - (I ÷ 10) × 10
Push(Chr[Idx])
I ← a
endwhile
プログラムを見る（読み取る）コツは、わかりやすい具体例を想定することです。
ここでは、変換する数値を格納している変数 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 では、どのような処理を行えばよいのでしょう？
ポイント4： 選択肢の変数に具体的な値を設定する
こういうことは、空欄を眺めて腕を組んで考えることではありません。基本情報技術者試験の問題は、すべて選択問題なのですから、必ず選択肢を見て考えてください。
以下に、空欄 a の選択肢を示します。
a に関する解答群
ア I – 10
イ I – I ÷ 10
ウ I – ( I ÷ 10 ) × 10
エ I ÷ 10
現時点で、変数 I は 120 です。これを 12 にしたいのですから、選択肢の変数 I に 120 を代入して、 12 になるものが正解です。
以下のように、選択肢エが正解です。繰り返しますが、整数の割り算では、小数点以下がカットされることに注意してください。
ア 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()
while (T が "#" でない)
Out[L] ← T
b
T ← Pop()
endwhile
まず、
T ← Pop()
の部分でスタックから取り出した数字を変数 T に格納しています。
次に、
while (T が "#" でない)
は、スタックの末尾を示す番兵（目印となるデータのことで、ここでは “#” という文字です）を取り出すまで繰り返す、つまりスタックに積まれたデータをすべて取り出すまで繰り返すということです。
次に、
Out[L] ← T
で、取り出した数字 T を Out[L] に格納しています。
次に、
b
という空欄 b があります。
空欄bの穴埋めは、以下の解答群から選びます。さあ、どれでしょう？
b に関する解答群
ア L ← L + 1
イ L ← L – 1
ウ I ← I + 1
エ I ← I – 1
ここでは、プログラムの中で、同様の処理をしている部分と見比べる、ということをしてみましょう。
以下のオレンジ色文字の部分で、同様の処理をしています。
/* 引数 Int がゼロの場合の処理 */
if (Int が 0 )
Out[L] ← Chr[Int]
L ← L + 1
Len ← L
return
endif
/* 符号の処理 */
if (Int が 0 より小さい)
I ← -Int
Out[L] ← "-"
L ← 1 + 1
else
I ← Int
endif
これらを見ると、 Out[L] にデータを格納したら、次の格納に備えて L の値を 1 増やす処理をしていることがわかります。空欄 b も同じはずです。
したがって、選択肢アの L ← L + 1 が正解です。
解答a － エ, b － ア
「習うより慣れろ」ということわざがあります。アルゴリズム穴埋め問題の克服に関しては、正にその通りでしょう。
この連載では、これからも短い練習問題を掲載していきますので、穴埋めに慣れることを目指してください。
正解を見出すポイントとして、同じことが示されることもあると思いますが、それは、多くの問題に共通したポイントがあるからです。
それでは、またお会いしましょう！
label 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
具体的な値を入れるとプログラムがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
具体例からヒントを掴む練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
プログラムを分割するコツがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
手順をヒントにトレースする練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
トレースのテクニックが身につく練習問題｜アルゴリズムとプログラミング問題を解くコツ
update
2進数を掛け算するプログラム | アルゴリズムとプログラミング問題を解くコツ
update
ヒープを配列で実現するプログラム｜アルゴリズムとプログラミング問題を解くコツ
update
ルールに従って検査文字（チェックディジット）を求めるプログラム｜アルゴリズムとプログラミング問題を解くコツ
update
配列のマッチング（突合せ）を行うプログラム｜アルゴリズムとプログラミング問題を解くコツ
update
2進数の知識が必要なプログラム｜アルゴリズムとプログラミング問題を解くコツ
update『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
