アルゴリズム問題 具体化すれば 50 % 以上正解できる「ビットの検査」


2022-05-06 更新

error

この記事は基本情報技術者試験の旧制度( 2022 年以前)の記事です。
この記事の題材となっている「午後問題」は現在の試験制度では出題されません。 ご注意くださいませ。

基本情報技術者試験の受験者の多くは、午後試験のアルゴリズム問題を苦手としています。しかし、その苦手なアルゴリズム問題で、 50 % 以上の正解が得られないと、合格は望めないでしょう。

この連載では、これまでに実施された基本情報技術者試験の過去問題を例にして、最低でも 50 % 正解できる解き方を紹介します。

今回は、平成 24 年度 春期 問 8 「ビットの検査」を取り上げます。

問題に示された具体例を見てプログラムの機能を理解する

平成 24 年度 春期「ビットの検査」の問題を見てみましょう。 以下に、問題と解答へのリンクがありますので、問題にざっと目を通してください。

平成 24 年度 春期 午後 問題 解答

この問題の内容は、前半部(設問 1 、設問 2 )と後半部(設問 3 )の 2 部構成になっています。

前半部は、 8 ビットの引数 Data の中で、 8 ビットの引数 Mask で指定したビット位置にあるビットの値を検査した結果を返す BitTest 関数です。

後半部は、 8 ビットの引数 Data の中にある 1 の個数を返す BitCount 関数です。

前半部の BitTest 関数のプログラムは、以下に示したように、とてもシンプルであり、プログラムの機能を理解できれば、問題を解けるでしょう。 この前半部で、 50 % の正解を目指すことにします。

〔プログラム 1 〕

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

○整数型関数 : BitTest (8 ビット論理型: Data, 8 ビット論理型: Mask) 
○整数型: RC         /* 返却値 */
▲ a
| • RC ← 2         /* 返却値は 2 */
+―――
| ▲ b
| | • RC ← 0        /* 返却値は 0 */
| +―――
| | • RC ← 1        /* 返却値は 1 */
| ▼
▼
• return RC          /* RC を返却値として返す */

以下は、問題に示された BitTest 関数の説明です。この説明を読んだだけでは、プログラムの機能がよくわかりませんね。

〔プログラム 1 の説明〕

 整数型関数 BitTest を,次のとおりに宣言する。

〇整数型関数 : BitTest (8 ビット論理型: Data, 8 ビット論理型: Mask)

 検査される 8 ビットのデータは入力用の引数 Data に,検査をするビット位置の情報は入力用の引数 Mask に,それぞれ格納されている。 Mask 中のビットの値が 1 で あるビット位置に対応した Data 中のビットを検査して,次の返却値を返す。ここで, Mask 中には 1 のビットが 1 個以上あるものとする。

返却値 0:
検査した全てのビットが 0
1:
検査したビット中に 0 と 1 が混在
2:
検査した全てのビットが 1

おそらく出題者も「説明だけではわからないだろう」と思ったのでしょう。 そこで、説明の後に、以下の具体例を示しています。

この具体例を見れば、プログラムの機能がわかるはずです。

 例えば,図 1 の例 1 では, Mask のビット番号 7 ~ 5 の 3 ビットが 1 であるので, Data のビット番号 7 ~ 5 の 3 ビットの値を検査し, 0 と 1 が混在しているので返却値 1 を返す。 例 2 では, Mask のビット番号 4 と 0 の 2 ビットが 1 であるので, Data の ビット番号 4 と 0 の 2 ビットの値を検査し,どちらも 1 であるので返却値 2 を返す。

図 1  BitTest の実行例

BitTest 関数は、引数 Mask の中にある 1 の位置で、引数 Data をチェックする桁を指定します。 BitTest 関数は、返却値として、チェックする桁が全て 0 なら 0 を返し、 0 と 1 が混在していれば 1 を返し、全て 1 なら 2 を返します。

