ところで、「回文」をご存知ですか?「しんぶんし」などの前後から読んでも同じ言葉になる文章のことをいいます。回文は、前と後ろからの読みを同じにすることに加え、文章の意味も通じるように考えないといけないため、とても頭を使う作業になります。
今回は、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行)のトレース】
初期状態
【汎用レジスタ】
【フラグレジスタ】
5行 LAD GR1, 0
【汎用レジスタ】
【フラグレジスタ】
6行 LD GR4, STRLEN
【汎用レジスタ】
【フラグレジスタ】
「STRLEN」番地の値9をGR2に転送します。
~1ループ目~
7行 LAD GR4, -1, GR4
【汎用レジスタ】
【フラグレジスタ】
8行 LD GR2, STR, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 0 |
GR2 | 1000001 |
GR3 | ? |
GR4 | 1000 |
【フラグレジスタ】
STR+0番地からGR2に「A」の文字コードを転送します。
9行 LD GR3, STR, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 0 |
GR2 | 1000001 |
GR3 | 1000001 |
GR4 | 1000 |
【フラグレジスタ】
STR+8番地からGR3に「A」の文字コードを転送します。
10行 LAD GR1, 1, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 1 |
GR2 | 1000001 |
GR3 | 1000001 |
GR4 | 1000 |
【フラグレジスタ】
11行 CPA GR2, GR3
【汎用レジスタ】
GR0 | ? |
GR1 | 1 |
GR2 | 1000001 |
GR3 | 1000001 |
GR4 | 1000 |
【フラグレジスタ】
CPA命令で、GR2の値「A」の文字コードとGR3の値「A」の文字コードを比較します。
「A」の文字コード=「A」の文字コードのためフラグレジスタが変化します。
12行 JZE MATCH
【フラグレジスタ】
ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。
15行 CPA GR1, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 1 |
GR2 | 1000001 |
GR3 | 1000001 |
GR4 | 1000 |
【フラグレジスタ】
CPA命令で、GR1の値1とGR4の値9を比較します。
1<9のためフラグレジスタが変化します。
16行 JMI LP1
【フラグレジスタ】
SFが1のため、JMI命令で指定されたラベル「LP1」に移動し7行を処理します。
~2ループ目~
7行 LAD GR4, -1, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 1 |
GR2 | 1000001 |
GR3 | 1000001 |
GR4 | 111 |
【フラグレジスタ】
8行 LD GR2, STR, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 1 |
GR2 | 1000010 |
GR3 | 1000001 |
GR4 | 111 |
【フラグレジスタ】
STR+1番地からGR2に「B」の文字コードを転送します。
9行 LD GR3, STR, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 1 |
GR2 | 1000010 |
GR3 | 1000010 |
GR4 | 111 |
【フラグレジスタ】
STR+7番地からGR3に「B」の文字コードを転送します。
10行 LAD GR1, 1, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 10 |
GR2 | 1000010 |
GR3 | 1000010 |
GR4 | 111 |
【フラグレジスタ】
11行 CPA GR2, GR3
【汎用レジスタ】
GR0 | ? |
GR1 | 10 |
GR2 | 1000010 |
GR3 | 1000010 |
GR4 | 111 |
【フラグレジスタ】
CPA命令で、GR2の値「B」の文字コードとGR3の値「B」の文字コードを比較します。
「B」の文字コード=「B」の文字コードのためフラグレジスタが変化します。
12行 JZE MATCH
【フラグレジスタ】
ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。
15行 CPA GR1, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 10 |
GR2 | 1000010 |
GR3 | 1000010 |
GR4 | 111 |
【フラグレジスタ】
CPA命令で、GR1の値2とGR4の値7を比較します。
2<7のためフラグレジスタが変化します。
16行 JMI LP1
【フラグレジスタ】
SFが1のため、JMI命令で指定されたラベル「LP1」に移動し7行を処理します。
~3ループ目~
7行 LAD GR4, -1, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 10 |
GR2 | 1000010 |
GR3 | 1000010 |
GR4 | 110 |
【フラグレジスタ】
8行 LD GR2, STR, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 10 |
GR2 | 1000011 |
GR3 | 1000010 |
GR4 | 110 |
【フラグレジスタ】
STR+2番地からGR2に「C」の文字コードを転送します。
9行 LD GR3, STR, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 10 |
GR2 | 1000011 |
GR3 | 1000011 |
GR4 | 110 |
【フラグレジスタ】
STR+6番地からGR3に「C」の文字コードを転送します。
10行 LAD GR1, 1, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 11 |
GR2 | 1000011 |
GR3 | 1000011 |
GR4 | 110 |
【フラグレジスタ】
11行 CPA GR2, GR3
【汎用レジスタ】
GR0 | ? |
GR1 | 11 |
GR2 | 1000011 |
GR3 | 1000011 |
GR4 | 110 |
【フラグレジスタ】
CPA命令で、GR2の値「C」の文字コードとGR3の値「C」の文字コードを比較します。
「C」の文字コード=「C」の文字コードのためフラグレジスタが変化します。
12行 JZE MATCH
【フラグレジスタ】
ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。
15行 CPA GR1, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 11 |
GR2 | 1000011 |
GR3 | 1000011 |
GR4 | 110 |
【フラグレジスタ】
CPA命令で、GR1の値3とGR4の値6を比較します。
3<6のためフラグレジスタが変化します。
16行 JMI LP1
【フラグレジスタ】
SFが1のため、JMI命令で指定されたラベル「LP1」に移動し7行を処理します。
~4ループ目~
7行 LAD GR4, -1, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 11 |
GR2 | 1000011 |
GR3 | 1000011 |
GR4 | 101 |
【フラグレジスタ】
8行 LD GR2, STR, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 11 |
GR2 | 1000100 |
GR3 | 1000011 |
GR4 | 101 |
【フラグレジスタ】
STR+3番地からGR2に「D」の文字コードを転送します。
9行 LD GR3, STR, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 11 |
GR2 | 1000100 |
GR3 | 1000100 |
GR4 | 101 |
【フラグレジスタ】
STR+5番地からGR3に「D」の文字コードを転送します。
10行 LAD GR1, 1, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 100 |
GR2 | 1000100 |
GR3 | 1000100 |
GR4 | 101 |
【フラグレジスタ】
11行 CPA GR2, GR3
【汎用レジスタ】
GR0 | ? |
GR1 | 100 |
GR2 | 1000100 |
GR3 | 1000100 |
GR4 | 101 |
【フラグレジスタ】
CPA命令で、GR2の値「D」の文字コードとGR3の値「D」の文字コードを比較します。
「D」の文字コード=「D」の文字コードのためフラグレジスタが変化します。
12行 JZE MATCH
【フラグレジスタ】
ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。
15行 CPA GR1, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 100 |
GR2 | 1000100 |
GR3 | 1000100 |
GR4 | 101 |
【フラグレジスタ】
CPA命令で、GR1の値4とGR4の値5を比較します。
4<5のためフラグレジスタが変化します。
16行 JMI LP1
【フラグレジスタ】
SFが1のため、JMI命令で指定されたラベル「LP1」に移動し7行を処理します。
~5ループ目~
7行 LAD GR4, -1, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 100 |
GR2 | 1000100 |
GR3 | 1000100 |
GR4 | 100 |
【フラグレジスタ】
8行 LD GR2, STR, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 100 |
GR2 | 1000101 |
GR3 | 1000100 |
GR4 | 100 |
【フラグレジスタ】
STR+4番地からGR2に「E」の文字コードを転送します。
9行 LD GR3, STR, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 100 |
GR2 | 1000101 |
GR3 | 1000101 |
GR4 | 100 |
【フラグレジスタ】
STR+4番地からGR3に「E」の文字コードを転送します。
10行 LAD GR1, 1, GR1
【汎用レジスタ】
GR0 | ? |
GR1 | 101 |
GR2 | 1000101 |
GR3 | 1000101 |
GR4 | 100 |
【フラグレジスタ】
11行 CPA GR2, GR3
【汎用レジスタ】
GR0 | ? |
GR1 | 101 |
GR2 | 1000101 |
GR3 | 1000101 |
GR4 | 100 |
【フラグレジスタ】
CPA命令で、GR2の値「E」の文字コードとGR3の値「E」の文字コードを比較します。
「E」の文字コード=「E」の文字コードのためフラグレジスタが変化します。
12行 JZE MATCH
【フラグレジスタ】
ZFが1のため、JZE命令で指定されたラベル「MATCH」に移動し15行を処理します。
15行 CPA GR1, GR4
【汎用レジスタ】
GR0 | ? |
GR1 | 101 |
GR2 | 1000101 |
GR3 | 1000101 |
GR4 | 100 |
【フラグレジスタ】
CPA命令で、GR1の値5とGR4の値4を比較します。
5<4のためフラグレジスタに変化はありません。
16行 JMI LP1
【フラグレジスタ】
SFが0のため、JMI命令で指定されたラベル「LP1」に移動せず17行を処理します。
15行 OUT TRU, BOOLEN
【汎用レジスタ】
GR0 | ? |
GR1 | 101 |
GR2 | 1000101 |
GR3 | 1000101 |
GR4 | 100 |
【フラグレジスタ】
OUT命令で、TRU番地の値「TRUE_」をディスプレイに出力します。
18行 RET
RET命令で、「PAL」サブルーチンを抜けて、呼び出し元の「MAIN」サブルーチンに戻り処理が終了します。
文字列「ABCDEDCBA」は、回文のため、答えは「真」を示す「TRUE_」が表示されます。
したがって、正しい答えになっていますね。
回文とは?
回文とは、前から読んでも、後ろから読んでも同じ言葉として成立する文章のことをいいます。
例えば、「しんぶんし」や「イカした歯科医」などが挙げられるでしょう。
回文を考える際は、意味が通るように工夫する必要もあるため、大変に頭を使う文章でもあります。
今回プログラムで判定した回文「ABCDEDCBA」は、意味が通らない文字列のため、厳密には回文とはいえません。
しかし、意味が伴うか否かを抜きにしても、回文とは、前から
1番目と後ろから
1番目が同じ、前から
2番目と後ろから
2番目が同じ...というように前後の
同一番目で同じ文字が対応することに変わりはありません。
したがって、簡易的に「ABCDEDCBA」を例に用いました。
確かな回文の例は下記のサイト様にたくさん載せられていますので、参考にしてみてください。
「
言葉遊び『おもしろ回文』一覧 50選|キッズの無料学習プリント素材」
最後に
今回は、回文の判定方法についてご紹介しました。
回文は、前と後ろから数えた同一番目の文字が同じか否かを確かめればいい、という処理です。
したがって、今回紹介したプログラムに拘(こだわ)らず、上記の処理を実現できればいいため、他のパターンのプログラムも考えてみてください。
それでは、続きはまた次回にご期待を!