「プロジェクトオイラー解説問4」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー解説問4 - (2014/01/09 (木) 09:20:39) のソース

----
*Problem 4 「最大の回文積」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204 

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である. 
では, 3桁の数の積で表される回文数の最大値を求めよ.

----
解法
組み合わせ数が少ないので全部検討しても十分間に合います。
a=100～999=900個
b=100～999=900個
としても
全部で81万個の数字の検討にしかなりません。
最近のパソコンでは処理回数が5億回で1秒かそれ以下ですので、81万回の検討程度なら瞬きする間に終わります。
c=a*b
とします。
100*100=10000<=c<=999*999=998001

10000<=c<=998001
となります。
ｃの桁数によらずに回文となってるか判別する方法は簡単です。

***手法1
一つの方法はｃを文字列に直してリバースメソッド（配列や文字列を逆にする）などを適用し適用したものが同じ文字列になればそれは回文だと判断する方法です。
数字ｃを文字列にしたものが　3457　ならこれにリバースを適用すると7543となります。
3457と7543は同じ文字列ではないので回文ではありませんね。
20002とそのリバース20002は同じなので回文数と判定します。
この手法はたいていの言語で使えるのでお勧めです。


***手法2
各桁を分解して桁の数字を一つずつ配列に入れてから判別する方法。

具体例で考えてみましょう。
cが430032だったとします。
cを整数型とし配列a[6](cは998001が最大なので配列は6個です)を考えます。
cを各桁に分解してaに入れる場合を考えます。

まず
c mod 10 (ｃ++やその系統の言語なら　c%10=c mod 10)で下一桁目の２が取り出せます.
これをa[0]=c mod 10として入れます。
次にc=c/10とします
整数型での割り算は割った結果の小数点以下は切り捨てられ、c=43003となります。
a[1]=c mod 10
c/=10,(cは4300となる)


a[2]=c mod 10
c/=10(cは430となる)
,,,
とループで続けます。
ｃが0になったらループを抜けます。
すると
a[0～5]にはa[0]=2,a[1]=3,a[2]=0,a[3]=0,a[4]=3,a[5]=4
とはいっています。
a[0]=a[5],a[1]=a[4],a[2]=a[3]
となればめでたく回文です。
ｃが4桁の場合と5桁の場合で処理を分けないためのコードは以下の通りです。
cが回文ならtrueをでないならfalseを返す関数は以下の通り。

 bool check(int c){
 int i=0;
 while(c>0){
     //cが0以上の間各桁に分解して配列に入れる
     a[i]=c%10;
     c=c/10;
     i++;
 }
 bool isOK=true;
 for(int j=0;j<i;j++){
       //回文になっているかチェックする
       if(a[i-j-1]!=a[j])isOK=false;//回文でないことが判明
 }
 return isOK;
 }