C++での回文判定．
こんにちは。みなみんです。
今回はC++を使った簡単なプログラムの紹介として，
「回文の判定」について記事にしました．
目次
最初に
回文とは
ある文を逆さまに読んでも，正文と全く同じ読み方である文の事．
例えば，
イタリアでありたい → いたりあでアリタイ
カバはバカ → カバはバカ
などなど．
今回のC++での回文判定では，char型やstring型の「文字列型」を使った判定なので，英語の回文で判定します．
英語での回文の例
もちろんの事だが，
英語でも逆さまにした文や単語を読んでも意味は一緒である事には変わりない．
Level → leveL
Madam → madaM
などなど．
回文判定の考え方
回文である条件
- 逆さまから読んでも正文と全く同じ
- 前から後ろからそれぞれ一文字ずつ読んでも同じ．
これらの事から，筆者が思いつく判定のアルゴリズムは2パターン考えられる．
パターン１：正文と逆文を比較する方法
回文というのは，正文を逆文にしても同じであることから，単純にプログラムで文を逆にする処理をして正文と比較するだけの方法．
処理回数は，文字数分とほぼ等しい（？）．
もし，回文でない場合の流れを見てみましょう．
パターン２：前後それぞれ一文字ずつ比較する方法
回文の前後それぞれ同じ文字目で読んでいく事で回文を判定するパターン．
こちらの方法だと，処理回数は文字数の半分なので，
前者の方法よりは少ない処理回数で済む（？）．
（筆者の見解）
これも，回文でない場合の流れを見てみましょう．
回文判定パターン１
仕様
関数を定義して，main関数で呼び出して判定させる．
ここでは，戻り値はint型にしている．
そして，関数の仕様には２つの方法が考えられる．
- char型を第一引数，第一引数の配列の長さを第二引数を取る関数
- char型を第一引数のみを取り，配列の長さは自動的に見つける関数
char型の引数にはどちらも判定したい回文を引数とする．
そして，引数の回文が回文であるなら，1
回文でない場合は，0を返す．
最終的なアルゴリズム
サンプルコードをご覧ください．(Gist)
回文の格納
引数から直接格納します．
そして，char型変数から用意したstring型変数に直接代入します．
文の反転処理
for-r文（逆向きfor文）で文の後ろから一文字ずつ他の変数に代入する．
forの実行回数は「配列の長さ-1 -1」である．これは，最大インデックスを求め方「要素数の-1」とchar型変数に代入した文字列の末尾にヌル文字(\0)が付加されているという事にも考慮している．最終的には「要素数 - 2」である．
配列の長さが不明の場合の処理
配列の長さ（要素数）が不明の時でも，char型変数から一度，string型変数に代入すれば，string変数.size()で文字数は取得する事ができる．
また，ヌル文字はstring型変数に代入する際，除かれる．
for(int i = word_copy.size() - 1; i >= 0; i++)
比較
代入した逆文の変数，正文の変数を比較演算で比較するだけ．
その比較の論理値をif文で条件分岐する．
引数がstring型での回文判定
上記の方法（引数がchar型のアルゴリズム）は少し面倒な感じだったが，string型を引数にとる場合は，ヌル文字などを考慮せずに処理を書く事ができる．
また，サンプルコードでの，char[]型変数の初期化は""で代入していた．
回文判定パターン２
仕様
仕様自体は上記と同様である．違いは判定するプロセスの違いだけである．
最終的なアルゴリズム
サンプルコードをご覧くだだい(Gist)
forの実行回数
前後それぞれ一文字ずつ同時に比較していくので，文字数回繰り返す必要はない．
文字数の半分が実行回数である．よって，
実行回数 = 要素番号の最大値 / 2
なお，回数（変数i）はint型（整数）なので，除算によって出た小数点以下は切り捨てられる．
よって，文字数が奇数の時は，前と後ろからの比較が文の真ん中に到達する際，１文字だけ残ってしまう．だが，文をひっくり返してもその一文字は変わらない．
よって比較する必要はない．
前後○文字目を取り出す
前 → i
後 → 要素番号の最大 - i
比較
比較した結果，両者同じであるならば，先頭にもどる．
（continueはなくても良い）
同じでない場合，それは回文では無くなったので，0を返す．
処理はその地点で終了．
処理が中断されずにfor文の処理を終えたら，回文であるので，１を返す．
この記事に誤りがあるかもしれません。その辺はご了承ください。
本記事で紹介されている方法・手法はあくまでも個人的なものです。
