基本情報技術者 2012年秋期午後問12

次のアセンブラプログラムの説明及びプログラムを読んで、設問1～4に答えよ。

〔プログラム1, 2の説明〕　与えられた値xに対し、係数が全て1であるn次多項式F(x, n)の値を求める副プログラムPOLYである。　　F(x, n) =

x^{n} + x^{n - 1} + ... + x + 1

　（n≧1）

(1) POLYは、多項式の次数nがGR1に、xの値がGR2に設定されて呼ばれ、計算結果をGR0に設定して呼出し元に戻る。nは1～32767の整数、xは非負の整数とし、F(x, n)の値が16ビット符号なし2進整数の範囲に収まるように与えられる。POLYは、その中で副プログラムMULTを利用する。 (2) MULTは、16ビット符号なし2進整数同士の乗算を行う副プログラムであり、被乗数と乗数がそれぞれGR0、GR2に設定されて呼ばれ、乗算結果をGR0に設定して呼出し元に戻る。乗算結果などの桁あふれは発生しないものとする。 (3) 副プログラムから戻るとき、汎用レジスタGR1～GR7の内容は元に戻す。

設問1：

問題文を見る

　プログラム1, 2中のに入れる正しい答えを、解答群の中から選べ。　 aに関する解答群　ア：JMI BRK 　イ：JMI FIN 　ウ：JNZ BRK 　エ：JNZ FIN 　オ：JZE BRK 　カ：JZE FIN 　 bに関する解答群　ア：JMI CONT 　イ：JMI FIN 　ウ：JNZ CONT 　エ：JOV CONT 　オ：JPL CONT 　カ：JZE FIN 　 cに関する解答群　ア：ADDL GR0,GR2 　イ：LD GR2,GR1 　ウ：OR GR2,=#0001 　エ：SLL GR1,1 　オ：SRA GR1,1 　カ：SRL GR1,1

模範解答

a：イ、b：カ、c：エ

解説

解答の導き方

この問題では、プログラム1が多項式の各項を計算して足し合わせ、プログラム2が乗算を行います。まず、二つの処理の流れを確認します。

a：多項式の計算を終える条件

プログラム1では、GR1に次数

n

が入っています。GR4は計算結果をためる汎用レジスタ（CPU内で値を一時的に保持する場所）で、最初に0にされています。

4行目で、GR1の値をGR3にコピーします。
6行目でGR0を1にし、 $x$ を掛ける処理を始めます。
7～11行目で、GR3が0になるまでGR0に $x$ を掛けます。GR3が $n$ なら、ここで $x^{n}$ が求まります。
12行目で、その値をGR4に足します。
13行目でGR1を1減らし、次の次数の項を計算します。

たとえば、最初の次数が2なら、計算する項は

x^{2}

、

x

、

1

の順です。

LP1に戻ったときのGR1	計算する項	GR4への加算
2	$x^{2}$	$x^{2}$
1	$x$	$x$
0	$1$	$1$
-1	なし	終了

大切なのは、GR1が0になったときには、まだ定数項の1を計算することです。GR1が0の回では、GR3も0になるため、内側の繰返しはすぐに終わります。GR0は最初に1にされているので、この項の値は1です。

したがって、終了条件は「GR1が0」ではなく、「GR1が負」になったときです。4行目のLDでGR3にGR1をコピーすると、その値の状態を示すフラグ（直前の処理結果が0か、負かなどを示す情報）も設定されます。GR1が負のときに分岐する命令はJMIなので、aには JMI FIN が入ります。

b：乗数が0になったときに乗算を終える

プログラム2は、シフト演算（ビットを左右にずらす処理）を使って乗算します。最初にGR0の被乗数をGR1に移し、GR0を0にして計算結果をためる準備をします。乗数はGR2にあります。

GR2の最下位ビット（いちばん右のビット）を調べ、1ならGR1の値をGR0に足します。その後、GR2を右に1ビットずらして、次のビットを調べます。GR2が0になれば、調べるビットがなくなったので乗算を終えます。

ループの先頭では、GR2が0かどうかを調べる必要があります。0ならFINへ進む条件分岐はJZEなので、bには JZE FIN が入ります。

c：被乗数を2倍にする

GR2を右に1ビットずらすたびに、次に調べる桁の重みは2倍になります。そのため、対応する被乗数も2倍にしておきます。

たとえば、

3 \times 5

を計算する場合、5は2進数で101です。右端から順にビットを調べます。

