Euler: Problem 101

Posted by YpsilonTAKAI On 2015年6月21日日曜日 0 コメント
久し振りにProject Eulerを解きました。
(※ なんと4年前に書いた下書きがそのままになっていた)

数列がはじめからN個与えられたときに得られる母関数では、N+1まで行くと間違った値(BOP)が出ます。 与える数列を増やしていったときに得られるすべてのBOPの和を求める問題です。

そういえば、こういうのって、補間法かなんか使えば出るんじゃなかったっけ…と思って解いたら解けました。
ウィキペディアで調べたら、ラグランジェ補間法ってやつだったので、まあ、そのまま、式にした感じです。

コメントにも書きましたけど、もうちょっとclojureらしく書いたほうがよかったのかもしれないんですが、そうすると、たぶん、元の式の形がなくなってしまいそう。


;; Prablem 101
;;"Elapsed time: 14.696085 msecs"
;; 準備
(defn exp [x n]
(reduce * (repeat n x)))
;; 題意の式の数列を返す関数
(defn un-seq []
(let [un (fn [n]
(reduce +
(map #(* (exp -1 %)
(exp n %))
(range 11))))]
(map un (iterate inc 1))))
(defn x [i]
(inc i))
;; Lagrange係数多項式
(defn lagrange [xt k num]
(reduce *
(for [i (range num) :when (not= i k)]
(/ (- xt (x i))
(- (x k) (x i))))))
;; Lagrange補間多項式を使って解を出す
;; もう一段関数を使ってもよかったか
(defn next-val [vals]
(let [x-range (count vals)
next-x (inc x-range)]
(reduce +
(for [k (range x-range)]
(* (nth vals k)
(lagrange next-x k x-range))))))
;; もうちょっとclojureらしい書きかたもできそうだったが、
;; 元の式の形を残すことにこだわってみた。
(defn pe-101 []
(reduce +
(for [turn (range 1 11)]
(next-val (take turn (un-seq))))))
view raw pe_101.clj hosted with ❤ by GitHub
ラベル: ,

0 コメント:

コメントを投稿