「うさぎの数が世界人口を越えるには」をやってみる

Perl 30分プログラム

30分プログラム、その583。http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_126をやってみる。

もともとフィボナッチ数は、つがいのうさぎの数を数える時の数列なので、何ヶ月目に現在の世界人口である 66 億 6000 万人をうさぎが越えるかを調べてみます。

フィボナッチ数の計算は、有名なO(n)のアルゴリズムを使いました。

使い方

$ perl fib.pl
1 2
2 2
3 4
4 6
5 10
6 16
7 26
8 42
9 68
10 110
11 178
12 288
13 466
14 754
15 1220
16 1974
17 3194
18 5168
19 8362
20 13530
21 21892
22 35422
23 57314
24 92736
25 150050
26 242786
27 392836
28 635622
29 1028458
30 1664080
31 2692538
32 4356618
33 7049156
34 11405774
35 18454930
36 29860704
37 48315634
38 78176338
39 126491972
40 204668310
41 331160282
42 535828592
43 866988874
44 1402817466
45 2269806340
46 3672623806
47 5942430146
48 9615053952

もとのやつとはfib(0)の値が違うので、1月ほどずれが生じています。

ソースコード

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

use strict;
use warnings;

sub fib_iter($$$) {
    my ($current,$prev,$n) = @_;
    if ($n == 1) {
	$current;
    }else{
	&fib_iter($current+$prev,$current,$n-1);
    }
}

sub fib($){
    my ($n) = @_;
    fib_iter(1,0,$n);
}

for (my $i = 1; ; $i++) {
    my $rabbit = 2 * fib($i);
    print "$i $rabbit\n";
    if($rabbit > 6660000000){
	exit;
    }
}

参考