調べるGR2	最下位ビット	GR1を加えるか	加算後のGR0	次のGR1、GR2
5（101）	1	3を加える	3	GR1は6、GR2は2
2（10）	0	加えない	3	GR1は12、GR2は1
1（1）	1	12を加える	15	GR1は24、GR2は0

GR1は3から6、12、24と2倍になり、GR2は右にずれていきます。GR2のビットが1のときに、その桁に対応するGR1を足すことで、積の15が求まります。

このため、GR1を左に1ビットずらして2倍にするSLL GR1,1がcに入ります。後続のSRL GR2,1は、乗数を右に1ビットずらす命令です。

なお、MULTは計算中にGR1やGR2を使いますが、復帰時にはGR1～GR7の内容を元に戻します。そのため、POLYから呼び出した場合も、次数や

x

の値を保ったまま次の計算に進めます。

誤りやすいポイント

aでGR1が0になった時点で終了すると、定数項の1を加算できません。0の回も計算し、その次に負になったところで終了します。
bは、乗数が0かを調べる位置です。最下位ビットを調べて加算する処理より先に、終了判定をします。
cで右にずらすのは乗数GR2です。被乗数GR1は、次の桁に対応するため左にずらして2倍にします。
GR0は、MULTでは積をため、POLYでは計算中のべき乗を保持します。プログラム1では、多項式全体の合計をGR4にためています。

FAQ

Q: GR1が0のときに、なぜJZEで終了しないのですか？
A: GR1が0の回は

x^{0}

を計算する回で、値は1です。この項を加算してから、GR1が負になったときに終了します。

Q: 乗数のビットが0なら、GR1を足さないのはなぜですか？
A: その桁の重みが積に含まれないためです。ビットが1の桁だけ、対応するGR1の値を結果に加えます。

Q: GR1を左にずらすと、なぜ2倍になるのですか？
A: 2進数では、各桁は右隣の桁の2倍の値を表します。左に1ビットずらすと、各ビットの値が1桁分上がるため、全体が2倍になります。

関連キーワード: 2進数、シフト演算、条件分岐、ビット演算、乗算アルゴリズム

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問2：

問題文を見る

　プログラム1のPOLYを使用してF(x, 4)を計算するとき、行番号9のCALL命令が実行される回数として正しい答えを、解答群の中から選べ。　解答群　ア：4 　イ：5 　ウ：10 　エ：11 　オ：15 　カ：16

模範解答

ウ

解説

解答の導き方

問われているのは、プログラム1の行番号9にあるCALL命令が何回実行されるかです。CALLは、副プログラム（ひとまとまりにした処理）を呼び出す命令です。ここでは、行番号9で副プログラムMULTを呼び出しています。

まず、プログラム1ではGR1に現在計算する次数が入っています。GR0は計算中の値を置くレジスタ（値を一時的に保存する場所）です。行番号6でGR0を1にし、行番号9のCALL MULTで、GR0にxを掛けていきます。

行番号7～11は、GR3の値が0になるまで繰り返す処理です。GR3が0でなければ行番号9でMULTを呼び出し、行番号10でGR3を1減らします。したがって、GR3が最初に

k

なら、CALL MULTは

k

回実行されます。これは、1から始めた値にxを

k

回掛けて、

x^{k}

を計算するためです。

プログラムはGR1の値を1ずつ減らしながら、次数4から0まで順に計算します。各次数での呼出し回数は次のとおりです。

計算する項	GR3の初期値	行番号9の実行回数
$x^{4}$	4	4
$x^{3}$	3	3
$x^{2}$	2	2
$x$	1	1
$1$	0	0

次数が0のときは、GR0を1にした後、GR3が0なのでMULTを呼び出さずに計算を進めます。この項はCALLの回数に含まれません。

したがって、行番号9の実行回数は、

4 + 3 + 2 + 1 = 10

回です。解答群ではウに当たります。xの値が何であっても、MULTを呼び出す回数は次数で決まるため変わりません。

誤りやすいポイント

多項式の項は $x^{4}$ から $1$ までの5個ですが、CALLの回数は項の数とは異なります。定数項 $1$ を計算するときはMULTを呼び出さないためです。
「次数4の計算でCALLを1回」と数えないようにします。次数4の項を計算するには、1にxを4回掛けるのでCALLは4回です。
MULTの中の繰返し処理と、行番号9のCALLの実行回数を混同しないようにします。問われているのは、MULTを呼び出す行番号9の回数です。

FAQ

Q: xが0でも、行番号9の実行回数は変わりませんか？
A: 変わりません。CALLの回数はGR3で決まり、xの値によって繰返し回数が変わる処理ではありません。

