ニッシー
1990年生まれ
血液型 O型

こんにちは。ITブログアルケーナム管理人のニッシーです。

詳細プロフィールへ

お問い合わせへ






2019-06-19

CASL2で回文判定







ところで、「回文」をご存知ですか?「しんぶんし」などの前後から読んでも同じ言葉になる文章のことをいいます。回文は、前と後ろからの読みを同じにすることに加え、文章の意味も通じるように考えないといけないため、とても頭を使う作業になります。


今回は、CASL2を使用して、コンピュータが回文をどのように判定しているかについて、その方法の一例として見てみたいと思います。


とはいえ、COMET2程度のコンピュータでは、文字の並びが回文かどうかは判定できても、意味が通じるかどうかまでは判定できないため、本記事では回文の意味については考慮しないプログラムを紹介します。














回文判定



例1: 回文「ABCDEDCBA」の判定

1 MAIN START 
2   CALL PAL 
3   RET 
4    
5 PAL LAD GR1, 0 ;前半文字の現在位置
6   LD GR4, STRLEN ;回文の長さ
7 LP1 LAD GR4, -1, GR4 ;回文の長さをデクリメント
8   LD GR2, STR, GR1 ;回文前半の文字
9   LD GR3, STR, GR4 ;回文後半の文字
10   LAD GR1, 1, GR1 ;前半文字の現在位置をインクリメント
11   CPA GR2, GR3 ;前半と後半の文字を比較
12   JZE MATCH ;同じ文字なら"MATCH"行へ
13   OUT FAL, BOOLEN ;違う文字なら"偽"判定
14   RET 
15 MATCH CPA GR1, GR4 ;前半文字位置<後半文字位置 であるか判定
16   JMI LP1 ;前半文字位置<後半文字位置 であるならラベルLP1へ
17   OUT TRU, BOOLEN ;前半文字位置<後半文字位置 でないなら"真"判定
18   RET 
19    
20 STR DC 'ABCDEDCBA' ;回文
21 STRLEN DC 9 ;回文の長さ
22 TRU DC 'TRUE_' ;回文のとき
23 FAL DC 'FALSE' ;回文でないとき
24 BOOLEN DC 5  ;判定文言の長さ
25   END 

シミュレータにそのままコピー&ペーストで使えます。



解説



回文判定は、最初の文字と最後の文字が同じか否か、最初から2番目の文字と最後から2番目の文字が同じか否か...というように順番に文字の違いを判定していきます。


文字の最初と最後の比較から始まって、参照する文字位置が真ん中で交わったときに終了します。真ん中の文字位置まで参照が終了した場合は、回文であるため、「真」を示します。


一方で、真ん中の文字位置まで参照する途中で文字に違いがあった場合は、その時点で「偽」を示します。


このプログラムの場合は、「TRUE_」と「FALSE」をそれぞれ真と偽を指す情報としてディスプレイに表示させるように組まれています。


とりわけ、判定した文字列が、真か偽のいずれかを表せればいいため、ディスプレイに表示する文字は、好きな表示に変えてしまって大丈夫です。


「TRUE_」の最後の文字「_ (アンダースコア)」は、「FALSE」と文字数を合わせるためにつけ加えています。ここでは、アンダースコアを使用していますが、スペースに置き換えても大丈夫です。


文字数を合わせないと、プログラム上の不整合があるため、その穴埋めにこのように記述してあります。どのような不整合かについては、一旦、横に置いておきます。


【回文判定の方法】



ここで、トレースを見てみましょう。



【例1のPAL(5~18行)のトレース】


初期状態

【汎用レジスタ】
GR0?
GR1?
GR2?
GR3?
GR4?

【フラグレジスタ】
ZFSFOF
000



5行 LAD GR1, 0

【汎用レジスタ】
GR0?
GR10
GR2?
GR3?
GR4?

【フラグレジスタ】
ZFSFOF
000



6行 LD GR4, STRLEN

【汎用レジスタ】
GR0?
GR10
GR2?
GR3?
GR41001

【フラグレジスタ】
ZFSFOF
000

「STRLEN」番地の値9をGR2に転送します。



~1ループ目~

7行 LAD GR4, -1, GR4

【汎用レジスタ】
GR0?
GR10
GR2?
GR3?
GR41000

【フラグレジスタ】
ZFSFOF
000



8行 LD GR2, STR, GR1

【汎用レジスタ】
GR0?
GR10
GR21000001
GR3?
GR41000

【フラグレジスタ】
ZFSFOF
000

STR+0番地からGR2に「A」の文字コードを転送します。



9行 LD GR3, STR, GR4

【汎用レジスタ】
GR0?
GR10
GR21000001
GR31000001
GR41000

【フラグレジスタ】
ZFSFOF
000

STR+8番地からGR3に「A」の文字コードを転送します。



10行 LAD GR1, 1, GR1

【汎用レジスタ】
GR0?
GR11
GR21000001
GR31000001
GR41000

【フラグレジスタ】
ZFSFOF
000



11行 CPA GR2, GR3

