Euler : Probllem 24

Posted by TAKAIY On 2011年5月11日水曜日 0 コメント

順列の1000000番目はなに?って問題だけど、樹形図を考えてこんな手順にした。

先頭に0があるやつは、 9! で 362880通り。1000000をこえない
先頭に1があるやつも、 9! で 362880通り。1000000をこえない
先頭に2があるやつは、 9! で 362880通りで、1000000をこえてしまうから、先頭は2
次は20で始まるやつは、8! で 40320通りで1000000をこえない
....って順に求めていく。

;;
;; Problem 24 : 2011/5/10
;; "Elapsed time: 1.543492 msecs"
(def fact-tree
[362880 40320 5040 720 120 24 6 2 1])

(use 'clojure.contrib.math)

(loop [fact-tree fact-tree
num-list [0 1 2 3 4 5 6 7 8 9]
remains (dec 1000000)
res-list ()]
(if (empty? fact-tree)
(concat (reverse res-list) num-list)
(let [div (floor (/ remains (first fact-tree)))
tgt-num (nth num-list div)]
(recur (rest fact-tree)
(remove #(= % tgt-num) num-list)
(rem remains (first fact-tree))
(cons tgt-num res-list)))))
;;


0 コメント:

コメントを投稿