CASL2で回文判定

ところで、「回文」をご存知ですか？「しんぶんし」などの前後から読んでも同じ言葉になる文章のことです。


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

回文判定

例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行)のトレース】


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


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

回文とは？

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


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


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


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


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


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



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


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

最後に

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


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


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


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