Problem25

Python 30分プログラム

30分プログラム、その296。Problem25 via ProjectEuler。

フィボナッチ数列は以下の漸化式で定義される:

F(n) = F(n-1) + F(n-2), ただし F(1) = 1, F(2) = 1.

最初の12項は以下である.

  • F(1) = 1
  • F(2) = 1
  • F(3) = 2
  • F(4) = 3
  • F(5) = 5
  • F(6) = 8
  • F(7) = 13
  • F(8) = 21
  • F(9) = 34
  • F(10) = 55
  • F(11) = 89
  • F(12) = 144

12番目の項, F12が3桁になる最初の項である.
1000桁になる最初の項の番号を答えよ.

最初はPerlでやろうとしたら10**1000程度の数値を扱えなかったので、Pythonに変更。Perlの数値型はdoubleの範囲しか扱えないらしいですよ。
それと再帰でフィボナッチ数を計算しようとしたら、再帰が深すぎると怒られたのでwhileに変更。末尾再帰にしたほうが格好よかったかもしれない。

使い方

$ time python problem25.py
4782
python problem25.py  1.35s user 0.12s system 89% cpu 1.648 total

ソースコード

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

# def fib(n):
#    if n == 0 or n == 1:
#	return (1,1);
#    else:
#        (x,y) = fib(n - 1)
#        return (x+y,x)

i = 1
(current,prev) = (1,0)
while len(str(current)) < 1000:
    (current,prev) = (current+prev,current)
    i+=1

print i

参考