Euler: Problem 93

Posted by TAKAIY On 2013年2月8日金曜日 0 コメント


4つの数字を加減乗除して作れる数を求める問題です。

しばらく考えてはみたのですが、総当たり以外にやりかたはなさそうなので、それで実装してます。
2分くらいかかってしまっていますが、まあ、よしとします。



対象となる数字の組み合わせは、0から9までの数から4つです。10C4=210通りです。
それぞれについて、数字を並べ変えたものは、4P4=24通りです。
加減乗除は3つなので、4^3=64通りです。
括弧の付けかたは、すごくたくさんありそうでうんざりしていたのですが、作ってみると意外に少なくて、
演算子を?とすると、
 a ? b ? c ? d
 a ? (b ? c) ? d
 a ? b ? (c ? d)
 a ? (b ? c ? d)
の4つであることがわかりました。他の括弧の組み合わせは、他の数字の並び換えで登場するか、
上記のどれかと同じになります。
結局 210*24*64*4=1290240通りの組み合わせを計算すればよさそうなので、それほど時間はかからないはずです。


・calc-all-paren-combo
 演算子のリストと数字のリストを与えると、全ての括弧のパターンで計算した結果を返します。

・calc
マクロです。
計算式を与えると、以下の場合にnilを返します。
-0での除算が発生したとき
-答えが正の整数でないとき

・calc-all-patterns
数字のリストと演算子の組み合わせリストを与えると、全ての数字の組替えについての計算結果を返します。
結果は、重複を除いて、昇順にならべます。

・count-seq-from-1
数字のリストがどこまで1から順になっているか数えます。
ちょっとclojureっぽい?

0 コメント:

コメントを投稿