このように、問題に具体例が示されているときは、それを見れば、短い時間にプログラムの機能を理解できるようになっています。 問題に具体例があったら「ヒントだ!」と思ってください。

選択肢に示された変数に具体的なデータを想定して考える(設問 1 )

プログラムの機能を理解できたので、設問を解いてみましょう。 設問 1 は、 BitTest 関数のプログラムの穴埋めです。 以下に、再度プログラムを掲載します。

空欄 a が真なら返却値を 2 にしています。 したがって、空欄 a は、チェックする桁が全て 1 であることの条件です。
空欄 b が真なら返却値を 0 にしています。 したがって、空欄 b は、チェックする桁が全て 0 であることの条件です。

〔プログラム 1 〕

○整数型関数 : BitTest (8 ビット論理型: Data, 8 ビット論理型: Mask) 
○整数型: RC         /* 返却値 */
▲ a
| • RC ← 2         /* 返却値は 2 */
+―――
| ▲ b
| | • RC ← 0        /* 返却値は 0 */
| +―――
| | • RC ← 1        /* 返却値は 1 */
| ▼
▼
• return RC          /* RC を返却値として返す */

以下は、空欄 a と空欄 b の選択肢です。

“&” は AND 演算(論理積)を意味し、 “|” は OR 演算(論理和)を意味しています。 これらは、条件を結ぶ論理演算ではなく、 2 つの 2 進数の対応する桁同士で論理演算をするものです。

それでは、これらの論理演算を使って、チェックする桁が全て 1 であることと、チェックする桁が全て 0 であることは、どうすれば判断できるのでしょうか?

解答群

ア (Data & Mask) = "00000000" B
イ (Data & Mask) = Data
ウ (Data & Mask) = Mask
エ (Data | Mask) = "00000000" B
オ (Data | Mask) = Mask

こういうことを頭の中だけで考えていると、どんどん時間が経過してしまいます。 選択肢があるのですから、それらをよく見てください。

どの選択肢でも、行っている論理演算は、 Data & Mask( AND 演算)と Data | Mask ( OR 演算)のいずれかなのですから、 Data と Mask に具体的なデータを想定して考えましょう。 そうすれば、短い時間に正解を選ぶことができます。

 

返却値が 2 (チェックする桁が全て 1 である)になる具体例として、問題に示されていた

Data = 00110011

および

Mask = 00010001

を想定してみましょう。

      00110011 Data
AND   00010001 Mask
――――――――――――――――――
      00010001
      00110011 Data
OR    00010001 Mask
――――――――――――――――――
      00110011

以上のように、 AND 演算の結果は 00010001 になり(これは、 Mask と同じであり選択肢ウです)、 OR 演算の結果は 00110011 になります(これは、 Data と同じであり選択肢にありません)。

したがって、選択肢ウが正解です。

返却値が 0 (チェックする桁が全て 0 である)になる具体例は、問題に示されていないので、先ほどの具体例をアレンジして

Data = 00110011

および

Mask = 10001000

を想定してみましょう。

      00110011 Data
AND   10001000 Mask
――――――――――――――――――
      00000000
      00110011 Data
OR    10001000 Mask
――――――――――――――――――
      10111011

以上のように、 AND 演算の結果は 00000000 になり(これは、選択肢アです)、 OR 演算の結果は 10111011 になります(これは、選択肢にありません)。

したがって、選択肢アが正解です。

具体例を想定してプログラムをトレースする(設問 2 )

設問 2 は、 BitTest 関数で引数 Mask を 00000000 (チェックする桁の指定なし)としたときに、返却値として 0 を返すようにするには、プログラムをどのように修正すればよいかという内容です。 変更なしも含めて、以下の 3 つの修正案が示されています。

問題に

空欄 a と空欄 b には、設問 1 の正しい答えが入っているものとする

とあるので、ここでは、それぞれの空欄にプログラムを入れてあります。

