フィボナッチ数の和

30分プログラム、その260。Project Euler - Problem 2:フィボナッチ数の和。

フィボナッチ数列の項は前の2つの項の和である。最初の2項を1,2とすれば、最初の10項は以下の通りである。

 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。

id:selvaggioに数式による解法を説明してもらったけれど、ちょっと面倒。
要するに、を計算すればいいらしい。フィボナッチ数の一般式の和を計算するのが面倒なのでパス。

使い方

$ perl fib.pl
4613732

ソースコード

#! /usr/bin/perl
# -*- mode:perl; coding:utf-8 -*-
#
# fib.pl -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/03/12 21:16:08
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

use strict;
use warnings;
use List::Util qw(sum);

our %cache = (0=>1,1=>2);
sub fib($){
    my ($n) = @_;

    unless(exists($cache{$n})){
	$cache{$n} = &fib($n-1)+&fib($n-2);
    }
    $cache{$n};
}

sub fibs($){
    my ($n) = @_;
    my @fibs = ();
    my $i = 0;

    while((my $f = fib($i)) < $n){
	push @fibs,$f;
	$i++;
    }
    @fibs;
}

print sum grep { $_ % 2 == 0 } fibs(4_000_000);
print "\n";

参考

• 過去の30分プログラム
• Problem 2 - PukiWiki