Archive for 2013年4月30日|Daily archive page

projecteuler4(続き)...または、組み合わせの求め方

 さて、問題4 の続きです。
 三桁の数同士を掛け算して、最大の回文数を求めるために、最初に回文数を用意します。

(setq digit 3
       max-num (pow 10 digit)
       numbers (sequence (pow 10 (- digit 1)) (- max-num 1))
       strings1 (map string numbers)
       strings2 (map reverse strings1)
       palindromes (map int (map append strings1 strings2)))

 palindromes の中に回文数が小さい順に入っています。それを newLISP 組込関数 reverse を使って順を逆にして、大きい順から一個一個、三桁の数同士の掛け算になるかどうかを確認します。
 そのために、例えば 906609 を newLISP 組込関数 factor で因数分解すると、

> (factor 906609)
(3 11 83 331)
> 

 このままでは、三桁の数同士の掛け算になるかどうか判りません。4つの数値を組み合わせて、二つの掛け算にする必要があります。
 その組み合わせは、

((3 11 83) (331))
((3 11 331) (83))
((3 11) (83 331))
((3 83 331) (11))
((3 83) (11 331))
((3 331) (11 83))
((3) (11 83 331))

 の7通り、リスト (3 11 83 331) の位置で表すと、

(0 0 0 1)
(0 0 1 0)
(0 0 1 1)
(0 1 0 0)
(0 1 0 1)
(0 1 1 0)
(0 1 1 1)

 と、こんな感じ。お気づきでしょうか、この組み合わせ方を binary counting と言うそうです。ここまで来れば、あとは実装するだけ。それが、前回紹介したコードになります。実行時間は早いはず、わずか 94 個目で解答にたどり着くわけですから(笑)。

 以上、如何でしょうか?

広告