アルゴリズム問題 2進数がわかれば 50 % 以上正解できる「符号付き2進数の乗算」


2022-05-06 更新

error

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

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

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

今回は、平成 22 年度 秋期「符号付き 2 進数の乗算」を取り上げます。

2 進数の取り扱いを習得しておく

平成 22 年度 秋期「符号付き 2 進数の乗算」の問題を見てみましょう。 以下に、問題と解答へのリンクがありますので、問題にざっと目を通してください。

平成 22 年度 秋期 午後 問題 解答

基本情報技術者試験のアルゴリズム問題には、 2 進数の知識が必要になる問題が出ることがよくあります。 この問題は、その好例です。

問題には、プログラム 1 とプログラム 2 という 2 つのプログラムが示されていますが、どちらにも「拡張(符号拡張とも呼びます)」「算術シフト」など、 2 進数の取り扱いに関する言葉があります。

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

〔プログラム 1 〕

○プログラム1 (M, N)
○符号付き 2 進整数型: M, N, R
○整数型: L
・M を 5 ビットの符号付き 2 進数に拡張
・N を 8 ビットの符号付き 2 進数に拡張
・R のビット番号 7 ~ 0 に N を複写
・R のビット番号 12 ~ 8 を 0 で初期化
■ L: 1, L ≦ 8, 1
| ▲  R のビット番号 0 のビットが 1
| |・ R のビット番号 12 ~ 8 の内容に M の値を加算
| ▼
|・ R の全 13 ビットを右に 1 ビット算術シフト    /* 空いたビット位置には */
■						/* 符号と同じものが入る */
・return ( R のビット番号 7 ~ 0 の内容)      /* 返却値(括弧内)を返す */
〔プログラム 2 〕

○プログラム2 (M, N)
○符号付き 2 進整数型: M, N, R
○整数型: L
・M を 5 ビットの符号付き 2 進整数に拡張
・R のビット番号 4 ~ 1 に N を複写
・R のビット番号 9 ~ 5 及び 0 を 0 で初期化
■ L: 1, L ≦ 4, 1
| ▲ R のビット番号 1 のビットが 0 かつ R のビット番号 0 のビットが 1
| | ・R のビット番号 9 ~ 5 の内容に M の値を加算
| ▼
| ▲ R のビット番号 1 のビットが 1 かつ R のビット番号 0 のビットが 0
| | ・R のビット番号 9 ~ 5 の内容から M の値を減算
| ▼
| ・R の全 10 ビットを右に 1 ビット算術シフト /* 空いたビット位置には */
■                                         /* 符号と同じものが入る */
・return( R のビット番号 8 ~ 1 の内容 ) /* 返却値(括弧内)を返す */

午前試験と午後試験を含めて、基本情報技術者試験の問題を解くために必要とされる2進数の知識には、以下に示したものがあります。ここでは、それぞれの説明をしませんが、もしも知らないものがあれば、教材を参照して習得しておきましょう。

    bookmark基本情報技術者試験に必要な 2 進数の知識

  • 10 進数と 2 進数の変換
  • 2 進数と 16 進数の変換
  • 2 の補数表現
  • 拡張(符号拡張)
  • 論理シフトと算術シフト
  • マスク演算
  • 固定小数点数と浮動小数点数

説明の番号と対応付ける(設問 1 の空欄 a 、 b 、 c )

基本情報技術者試験のアルゴリズム問題には、アルゴリズムの説明に番号が示されていて、それとプログラムを対応付ければ解けるという問題が出ることがよくあります。 この問題は、その好例でもあります。

ただし、この問題は、ちょっと変わっています。 擬似言語で示されたプログラムがアルゴリズムの説明になっていて、図に示された手順(具体的なデータを処理する手順)の穴埋めをします。 この穴埋めでは、説明の番号と図に示された番号を対応付けることで、容易に答えを得られます。

以下は、設問 1 の空欄 a と b の答えを得る手順です。 プログラム全体の内容を理解できなくても、手順にしたがってデータを処理すれば、穴埋めができます。

| |・ R のビット番号 12 ~ 8 の内容に M の値を加算
| ▼
|・ R の全 13 ビットを右に 1 ビット算術シフト	/* 空いたビット位置には */
■						/* 符号と同じものが入る */
の手順に従って加算の手順に従って算術シフト(空欄 a )の手順に従って加算の手順に従って算術シフト(空欄 b )

以下は、設問 1 の空欄 c の答えを得る手順です。 ここでも、プログラム全体の内容を理解できなくても、手順にしたがってデータを処理すれば、穴埋めができます。

| | ・R のビット番号 9 ~ 5 の内容から M の値を減算
| ▼
| ・R の全 10 ビットを右に 1 ビット算術シフト /* 空いたビット位置には */
■                                         /* 符号と同じものが入る */
・return( R のビット番号 8 ~ 1 の内容 ) /* 返却値(括弧内)を返す */
の手順に従って減算
11011は、-5なので、00000と00101(5)を加算する
の手順に従って算術シフトの手順に従って算術シフト(空欄 c )

選択肢を見て常識的に判断する(設問 2 の空欄 g )

基本情報技術者試験の設問の中には、解答群の選択肢を見て常識的に判断できるものが時々あります。 「えっ! こんな簡単でいいの?」と言いたくなるような設問です。 この問題の設問 2 の空欄 g は、正にその好例です。

おそらく、空欄 d 、 e 、 f が、かなり難しいので、空欄 g を簡単にしたのでしょう。 以下は、問題と解答群です。

  1. プログラム 1 では, N のビットが 1 の位置で加算をするので,例えば N = 7 ( 2 進数で 0111 ) なら、加算が3回必要である。 一方,プログラム 2 では, N の各ビットを最下位から順に調べ, 1 が現れたけた位置では減算をし、次に 1 の並びが途切れて 0 が現れたけた位置では加算をする,という処理を繰り返す。 例えば N = 7 ( 2 進数で 0111 ) の場合, M × 7 を M x ( g ) として計算をするので, 2 進数での加減算の回数が 2 回で済む。

g に関する解答群

ア -20 + 23
イ -20 + 24
ウ -21 + 23
エ -21 + 24

問題をすべて読む必要はありません。

M × 7 を M x ( g )として計算

の部分だけに注目してください。

M × 7 という計算をするのですから、

M x ( g )

の空欄 g には 7 になるものが入るはずです。 その考えで、解答群を見てみましょう。

実際の数値を使った式が示されています。 それぞれを計算すると、以下のように選択肢アだけが 7 になるので、選択肢アが正解です。「えっ! こんな簡単でいいの?」ですね。

ア -20 + 23 = -1 + 8 = 7 正解
イ -20 + 24 = -1 + 16 = 15
ウ -21 + 23 = -2 + 8 = 6
エ -21 + 24 = -2 + 16 = 14

この問題には、設問 1 に空欄 a 、 b 、 c 、設問 2 に空欄 d 、 e 、 f 、 g があり、全部で 7 項目です。ここまでで、 a 、 b 、 c 、 g の 4 項目に正解できたので、それぞれの配点はわかりませんが(午後試験の設問ごとの配点は公開されていません)、きっと 50 % に達したでしょう。

今回は、

  • 「 2 進数の取り扱いを習得しておく」
  • 「説明の番号と対応付ける」
  • 「選択肢を見て常識的に判断する」

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

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

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

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