~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ＴＮＯ2 ＣＡＳＬII試験対策
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
著作権は、小野智章(小野情報設計)が保有します。
お客様ご本人の利用のため以外の複写・複製や
第三者への公開、配布、譲渡は禁止します。
小野智章(小野情報設計)
試験情報 http://ww3.tiki.ne.jp/~tno2/shikaku.htm
登録解除 http://ww3.tiki.ne.jp/~tno2/mag/mag.htm
連絡先 http://ww3.tiki.ne.jp/~tno2/profile/mail.htm
マイページ(解除、メール・アドレスの変更等)
https://mypage.mag2.com/Welcome.do
-------------------------------------------
テーマ記号;A17
テーマ;最大公約数,最小公倍数
テーマ分類;計算-2
テーマ発行番号;5
発行;2005年7月
メール番号;5-5
-------------------------------------------
[穴埋め問題]-2
「プログラムの説明」を読んで、プログラム中の空欄を埋めよ。
プログラムの各行の先頭には、各行を区別するため、行番号を加えてある。
[プログラムの説明]
指定された２つの数の、最大公約数を求める副プログラムGCMである。
1.指定の数は、符号無し１６ビット整数として、
GR1とGR2に格納して与えられる。
2.求めた最大公約数は、符号無し１６ビット整数として、
GR0に格納して戻される。
指定したGR1とGR2の一方が０で最大公約数が求められない場合は、
エラーとして、GR0に０を格納する。
3.結果以外の汎用レジスタは、内容を保存する。
[プログラム]
1:GCM RPUSH
2: LD GR1,GR1 ;check 0
3: [ a ]
4: LD GR2,GR2 ;check 0
5: [ a ]
6:LOOP CPL GR1,GR2
7: [ b ] ;GR1=GR2=GCMの時
8: [ c ] ;GR1>GR2の時
9: LD GR0,GR2 ;GR1とGR2の入れ替え
10: [ d ]
11: [ e ]
12:SUB SUBL GR1,GR2
13: [ f ]
14:FIND LD GR0,GR1 ;GCM
15:FINISH RPOP
16: [ g ]
17:ERROR SUBA [ h ] ;GCM=0
18: [ i ]
19: END
-------------------------------------------
[穴埋め問題の解法・解答]-2
先ず[ g ]を埋めよう。
直前の15行目が汎用レジスタの復旧であるから、
ここでサブルーチン処理が終了すると予想出来る。
!!サブルーチン処理の終了箇所の確認は、プログラム分析の基本。
又、その前の14行目は、
FIND(発見)というラベルが付き、
結果を格納するレジスタGR0にGR1の内容をコピーしている。
14行目のコメントが最大公約数(GCM)となっていることも踏まえ、
この位置では最大公約数が発見されていることが判る。
!!GCMが最大公約数と知らなくても、サブルーチン名から予想出来る筈。
従って[ g ]では、RET命令でサブルーチンから戻れば良いことが判る。
g;RET
次に[ a ]を埋めよう。
[ a ]は２箇所あるが、どちらも直前で汎用レジスタを判定している。
!!レジスタの値によるフラグ設定の、定型パターン。
そのコメントから、GR1とGR2の０かどうかの判定と判る。
判定には条件付きジャンプを使うので、
[ a ]にはJZE命令かJNZ命令が入ることが判る。
「プログラムの説明」から、GR1やGR2が０の時はエラーとする。
直後の6行目以降の処理はエラー処理とは見えず、
ERRORと言うラベルが付いている17行目以降がエラー処理と思われる。
!!ラベルの言葉の意味から役割等を予測するのは、プログラム分析の常套手段。
従って、[ a ]には０の時にERRORへジャンプする命令が入る。
a;JZE ERROR
次に[ b ]と[ c ]を埋めよう。
直前の6行目では、GR1とGR2を比較している。
コメントは、それぞれ、「GR1=GR2=GCMの時」と「GR1>GR2の時」となっている。
つまり、その条件の時に分岐すると言うことである。
従って、[ b ]はJZE命令、[ c ]はJPL命令となる。
「GR1=GR2=GCM」と言うことは、
最大公約数が見つかって、GR1とGR2に格納されていると言うこと。
!!GCMが最大公約数と知らなくても、サブルーチン名から予想出来る筈。
14行目のFINDと言うラベルが、
見つかった場合のジャンプ先を表していると推測出来る。
!!ラベルの言葉の意味から役割等を予測するのは、プログラム分析の常套手段。
確かに、14行目で結果を格納するレジスタGR0にGR1の内容をコピーし、
その後、汎用レジスタを復旧してRETしている。
b;JZE FIND
8行目で「GR1>GR2の時」にジャンプしているので、
9〜11行目は、GR1 |
尚、各ラベルが、命令中で過不足無く使用されていることを確認しておこう。
ただし、コメント代わりや読み易さのために付け加えられた、
命令中では使用されないラベルも有り得る。
-------------------------------------------
[プログラムの機能変更]
最大公約数(GCM)を求めるプログラムを利用して、
最小公倍数(LCM)を求めるプログラムを作成してみましょう。
[プログラムの説明]
指定された２つの数の、最小公倍数を求める副プログラムLCMである。
1.指定の数は、符号無し１６ビット整数として、
GR1とGR2に格納して与えられる。
2.求めた最小公倍数は、符号無し１６ビット整数として、
GR0に格納して戻される。
指定したGR1とGR2の一方が０で最小公倍数が求められない場合は、
エラーとして、GR0に０を格納する。
又、最小公倍数が符号無し１６ビット整数の範囲を越える場合も、
エラーとして、GR0に０を格納する。
3.結果以外の汎用レジスタは、内容を保存する。
!!「最小公倍数(Least Common Multiple)」とは、
!!２つの数の共通の倍数(公倍数)の内、最も小さなもの。
!!分数の通分の際に、分母として使う。
!!(「倍数」とは、ある自然数に対して、任意の自然数を掛けた数。)
-------------------------------------------
[プログラミングのヒント]
自然数A,B(A>B>0)の最大公約数をMと置いて、次の様にa,bを取る。
A=aM , B=bM
最大公約数のヒントにある通り、a,bは互いに素となる。
ここで、A,Bのある公倍数をCと置いて、次の様にx,yを取る。
C=xaM=ybM
|
-------------------------------------------
全体の記述は、省略します。
[詳細化-第1段階]
MP.主要処理
MP-1.GR1=0 or GR2=0ならば、エラー処理へ飛ぶ
MP-2.GR3←GR2
MP-3.GR2←GCM(GR1,GR2)
!!引数GR1,GR2でサブルーチンGCMを呼出す。
!!ヒント中のM
MP-4.GR1←GR1÷GR2
!!ヒント中のy=a
MP-5.GR2←GR3
MP-6.MULCHK(GR1,GR2)!=0ならば、エラー処理へ飛ぶ
!!オーバフロー判定
MP-7.GR0←GR1×GR2
!!ヒント中のa×bM
!!掛け算を割算より先にすると、
!!最終結果が符号無し１６ビット整数に納まっても、
!!掛け算時点でオーバフローする可能性がある。
フローチャートは、省略します。
[詳細化-第1段階-命令作成]
!!フローと同様、「全体」の命令中の「主要処理」を置き換えれば良い。
MP-1.GR1=0 or GR2=0ならば、エラー処理へ飛ぶ
!LD GR1,GR1
!!フラグが設定される。
!!レジスタ同士の演算なので、高速。
!JZE エラー処理
!LD GR2,GR2
!JZE エラー処理
MP-2.GR3←GR2
!LD GR3,GR2
MP-3.GR2←GCM(GR1,GR2)
!CALL GCM
!LD GR2,GR0
MP-4.GR1←GR1÷GR2
!CALL DIV
!LD GR1,GR0
MP-5.GR2←GR3
!LD GR2,GR3
MP-6.MULCHK(GR1,GR2)!=0ならば、エラー処理へ飛ぶ
!CALL MULCHK
!LD GR0,GR0
!JNZ エラー処理
MP-7.GR0←GR1×GR2
!CALL MULCHK
-------------------------------------------
以下、全体を纏め、ラベル等を適切に設定すれば良いです。
Rookでは、リンク機能が無いので、ラベルはGCMとは異なる様にします。
又、適宜コメントを付け加えます。
この後については、プログラムの清書より前は、省略します。
-------------------------------------------
[プログラム全体-清書]
ラベル等を適切に設定した例です。
又、適宜コメントを付け加えています。
テスト用ドライバの例も、
小文字で示して、加えています。
Rookで実際に動かして、動作試験を行ってみましょう。
尚、ドライバ中の「read」「write」は、Rook専用のレジスタ入出力命令です。
Rookを使用しない場合は、
read命令で指定しているレジスタにlad命令で直接データを格納し、
write命令で指定しているレジスタの内容を別の方法で確認して下さい。
!!Rookにはリンク機能が無いため、
!!清書した副プログラムのSTART命令は削除している。
sample start
read 1
read 2
call LCM
write 0
ret
;
LCM RPUSH
LD GR1,GR1 ;check GR1
JZE LERROR
LD GR2,GR2 ;check GR2
JZE LERROR
LD GR3,GR2
CALL GCM ;GR0=GCM(GR1,GR2)
|
