アセンブラCASL2で「二分探索」を作ってみた

この記事では、アセンブラ言語で「二分探索法」について簡単な例題で学べます。
シンプルな図解を用いています。また、アセンブラとアルゴリズムのの本の紹介もしています。

<<関連記事>>

基本情報技術者試験トップへ
アセンブラ自作サンプルへ
アセンブラ過去問プログラムへ
令和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
入門が卒業出来たら、ガシガシ例題解いて、
演習問題を解いて、力を付けたいという時に
読む本です。

基本情報技術者試験トップへ
アセンブラ自作サンプルへ
アセンブラ過去問プログラムへ
これからプログラミングを始める方へ