Q: MULTの中で乗算処理が何度も繰り返される場合、その回数も行番号9の実行回数に加えますか？
A: 加えません。行番号9の実行回数は、MULTを呼び出した回数だけを数えます。

Q: MULTを呼び出した後、GR3の値が保たれるのはなぜですか？
A: 問題文に、副プログラムから戻るときGR1～GR7の内容は元に戻るとあります。そのため、MULTの処理後も、POLYの繰返しに使うGR3の値を引き続き使えます。

関連キーワード: レジスタ、ループ、累積加算、べき乗、サブルーチン呼出し

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問3：

問題文を見る

　関数F(x, n)は、次のように変形できる。

F (x, n) = x \times (x^{n - 1} + x^{n - 2} + ... + x + 1) + 1

（

n \geq 1

）

　更に次のように、再帰的に表現することができる。　

F (x, 0) = 1

F (x, n) = x \times F (x, n - 1) + 1

（

n \geq 1

）　この再帰表現を実装する、プログラム3のPOLY2を作成した。プログラム3中のに入れる正しい答えを、解答群の中から選べ。ここで、POLY2はPOLYと同様に呼ばれる。

解答群　ア：LAD　GR1,-1,GR1 　イ：LAD　GR1,1,GR1 　ウ：LD　GR1,GR2 　エ：LD　GR2,GR1 　オ：POP　GR1 　カ：PUSH　0,GR1

模範解答

ア

解説

解答の導き方

この問題では、再帰的な式をプログラムで実現するために、空欄で何をする必要があるかを考えます。再帰呼出しとは、処理の途中で同じ手続きをもう一度呼び出すことです。

まず、問題文の式は次のとおりです。

F (x, 0) = 1

F (x, n) = x \times F (x, n - 1) + 1 (n \geq 1)

つまり、

n

が

0

なら答えは

1

です。

n

が

0

でなければ、次数を

1

減らした

F (x, n - 1)

を求め、その値に

x

を掛けてから

1

を足します。

プログラム3の6～9行目では、GR1が

0

かどうかを調べています。GR1は次数

n

を格納する汎用レジスタ（計算に使う値を一時的に置く場所）です。GR1が

0

なら、8行目でGR0に

1

を設定して戻ります。これは、式の

F (x, 0) = 1

に当たります。

GR1が

0

でない場合は、10行目の処理をしてから11行目でRSUBを呼び出します。この呼出しでは、

F (x, n - 1)

を計算する必要があります。そのため、RSUBを呼び出す前に、GR1の値を

n

から

n - 1

に変えなければなりません。

この処理をするのが、GR1を

1

減らす「LAD GR1,-1,GR1」です。呼出しの後は、GR0に再帰呼出しで求めた値が入っています。12行目のMULTでGR2の

x

を掛け、13行目で

1

を足すと、式の

x \times F (x, n - 1) + 1

が計算できます。

たとえば、

x = 3

、

n = 2

の場合は、次のように計算が進みます。

処理	GR1（次数）	GR0（計算値）
最初の呼出し	2	まだ未確定
次の呼出しの前	1	まだ未確定
さらに次の呼出しの前	0	まだ未確定
$F (3, 0)$ の計算	0	1
1段目に戻って、 $3 \times 1 + 1$	0	4
2段目に戻って、 $3 \times 4 + 1$	0	13

結果は

13

で、

3^{2} + 3 + 1

と一致します。次数を呼出しのたびに減らすことで、

0

の場合に到達し、そこから順に答えを作れます。

したがって、空欄に入るのはアの「LAD GR1,-1,GR1」です。

誤りやすいポイント

GR1は次数 $n$ 、GR2は $x$ を格納しています。減らすのは次数なので、GR1を変更します。
GR1を増やすと、再帰呼出しのたびに次数が大きくなり、 $0$ の場合に到達できません。
GR1を減らす処理は、RSUBを呼び出す前に行います。呼出し先には $n - 1$ を渡す必要があるためです。
MULTの後に $1$ を足す処理だけに注目して、空欄でも計算する値を変更しようとしないようにします。空欄で必要なのは、次の再帰呼出しに渡す次数の調整です。

FAQ

Q: GR1を減らした後、再帰呼出しから戻るとGR1は元の値に戻りますか？
A: 戻りません。しかし、再帰呼出しの後に必要なのは、GR0にある計算結果を使って乗算することです。元の次数はその後使わないため、問題ありません。外側のPOLY2は、最後に保存していたレジスタの値を戻します。

Q: GR2の

x