【汎用レジスタ】
GR0?
GR11
GR21000001
GR31000001
GR41000

【フラグレジスタ】
ZFSFOF
100

CPA命令で、GR2の値「A」の文字コードとGR3の値「A」の文字コードを比較します。
「A」の文字コード=「A」の文字コードのためフラグレジスタが変化します。



12行 JZE MATCH

【フラグレジスタ】
ZFSFOF
100

ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。



15行 CPA GR1, GR4

【汎用レジスタ】
GR0?
GR11
GR21000001
GR31000001
GR41000

【フラグレジスタ】
ZFSFOF
010

CPA命令で、GR1の値1とGR4の値9を比較します。
1<9のためフラグレジスタが変化します。



16行 JMI LP1

【フラグレジスタ】
ZFSFOF
010

SFが1のため、JMI命令で指定されたラベル「LP1」に移動し7行を処理します。



~2ループ目~

7行 LAD GR4, -1, GR4

【汎用レジスタ】
GR0?
GR11
GR21000001
GR31000001
GR4111

【フラグレジスタ】
ZFSFOF
010



8行 LD GR2, STR, GR1

【汎用レジスタ】
GR0?
GR11
GR21000010
GR31000001
GR4111

【フラグレジスタ】
ZFSFOF
010

STR+1番地からGR2に「B」の文字コードを転送します。



9行 LD GR3, STR, GR4

【汎用レジスタ】
GR0?
GR11
GR21000010
GR31000010
GR4111

【フラグレジスタ】
ZFSFOF
010

STR+7番地からGR3に「B」の文字コードを転送します。



10行 LAD GR1, 1, GR1

【汎用レジスタ】
GR0?
GR110
GR21000010
GR31000010
GR4111

【フラグレジスタ】
ZFSFOF
010



11行 CPA GR2, GR3

【汎用レジスタ】
GR0?
GR110
GR21000010
GR31000010
GR4111

【フラグレジスタ】
ZFSFOF
100

CPA命令で、GR2の値「B」の文字コードとGR3の値「B」の文字コードを比較します。
「B」の文字コード=「B」の文字コードのためフラグレジスタが変化します。



12行 JZE MATCH

【フラグレジスタ】
ZFSFOF
100

ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。



15行 CPA GR1, GR4

【汎用レジスタ】
GR0?
GR110
GR21000010
GR31000010
GR4111

【フラグレジスタ】
ZFSFOF
010

CPA命令で、GR1の値2とGR4の値7を比較します。
2<7のためフラグレジスタが変化します。



16行 JMI LP1

【フラグレジスタ】
ZFSFOF
010

SFが1のため、JMI命令で指定されたラベル「LP1」に移動し7行を処理します。



~3ループ目~

7行 LAD GR4, -1, GR4

【汎用レジスタ】
GR0?
GR110
GR21000010
GR31000010
GR4110

【フラグレジスタ】
ZFSFOF
010



8行 LD GR2, STR, GR1

【汎用レジスタ】
GR0?
GR110
GR21000011
GR31000010
GR4110

【フラグレジスタ】
ZFSFOF
010

STR+2番地からGR2に「C」の文字コードを転送します。



9行 LD GR3, STR, GR4

【汎用レジスタ】
GR0?
GR110
GR21000011
GR31000011
GR4110

【フラグレジスタ】
ZFSFOF
010

STR+6番地からGR3に「C」の文字コードを転送します。



10行 LAD GR1, 1, GR1

【汎用レジスタ】
GR0?
GR111
GR21000011
GR31000011
GR4110

【フラグレジスタ】
ZFSFOF
010



11行 CPA GR2, GR3

【汎用レジスタ】
GR0?
GR111
GR21000011
GR31000011
GR4110

【フラグレジスタ】
ZFSFOF
100

CPA命令で、GR2の値「C」の文字コードとGR3の値「C」の文字コードを比較します。
「C」の文字コード=「C」の文字コードのためフラグレジスタが変化します。



12行 JZE MATCH

【フラグレジスタ】
ZFSFOF
100

ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。



15行 CPA GR1, GR4

【汎用レジスタ】
GR0?
GR111
GR21000011
GR31000011
GR4110

【フラグレジスタ】
ZFSFOF
010

CPA命令で、GR1の値3とGR4の値6を比較します。
3<6のためフラグレジスタが変化します。



16行 JMI LP1

【フラグレジスタ】
ZFSFOF
010

SFが1のため、JMI命令で指定されたラベル「LP1」に移動し7行を処理します。



~4ループ目~

7行 LAD GR4, -1, GR4

【汎用レジスタ】
GR0?
GR111
GR21000011
GR31000011
GR4101

【フラグレジスタ】
ZFSFOF
010



8行 LD GR2, STR, GR1

【汎用レジスタ】
GR0?
GR111
GR21000100
GR31000011
GR4101

【フラグレジスタ】
ZFSFOF
010

STR+3番地からGR2に「D」の文字コードを転送します。



9行 LD GR3, STR, GR4

【汎用レジスタ】
GR0?
GR111
GR21000100
GR31000100
GR4101

