基本情報技術者 2014年 秋期 午後 問12
次のアセンブラプログラムの説明及びプログラムを読んで、設問1～3に答えよ。
〔プログラム1の説明〕
n個の要素（大きさ1語）から成る配列に格納されているデータを、バブルソートによって昇順に並べ替える副プログラムSORTである。
(1) 配列の先頭アドレスはGR1に設定されて、主プログラムから渡される。
(2) 配列の要素数n（n≧2）はGR2に設定されて、主プログラムから渡される。
(3) 配列に格納されているデータは、符号なしの整数とみなして並べ替える。
(4) 副プログラムから戻るとき、汎用レジスタGR1～GR7の内容は元に戻す。
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
解答群
ア：JMI CONT
イ：JMI LOOP1
ウ：JPL CONT
エ：JPL LOOP1
オ：JZE CONT
カ：JZE LOOP1
模範解答
a：ア、b：エ
解説
解答の導き方
この副プログラムは、隣り合う要素を比べ、大きい値を右側へ移して昇順に並べるバブルソートです。配列の要素は「符号なしの整数」として扱うので、負の数はなく、値の大小を比較します。
まず、aに入る処理を考えます。
6行目で、GR4が指す要素をGR5に読み込みます。続く7行目のCPL（Compare Logical：符号なしの値として比較する命令）は、GR5と、GR4の次のアドレスにある要素を比べます。比較の結果は、条件分岐に使うフラグ（比較結果などを示す状態）に記録されます。
昇順にするには、GR5の値が次の要素より大きい場合に、9～11行目で二つの値を入れ替えます。一方、GR5の値が次の要素より小さい場合は、すでに正しい順序なので、入れ替えずに次の比較へ進みます。
JMI（Jump on Minus：比較結果が小さい側を示すときの分岐）は、CPLによる比較でGR5の値が次の要素より小さいときに分岐します。次の比較へ進む場所はCONTなので、aにはJMI CONTが入ります。JMI LOOP1では、残りの要素を比べる前に次の走査へ進んでしまうため、分岐先もCONTである必要があります。
次に、bに入る処理を考えます。
3行目では、GR2から1を引いています。配列の要素がn個なら、隣り合う要素の組は最初の走査で組あるためです。4行目では、その回数をGR3にコピーしています。
内側のループでは、比較のたびにGR4を次の要素のアドレスへ進め、GR3を1減らします。14行目のJPL LOOP2（Jump on Plus：値が正のときの分岐）は、GR3がまだ0より大きい間、次の要素の比較を続けます。比較が終わると、15行目でGR2を1減らします。残りの走査回数がある、つまりGR2が0より大きい間は、外側のループLOOP1に戻る必要があります。
したがって、bにはJPL LOOP1が入ります。
誤りやすいポイント
- aの条件と分岐先は、別々に判断します。GR5の値が次の要素より小さいときに分岐し、分岐先は次の比較へ進むCONTです。
- CPLは符号なしの比較です。符号付きの数として大小を考えないようにします。
- JPL LOOP1は、GR2を減らした後に、残りの走査回数がある場合に使います。GR2が0になったときは分岐せず、ループを終了します。
FAQ
Q: GR5の値と次の要素が等しい場合は、どうなりますか？
A: JMIの条件には当てはまらないため、入れ替え処理へ進みます。ただし、等しい値同士を入れ替えても配列の内容は変わりません。
A: JMIの条件には当てはまらないため、入れ替え処理へ進みます。ただし、等しい値同士を入れ替えても配列の内容は変わりません。
Q: なぜ内側のループではGR3を使うのですか？
A: GR3は、現在の走査で残っている比較回数を数えるためです。比較のたびに1減らし、0になるまで次の要素との比較を続けます。
A: GR3は、現在の走査で残っている比較回数を数えるためです。比較のたびに1減らし、0になるまで次の要素との比較を続けます。
関連キーワード: バブルソート、配列、比較命令、条件分岐、ループカウンタ
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
主プログラムから渡された配列の要素数nが4で、配列の内容が図2のとき、行番号7のCPL命令はc回実行され、行番号11のST命令はd回実行される。
解答群
ア：1
イ：2
ウ：3
エ：4
オ：5
カ：6
模範解答
c：カ、d：ウ
解説
解答の導き方
この問題では、行番号7の比較命令が何回実行されるかと、行番号11のST命令が何回実行されるかを数えます。
図2の配列は、先頭から「2、4、1、3」です。プログラム1は、隣り合う要素を比べ、順序が逆なら入れ替えるバブルソート（隣り合う要素を順に比べて並べ替える方法）を行います。
まず、行番号7の比較回数を考えます。行番号3では、要素数から1を引いた値をGR2に設定します。GR2はループの回数を管理するレジスタ（処理中の値を一時的に置く場所）です。要素数が4なので、GR2は3になります。
行番号4ではGR2の値をGR3に移します。行番号6、7で隣り合う要素を調べた後、行番号13でGR3を1減らし、まだ回数が残っていれば次の要素を調べます。行番号15ではGR2を1減らして次の巡回に進みます。このため、比較する回数は次のように減っていきます。
したがって、行番号7のCPL命令は、回実行されます。
次に、行番号11のST命令の実行回数を数えます。行番号7で隣り合う値を比べ、左の値の方が大きい場合は、行番号9～11で2つの値を入れ替えます。左の値の方が小さい場合は入れ替えません。
図2の値を、比較の順に追うと次のようになります。
値を入れ替えたのは、「4と1」「4と3」「2と1」の3回です。行番号11は、入れ替えのたびに1回実行されるため、実行回数は3回です。行番号10も入れ替えの際に実行されますが、設問で数えるのは行番号11のST命令だけです。
誤りやすいポイント
- 比較回数を「要素数と同じ回数」と考えないようにします。隣り合う要素を比べるため、最初の巡回でも比較回数は要素数より1少ない3回です。
- すべての比較で入れ替えが起こるわけではありません。すでに小さい順に並んでいる組合せでは、行番号11は実行されません。
- 行番号10と行番号11は、どちらもST命令ですが、設問が尋ねているのは行番号11だけです。入れ替え1回につき、行番号11は1回実行されます。
FAQ
Q: 2回目、3回目と比較回数が少なくなるのはなぜですか？
A: 1回目の巡回で、最も大きい値が配列の右端まで移動します。そのため、次の巡回では右端を改めて比べる必要がなくなり、比較する回数が1回ずつ減ります。
A: 1回目の巡回で、最も大きい値が配列の右端まで移動します。そのため、次の巡回では右端を改めて比べる必要がなくなり、比較する回数が1回ずつ減ります。
Q: 比較回数と入れ替え回数が同じになることはありますか？
A: 配列の並び方によっては同じ回数になることもあります。しかし、この問題の配列では、比較した6組のうち入れ替えが必要なのは3組だけです。
A: 配列の並び方によっては同じ回数になることもあります。しかし、この問題の配列では、比較した6組のうち入れ替えが必要なのは3組だけです。
Q: 行番号11のST命令は、配列の値を保存する命令ですか？
A: はい。ST命令は、レジスタにある値を指定されたメモリ上の場所に書き込みます。このプログラムでは、2つの値を交換するために使われています。
A: はい。ST命令は、レジスタにある値を指定されたメモリ上の場所に書き込みます。このプログラムでは、2つの値を交換するために使われています。
関連キーワード: バブルソート、配列、ループカウンタ、比較命令、条件分岐
設問3：
問題文を見る m個の数字列を入力し、副プログラムSORTを使って、昇順に並べ替えて出力する主プログラムMAINを作成した。プログラム2中のに入れる正しい答えを、解答群の中から選べ。
(1) 入力する数字列は4桁以内とする。
(2) 2 ≦ m ≦ 100とする。
(3) 出力する数字列は4桁で、左のゼロは空白で表示する。
(4) 主プログラムMAINは入力した数字列を、1語長の2進化10進数に変換して配列に格納し、並べ替えを行う。図4に、数字列'298'を変換した2進化10進数の例を示す。
解答群
ア：AND GR0,=#000F
イ：AND GR3,=#000F
ウ：SLL GR0,4
エ：SLL GR3,4
オ：SRL GR0,4
カ：SRL GR3,4
模範解答
e：イ、f：オ
解説
解答の導き方
この設問では、並べ替えた配列の値を、4桁の数字として表示するための処理を考えます。特に、eでは数字を1桁取り出し、fでは次の桁を取り出せるようにします。
本文には、入力した数字列を「1語長の2進化10進数に変換して配列に格納」するとあります。2進化10進数（BCD：Binary-Coded Decimal）は、10進数の各桁を4ビットで表す方式です。図4では、数字列「298」が4ビットずつに分かれて格納されています。
出力処理では、LOOP6の先頭でGR0の値をGR3にコピーします。GR0には、まだ出力していない桁も含む値が残っています。そのため、GR3から一番右の4ビットだけを取り出し、数字として表示します。
まず、eには、GR3の一番右の4ビットだけを残す処理が必要です。#000Fは、下位4ビットが1の値です。これとGR3の論理積を取ると、GR3の下位4ビットだけが残り、それ以外のビットは0になります。したがって、eは「AND GR3,=#000F」です。
この処理でGR0ではなくGR3を使うのは、GR0には次の桁を取り出すための値を残しておく必要があるからです。その後の「OR GR3,=#0030」は、取り出した数字に文字「0」の文字コードを加えて、出力用の文字にする処理です。ASCII（American Standard Code for Information Interchange：文字を数値で表す規格）では、数字の文字コードは#0030から始まります。
次に、fでは、GR0を右へ4ビットずらします。そうすると、直前に取り出した桁の左隣にあった桁が、一番右に移動します。右へ4ビットずらす命令は「SRL GR0,4」です。
この直後に「JNZ LOOP6」があります。JNZは、直前の処理結果が0でなければLOOP6へ戻る命令です。GR0をずらした結果、まだ取り出す桁が残っていれば繰り返し、残っていなければLOOP7へ進んで左側を空白で埋めます。したがって、fには「SRL GR0,4」が入ります。
たとえば、図4の「298」は、4桁分の領域に「0000 0010 1001 1000」と格納されています。右端から1桁ずつ取り出すと、次のようになります。
GR0が0になった後は、残った左端の位置に空白を格納します。これにより、数字列「298」は左側に空白を付けて右寄せで表示されます。
誤りやすいポイント
- GR0ではなくGR3にANDを行います。GR3はGR0のコピーなので、GR3だけを加工すれば、残りの桁を含むGR0を保てます。
- 下位4ビットを取り出した後、GR0を4ビットずらす必要があります。ずらさないと、同じ数字を繰り返し出力してしまいます。
- 右へずらす量は1ビットではなく4ビットです。2進化10進数では、1桁が4ビットで表されているためです。
- 数字の文字コードへの変換は、下位4ビットの取り出しとは別の処理です。取り出した数字に「OR GR3,=#0030」を行ってから、出力用のバッファに格納します。
FAQ
Q: なぜGR3にGR0をコピーしてから、GR3の下位4ビットを取り出すのですか？
A: GR3は、現在出力する1桁を加工するために使います。GR0は後続の桁を含む値として残しておき、fで右へずらして次の桁を取り出します。
Q: GR0を右へずらした後、なぜ0なら空白を格納するのですか？
A: 数字列を4桁で右寄せ表示するためです。たとえば「9」のように4桁未満の数字列では、数字の左側に残った位置を空白で埋めます。
Q: 右へ4ビットずらすと、なぜ隣の桁が一番右に来るのですか？
A: 1桁分が4ビットで表されているためです。右へ4ビットずらすと、左隣の桁が一番右の位置に移動します。
関連キーワード: 2進化10進数、ビットマスク、論理シフト、ASCIIコード、バブルソート