は、再帰呼出しの間も保たれますか？
A: はい。MULTはGR1～GR7の内容を元に戻す仕様で、RSUBもGR2を変更しません。そのため、各段階でGR2の

x

を乗算に使えます。

Q: GR1が

0

のときに計算を止めるのはなぜですか？
A:

F (x, 0) = 1

が再帰計算の出発点だからです。このような、再帰を止める条件を基底条件といいます。

関連キーワード: 再帰呼出し、基底条件、汎用レジスタ、乗算、スタック

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問4：

問題文を見る

　次の記述中のに入れる正しい答えを、解答群の中から選べ。　　プログラム3のPOLY2を使用してF(x, 4)を計算するとき、行番号6のラベルRSUBの行にはd回制御が移る。また、行番号12のCALL命令はe回実行される。　 d, eに関する解答群　ア：1 　イ：2 　ウ：3 　エ：4 　オ：5 　カ：6

模範解答

d：オ、e：エ

解説

解答の導き方

プログラム3では、POLY2からRSUBを呼び出し、RSUBの中から再びRSUBを呼び出します。このように、自分自身を呼び出す処理を再帰呼出しといいます。

この設問では、

n = 4

のときにRSUBへ何回移るかと、MULTを何回呼び出すかを数えます。GR1は

n

を入れておくレジスタ（値を一時的に置く場所）なので、最初のRSUBではGR1に4が入っています。

行番号6の「LD GR1,GR1」は、GR1の値を確認する処理です。続く行番号7の「JNZ CONT」は、GR1が0でなければCONTへ進みます。CONTではGR1を1減らしてから、行番号11で再びRSUBを呼び出します。

動きを順に追うと、次のようになります。

RSUBに入ったときのGR1	処理	次の動き
4	0ではないのでGR1を3にする	RSUBを呼び出す
3	0ではないのでGR1を2にする	RSUBを呼び出す
2	0ではないのでGR1を1にする	RSUBを呼び出す
1	0ではないのでGR1を0にする	RSUBを呼び出す
0	JNZでCONTへ進まず、GR0に1を設定する	呼出し元へ戻る

最初の呼出しも含めると、RSUBにはGR1が4、3、2、1、0のときに入ります。したがって、行番号6のラベルRSUBの行に制御が移る回数は5回です。解答群ではオです。

次に、MULTの回数を数えます。問題文の再帰式は、

F (x, n) = x \times F (x, n - 1) + 1

です。プログラム3では、RSUBから戻った後にMULTで

x

を掛け、行番号13で1を加えます。

GR1が0のときは、行番号8でGR0に1を設定して、行番号9から戻ります。この場合はMULTを呼び出しません。一方、GR1が1、2、3、4のときは、それぞれ再帰呼出しから戻った後にMULTを1回呼び出します。

つまり、MULTの呼出しは

n = 1

、

n = 2

、

n = 3

、

n = 4

の各段階で1回ずつ、合計4回です。解答群ではエです。

誤りやすいポイント

RSUBの回数を4回と数えてしまうことがあります。最初の呼出しに加えて、GR1が3、2、1、0になったときにもRSUBに入るため、合計は5回です。
MULTも5回と数えてしまうことがあります。GR1が0のときは行番号8で値を設定して戻り、MULTを呼び出さないため、MULTは4回です。
再帰呼出しの回数と、MULTの呼出し回数は同じではありません。RSUBには基底となる $n = 0$ の処理もありますが、その処理ではMULTを実行しません。

FAQ

Q: GR1を毎回1減らすのはなぜですか？
A: 再帰式では、

F (x, n)

を求めるために、まず

F (x, n - 1)

を求めます。GR1を1減らすことで、次のRSUBに

n - 1

を渡しています。

Q: MULTが呼び出されるのは、RSUBから戻った後なのはなぜですか？
A: 先に

F (x, n - 1)

を求め、その結果に

x

を掛けてから1を加えるためです。これは再帰式の

x \times F (x, n - 1) + 1

に対応しています。

n = 0

の処理は何のためにありますか？
A: 再帰呼出しを止めるためです。プログラムでは

n = 0

のときGR0に1を設定して戻ります。これが再帰処理の基底条件（呼出しを終える条件）です。

関連キーワード: 再帰呼出し、基底条件、レジスタ、サブルーチン、漸化式

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

基本情報技術者 2012年 秋期 午後 問12

次のアセンブラプログラムの説明及びプログラムを読んで、設問1～4に答えよ。

.css-epvm6{white-space:nowrap;}設問1：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問2：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問3：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問4：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

基本情報技術者 2012年秋期午後問12

設問1：