小町算
Posted feedbacks - Common Lisp
kozima
#4743()
[
Common Lisp
]
とりあえず適当に全探索。候補を5進8桁の整数と同一視して dotimes で回してます。結果は101 件、CLISP で 16 秒でした。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | (defun apply-op (op x y)
(case op
(#\+ (+ x y))
(#\- (- x y))
(#\* (* x y))
(#\/ (/ x y))
(#\SPACE (+ (* 10 x) y))
(t 't)))
(defun precedence (op) (case op ((#\+ #\-) 1) ((#\* #\/) 2) (t 3)))
(defun precedence< (op1 op2) (< (precedence op1) (precedence op2)))
(defun eval-string (s)
(loop with vstack and opstack
for c across s
if (digit-char-p c) do
(push (parse-integer (string c)) vstack)
else if #1=(or (null opstack) (precedence< (car opstack) c)) do
(push c opstack)
else do
(loop until #1# do
#2=(setf vstack
(cons (apply-op (pop opstack) (cadr vstack) (car vstack))
(cddr vstack))))
(push c opstack)
finally
(loop for op in opstack do #2#)
(return (car vstack))))
(defun komachi ()
(let ((s (copy-seq "1 2 3 4 5 6 7 8 9")))
(dotimes (x (expt 5 8))
(dotimes (i 8)
(setf (elt s (+ i i 1)) (elt " +-*/" (rem (floor x (expt 5 i)) 5))))
(if (= (eval-string s) 100) (write-line s)))))
|
dpp
#4509()
Rating0/2=0.00
古典的なパズルである小町算を解くプログラムを作成してください。
小町算とは：
1□2□3□4□5□6□7□8□9＝100
四角の中に、空白、＋、－、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。
解答例：
1－2－3＋4×56÷7＋8×9＝100
1＋234×5÷6－7－89＝100
参考： http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97
手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。
[ reply ]