【フラグレジスタ】
ZFSFOF
010

STR+5番地からGR3に「D」の文字コードを転送します。



10行 LAD GR1, 1, GR1

【汎用レジスタ】
GR0?
GR1100
GR21000100
GR31000100
GR4101

【フラグレジスタ】
ZFSFOF
010



11行 CPA GR2, GR3

【汎用レジスタ】
GR0?
GR1100
GR21000100
GR31000100
GR4101

【フラグレジスタ】
ZFSFOF
100

CPA命令で、GR2の値「D」の文字コードとGR3の値「D」の文字コードを比較します。
「D」の文字コード=「D」の文字コードのためフラグレジスタが変化します。



12行 JZE MATCH

【フラグレジスタ】
ZFSFOF
100

ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。



15行 CPA GR1, GR4

【汎用レジスタ】
GR0?
GR1100
GR21000100
GR31000100
GR4101

【フラグレジスタ】
ZFSFOF
010

CPA命令で、GR1の値4とGR4の値5を比較します。
4<5のためフラグレジスタが変化します。



16行 JMI LP1

【フラグレジスタ】
ZFSFOF
010

SFが1のため、JMI命令で指定されたラベル「LP1」に移動し7行を処理します。



~5ループ目~

7行 LAD GR4, -1, GR4

【汎用レジスタ】
GR0?
GR1100
GR21000100
GR31000100
GR4100

【フラグレジスタ】
ZFSFOF
010



8行 LD GR2, STR, GR1

【汎用レジスタ】
GR0?
GR1100
GR21000101
GR31000100
GR4100

【フラグレジスタ】
ZFSFOF
010

STR+4番地からGR2に「E」の文字コードを転送します。



9行 LD GR3, STR, GR4

【汎用レジスタ】
GR0?
GR1100
GR21000101
GR31000101
GR4100

【フラグレジスタ】
ZFSFOF
010

STR+4番地からGR3に「E」の文字コードを転送します。



10行 LAD GR1, 1, GR1

【汎用レジスタ】
GR0?
GR1101
GR21000101
GR31000101
GR4100

【フラグレジスタ】
ZFSFOF
010



11行 CPA GR2, GR3

【汎用レジスタ】
GR0?
GR1101
GR21000101
GR31000101
GR4100

【フラグレジスタ】
ZFSFOF
100

CPA命令で、GR2の値「E」の文字コードとGR3の値「E」の文字コードを比較します。
「E」の文字コード=「E」の文字コードのためフラグレジスタが変化します。



12行 JZE MATCH

【フラグレジスタ】
ZFSFOF
100

ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。



15行 CPA GR1, GR4

【汎用レジスタ】
GR0?
GR1101
GR21000101
GR31000101
GR4100

【フラグレジスタ】
ZFSFOF
100

CPA命令で、GR1の値5とGR4の値4を比較します。
5<4のためフラグレジスタに変化はありません。



16行 JMI LP1

【フラグレジスタ】
ZFSFOF
100

SFが0のため、JMI命令で指定されたラベル「LP1」に移動せず17行を処理します。



15行 OUT TRU, BOOLEN

【汎用レジスタ】
GR0?
GR1101
GR21000101
GR31000101
GR4100

【フラグレジスタ】
ZFSFOF
100

OUT命令で、TRU番地の値「TRUE_」をディスプレイに出力します。



18行 RET

RET命令で、「PAL」サブルーチンを抜けて、呼び出し元の「MAIN」サブルーチンに戻り処理が終了します。


文字列「ABCDEDCBA」は、回文のため、答えは「真」を示す「TRUE_」が表示されます。


したがって、正しい答えになっていますね。











回文とは?



回文とは、前から読んでも、後ろから読んでも同じ言葉として成立する文章のことをいいます。


例えば、「しんぶんし」や「イカした歯科医」などが挙げられるでしょう。


回文を考える際は、意味が通るように工夫する必要もあるため、大変に頭を使う文章でもあります。


今回プログラムで判定した回文「ABCDEDCBA」は、意味が通らない文字列のため、厳密には回文とはいえません。


しかし、意味が伴うか否かを抜きにしても、回文とは、前から1番目と後ろから1番目が同じ、前から2番目と後ろから2番目が同じ...というように前後の同一番目で同じ文字が対応することに変わりはありません。


したがって、簡易的に「ABCDEDCBA」を例に用いました。



確かな回文の例は下記のサイト様にたくさん載せられていますので、参考にしてみてください。


言葉遊び『おもしろ回文』一覧 50選|キッズの無料学習プリント素材





最後に



今回は、回文の判定方法についてご紹介しました。


回文は、前と後ろから数えた同一番目の文字が同じか否かを確かめればいい、という処理です。


したがって、今回紹介したプログラムに拘(こだわ)らず、上記の処理を実現できればいいため、他のパターンのプログラムも考えてみてください。


それでは、続きはまた次回にご期待を!














プロフィール

ニッシー
1990年生まれ
血液型 O型

こんにちは。ITブログアルケーナム管理人のニッシーです。

詳細プロフィールへ

お問い合わせへ