スゴ技

平成24年度秋基本情報技術者試験【問12】

Blog：IT・情報処理BLOG | 2013.01.21

ソフトⅡコース担当　ブログのおにーさまこと高橋です。

コベコちゃん、神戸電子専門学校のある山本通りの一宮神社を忘れてるよ。（神戸電子のコベコちゃん第84回「神戸の人気初詣スポットは？）

さて今回は、平成24年度秋期基本情報技術者試験午後問12、CASLの解説です。問題はIPAのサイトをご覧ください。

今回の問題は、掛算と再帰呼び出しです。問題文とプログラムのコメントをしっかり対応付けること、落ち着いてトレースすれば大丈夫かと思います。

プログラム1は、多項式の計算部分です。掛算はプログラム2で行うので、プログラム１では、

xⁿ (x × x × x × … × x)
xⁿ + x^n-1 + … + 1

の計算です。流れを図にすると次のようになります。

xの値はGR2に設定されています。9行目のMULTでは、乗数をGR2に設定して呼び出すので、GR2はそのまま使います。次数nは、GR1に設定されています。多項式の和の数はこの次数になるので、カウントダウンして繰り返しを行います。4行目のラベルLP1には、14行目のJUMP命令で戻ってきています。このことから、ループの上端であることが分かります。4行目でGR1の値をGR3に設定しているので、GR3に設定された値によって終了判定できます。6行目でLD命令を実行しているので、4行目のフラグの状態は消えてしまいます。5行目で判定を行う必要があります。図のように、多項式の最後の1を加えないといけないので、GR1が0のときは繰り返さないといけません。終了条件はGR1が-1、すなわち負の数です。JMIを使います。ジャンプ先は、繰り返しの外なので14行目の次、15行目です。ラベルFINが一度も使われていないので、問題的には一度使うということで判断できないこともありません。空欄aはイです。

プログラム2は2数の掛算です。シフト命令が出てきますが、10進数の掛算を筆算で行うのと同じです。次の図で筆算での掛算を思い出して下さい。

筆算では、掛けた値の和を求めることになります。被乗数がGR0に、乗数がGR2に設定されてMULTは呼び出されます。GR0に結果を入れるため、最初に被乗数をGR1に設定しています。次に、合計処理なのでGR0に初期値0を設定しています（乗算結果の初期化）。ラベルFINの上の行で、「JUMP LP」とラベルLPに戻っています。従って、この部分が繰り返し処理です。繰り返しの上端である空欄bには、終了条件が入ります。JUMP命令の直前行では、GR2、つまり乗数を右へ1ビットシフトしています。この処理は、筆算で乗数を1桁右に移動していることに該当します。乗数が0になれば終了、つまり繰り返しの外であるラベルFINにジャンプします。空欄bはカです。空欄cには、筆算での被乗数を1桁左へ移動する処理、すなわち左へ1ビットシフトが入ります。プログラムの説明(2)より、符号なし整数で、桁あふれは発生しないので論理シフトを入れます。空欄cはエです。

最初の図より、3乗の計算では掛算(MULT)を3回実行します。F(x,4)では、4乗計算、3乗計算、2乗計算、1乗計算、0乗計算を行います。それぞれでMULTを実行する回数は、4回、3回、2回、1回、0回です。10回となり、設問2の解答はウです。

問題に記載されているように、

F(x,n)=x×F(x,n-1)+1

と表現することができます。すなわち、n次の多項式はn-1次の多項式を用いて計算できます。このように関数Fを計算するのに関数Fを用いることを再帰的と言います。ただし、再帰関数では、ある条件のときは再帰的にならず、単に計算値となります。常に再帰的であると、無限に再帰呼び出しを行い、抜け出せなくなります。この問題では、nが0のとき、1になります。

プログラム3を、パラメータとして使用するレジスタGR0,GR1,GR2の値の変化と呼び出し関係を図示すると次のようになります。

次の呼び出しを行うときに、赤の矢印線のようにGR1の値を1減らします。設問3の空欄はアです。青の矢印がRSUBの呼び出しです。F(x,3)では4回行われます。F(x,4)では、1回呼び出しが増えるので、6行目には5回制御が移ることになります。空欄dはオです。紫の矢印は12行、13行目の処理です。F(x,3)では3回行われます。F(x,4)では、1回増えるので、12行目は4回実行されます。空欄eはエです。