〔修正案 looks_one (変更なし) 〕

▲ (Data & Mask) = Mask
| • RC ← 2
+―――
| ▲ (Data & Mask) = "00000000" B
| | • RC ← 0
| +―――
| | • RC ← 1
| ▼
▼
• return RC
〔修正案 looks_two

▲ (Data & Mask) = "00000000" B
| • RC ← 0
+―――
| ▲ (Data & Mask) = Mask
| | • RC ← 2
| +―――
| | • RC ← 1
| ▼
▼
• return RC
〔修正案 looks_3

• RC ← 2
▲ (Data & Mask) = "00000000" B
| • RC ← 2
▼
▲ (Data & Mask) = Mask
| • RC ← 1
▼
▼
• return RC

解答群
ア 修正案 looks_one  
イ 修正案 looks_two
ウ 修正案 looks_3  
エ 修正案 looks_one 及び looks_two
オ 修正案 looks_one 及び looks_3  
カ 修正案 looks_two及び looks_3

この設問は、具体例を想定してプログラムをトレースすることで、解くことができます

Data = 00110011

および

Mask = 00000000

を想定してみましょう。

〔修正案 looks_one (変更なし) 〕

▲ (Data & Mask) = Mask
| • RC ← 2
+―――
| ▲ (Data & Mask) = "00000000" B
| | • RC ← 0
| +―――
| | • RC ← 1
| ▼
▼
• return RC(Data & Mask) = Mask となり、
変数 RC に 2 が格納される。
返却値として 2 が返される

〔修正案 looks_two

▲ (Data & Mask) = "00000000" B
| • RC ← 0
+―――
| ▲ (Data & Mask) = Mask
| | • RC ← 2
| +―――
| | • RC ← 1
| ▼
▼
• return RC(Data & Mask) = 00000000 となり、
変数 RC に 0 が格納される。
返却値として 0 が返される

〔修正案 looks_3

• RC ← 2
▲ (Data & Mask) = "00000000" B
| • RC ← 2
▼
▲ (Data & Mask) = Mask
| • RC ← 1
▼
▼
• return RC(Data & Mask) = 00000000 となり、
いったん変数 RC に 0 が格納される。
(Data & Mask) = Mask ともなるので、
変数 RC が 2 で上書きされる。
返却値として 2 が返される

以上のように、修正案 looks_one では、

Data & Mask = Mask

となるので、返却値として 2 が返されます。

 

修正案 looks_two では、

Data & Mask = 00000000

となるので、返却値として 0 が返されます。

 

修正案 looks_3 では、

Data & Mask = 00000000

となるので返却値を格納する変数 RC にいったん 0 が格納されますが、

Data & Mask = Mask

も成り立つので変数 RC が 2 で上書きされて、返却値として 2 が返されます。

 

したがって、修正案 looks_two だけが正しく動作し、選択肢イが正解です。

今回は、

  • 「問題に示された具体例を見てプログラムの機能を理解する」
  • 「選択肢に示された変数に具体的なデータを想定して考える」
  • 「具体例を想定してプログラムをトレースする」

という解き方を紹介しました。

どの解き方にも「具体例」や「具体的」という言葉があります。 これは、他人(出題者)が作ったプログラムを短い時間で読み取るには、とにかく具体例を想定することが重要だからです。

今後も、この連載では、アルゴリズム問題で最低でも 50 % 正解できる解き方を、あれこれと紹介していきます。少しでも、皆様の参考になれば幸いです。

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

label 関連タグ
新制度でも、
午前免除できます。
独習ゼミで科目 A 試験を免除しましょう。
免除試験を受けた 86% の方が、
1 年間の午前免除資格を得ています。
午前免除試験 最大 2 回の
受験チャンス !
info_outline
午前免除試験 最大 2 回の
受験チャンス !
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズム問題で半分以上正解できる解き方』の連載一覧 label 著者