この記事では、アセンブラ言語で「二分探索法」について簡単な例題で学べます。
シンプルな図解を用いています。また、アセンブラとアルゴリズムのの本の紹介もしています。
＜＜関連記事＞＞
基本情報技術者試験トップへ
アセンブラ自作サンプルへ
アセンブラ過去問プログラムへ
令和2年（令和3年1月）合格報告
2020年からの基本情報技術者試験は、言語とアルゴリズムの配点が高くなりました。
なので、プログラミング未経験の事務員の私は、非常に焦っていましたが、無事合格できました。
学習中のアウトプットを少し編集してお届けしております。
疑似言語によるアルゴリズムをCASL2で再現してみたら、両方学べて
一石二鳥なのではと思い、今回は「二分探索」を作ってみました。
二分探索は整列済みの配列から、目的の値を探します。
探索対象を真ん中の値より大きいか、小さいかで、範囲を絞って見つけます。
Log2 8=3 で、配列の要素数が8だったら3回の比較、Log2 16=4 で、要素数が16だったら4回の比較です。
ここで使うHAIRETSUの要素数は10個なので、
4回比較します。
CASL2では文字コードで大小を判断して、
例えばAなら41、Bなら42…と比較して探します。
配列HAIRETSUに「A」から「J」が入っていて、
「H」の要素番号「7」を返すようにします。
GR0に「H」を設定します。
LeftはGR1を、RightはGR2を、
MIDはGR3を使います。
LeftやRight、MIDは、変動するので、
先頭のアドレスをGR4に退避して固定します。
これは後で見つかった位置を返す時に使います。
それぞれのアドレスを指します。
先頭アドレスを仮に「101」とします。
イメージ的にはビジネスホテルの部屋番号みたいなものでしょうか。
左端の部屋は101号室、右端の部屋は110号室。
真ん中の部屋は（101＋110）を2で割ります。
CASL2では右に1ビットシフトします。
GR3にGR1を加え、更にGR2を加え、右に1ビットシフトすると、
105号室がGR3になります。
それでは「Eさん」をGR5に呼び出します。
GR5のEさんとGR0のHさんを比べ、MIDのEさん（文字コード45）は
Hさん（文字コード48）より小さいので、探索対象を後ろに絞ります。
USHIROにジャンプします。
GR3の1つ後ろをLeftであるGR1に設定します。
この繰り返しで、GR1のLeftがGR2のRightよりも大きくなった、
または、Hさんが見つかった時にループを抜けます。
MIDのアドレスから先頭アドレスが入っているGR4を引くと、
見つかった位置が先頭からどれだけ離れているか求まります。
GR3に「7」が求まったらそれを文字に変換して、出力します。
出力結果です。
プログラムはこちらになります。
TEST START
RPUSH
LD GR0,=’Z’ ;誰を探すか
LAD GR1,HAIRETSU
LD GR4,GR1 ;GR1の先頭アドレスを固定用にコピー
LD GR2,GR1
ADDA GR2,=9 ;配列の右端のアドレスを設定
LOOP LD GR3,GR1 ;GR3にMIDのアドレスを求める
ADDA GR3,GR2
SRL GR3,1
LD GR5,0,GR3 ;GR5にMIDの客を呼び出す
CPA GR5,GR0 ;探しているお客か？
JZE ATTA
JMI USHIRO
MAE LD GR2,GR3
LAD GR2,-1,GR2
JUMP LOOP
USHIRO LD GR1,GR3
LAD GR1,1,GR1
CPA GR1,GR2
JPL NAINAI
JUMP LOOP
ATTA ;お客が見つかった
SUBA GR3,GR4
ADDA GR3,=’0′
ST GR3,ICHI
OUT MOJI,LEN
JUMP FIN
NAINAI ;お客が見つからない
OUT MOJI2,LEN2
FIN
RPOP
RET
HAIRETSU DC ‘ABCDEFGH’
MOJI DC ‘Pos=’
ICHI DS 1
LEN DC 5
MOJI2 DC ‘MITUKARANAKATTA’
LEN2 DC 15
END
赤枠の部分を変えて、
見つからなかった場合や、探索文字をBなどの前側で
動作させてみて、無事に動きました。
探索文字をBにして、Bさんを探した結果。
この配列にないZさんを探した結果。
読んで下さってありがとうございました。
この記事を書くのに勉強になった本を紹介します。
多分この記事を読んで面白かったと思われた方は、
きっとハマると思います。
◆アルゴリズム問題がちゃんと解ける本
アルゴリズム学習の定番。
アルゴリズムが苦手で何とかしたい方におススメ
◆アルゴリズムはじめの一歩完全攻略
実際に作って学べます。
Javaを使っています。
私はJava初めてでしたが、
それでも、ハッシュ関数の所までは、
どうにかついていけました。
もっと頑張ります。
◆速習言語CASL2
CASL2、何それ、テーマパークの絶叫マシーン
みたいな名前だね、ぐらいだった私でも、入門書として楽しく読めた本です。
◆プログラミング入門CASL2
入門が卒業出来たら、ガシガシ例題解いて、
演習問題を解いて、力を付けたいという時に
読む本です。