musik

久しぶりにプロジェクトオイラー。問題2。１年ほどかかって、1桁ができていない。こういう人間もいる、ということで。

ここにあるソースを学校で使う人がいるとは思いませんが、万一使うと、大量に怒られるような内容に（意図はしていませんが）、なっていると思います。お気をつけ下さい。

Haskell版。無限リストを使っても良さそうに思ったが、それでは動かなかった（結果がいつまでも返ってこない）。そのため、マジックナンバーで上限を抑えるの挙に出た。回答が返ってきて、かつ、意味のある回答になるよう調整する。ああ、悲しい。

Ruby版とHaskell版で回答が同じになったので、よしとしているが、本当にあっているのかな？
計算時間はHaskell版の方が長い。これも異なように思われる。

まずはHaskell版。リスト内包表記を使うともう戻れない。が、複雑化した場合に対処しきれる気はしない。

fiv 1 = 1

fiv 2 = 2

fiv n = fiv (n-1) + fiv (n-2) 


main = do print $ sum [x | x<-map fiv [1..40], x<4000000, even x] 

ここで利用しているフィボナッチ関数で得た４００万以下の数列は以下のごとし。
[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578]

偶数だけ抽出すると以下のごとし。
[2,8,34,144,610,2584,10946,46368,196418,832040,3524578]

合計すると以下のとおり。
4613732

計算時間は以下の如し。
real 1m19.321s
user 1m18.793s
sys 0m0.264s

こちらはruby版。デバッグ出力が普通にできるのが嬉しい。

#!/usr/bin/ruby


def fiv(n)

	if n <= 0 then

		r = 0

	elsif n == 1 then

		r = 1

	elsif n == 2 then

		r = 2

	else

		r = fiv(n-1) + fiv(n-2)

	end

#	print "n=",n,",fiv=",r,"\n"

	r

end

c = 1

sum = 0

while c <400

	

	r = fiv(c)

	if 4000000 < r then

		print "r=",r,"\n"

		print "sum=",sum,"\n"

		exit

	elsif r % 2 == 0 then

		print "c=",c,",r=",r,",sum=",sum,"\n"

		sum = sum + r

	end

	c = c + 1

end

デバッグ出力の経過は以下の如し。
c=2,r=2,sum=0
c=5,r=8,sum=2
c=8,r=34,sum=10
c=11,r=144,sum=44
c=14,r=610,sum=188
c=17,r=2584,sum=798
c=20,r=10946,sum=3382
c=23,r=46368,sum=14328
c=26,r=196418,sum=60696
c=29,r=832040,sum=257114
c=32,r=3524578,sum=1089154
r=5702887
sum=4613732

ruby版の実行時間はこんなもの（たかが4799.41bogomipsの古いマシンなので）。
real 0m17.065s
user 0m16.949s
sys 0m0.012s