/ 最近 .rdf 追記 編集 設定 本棚

脳log[20110819] Problem 101



2011年08月19日 (金) [ProjectEuler] くっそう。「これは、線型方程式を解くだけなので簡単です。」なんて言ってみたいぜ。手で解く手順は見当がついても脳のキャパをオーバーしてるのでうまくコーディングできない。Wishlistから『プログラミングのための線形代数』を掘り出してきたので、そのうち。

最終更新: 2011-09-10T23:55+0900

[ProjectEuler] Problem 101

 Problem 101

(↑↑のリンク先を見て)行列を使うことがわかればなんとか。最初に考えた階差数列とか二項係数を使った手順とはなんだったのか。要の逆行列の計算(もう忘れた)は Rubyがやってくれるし。だけど最初は行列の要素が整数だったせいで正しい逆行列が得られなくてハマった。

浮動小数点数や有理数その他に対応するために、Matrix#inverseは演算の手続きだけを提供してる、ということなんだと思うけど、全くでたらめな結果が正常に返ってくるのは驚き。元の行列と逆行列の要素がどちらも整数になることがわかってる場合はなおさら。型指定がないことで扱いが難しくなってしまってる。

このへん(ja.wikipedia.org)まで理解したいなあ。

require 'matrix'

# (a0,a1,a2,a3,...) -> (n) -> a0 + a1*n + a2*n^2 + a3*n^3 +...
Poly = lambda{|*kk|
	kk.reverse!
	return lambda{|n|
		return kk.inject(0){|sum,k|
			sum * n + k
		}
	}
}
Q = [1,-1,1,-1,1,-1,1,-1,1,-1,1]
QSeq = Poly[*Q] # (n) -> 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^10

Main = lambda{
	sum_of_FIT = 0
	a, n = [QSeq[0]], 0
	until a == Q
		aseq = Poly[*a]
		raise if aseq[n] != QSeq[n]
		n += 1 while aseq[n] == QSeq[n]
		sum_of_FIT += aseq[n]
		a = Next_OP[QSeq, n]
	end
	p sum_of_FIT
}

Next_OP = lambda{|seq, k|
	return (Matrix[
		*(1..k).map{|i| _ = [1.0]; (k-1).times{ _.push(_.last*i) }; _ }
	].inverse * Matrix[
		*(1..k).map{|_| [seq[_]] }
	]).column(0).to_a.map(&:round)
}

Main.call