Project Euler 78, 64, 65
めっきり解く頻度が下がってしまいましたが、今日は3問解きました。
Project Euler 78
この問題は数学において「整数分割 (integer partition) 」と呼ばれる問題そのままのようです。
そんなことに気づかず普通に再帰で解こうとしていて、全く手が出ていない状態でした。
友達が解いているのを見て、私も解きました。
最近そんなのばっかりですね。
しかし、整数分割って、問題はすごく単純なのに解法がなんだか複雑なんですよね。数学者が好んで研究するわけですね。
http://ja.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E5%88%86%E5%89%B2
Project Euler 64
平方根の連分数についての問題です。
PE66 でペル方程式を解いたときのコードとほとんど同じコードで PE64 は解けました。
ペル方程式の解を求める方法が、平方根の連分数を利用しているためそうなります。
Project Euler 65
ネイピア数の連分数についての問題です。
有限な連分数を約分する方法というものがあるようで、それを利用しました。
http://ja.wikipedia.org/wiki/%E9%80%A3%E5%88%86%E6%95%B0
「連分数の性質」というところに、漸化式が書いてあります。
どれもプログラミングの問題というより、数学の問題ですね。
解法は数学者がすでに編み出しているので、私はそれを使うだけでした。