[ F# / Python ] フィボナッチ数列

via ときどきの雑記帖 リターンズ

MSN相談箱 以下のプログラミング（C++）がわかりません。
以下のプログラミング（C++）がわかりません。
質問者：kens-1813 以下の問題のプログラミング（C++）がわかりません。誰かわかる人いますか？

フィボナッチ数列f1=1,f2=1,f3=2,f4=3…は漸化式
f1=1,f2=1 n≧3でfn=f(n-1)+f(n-2)
で定義されます。
(a)fnを計算する関数f(n)を、再帰的定義を用いて作ってください。

(b)画面から入力された整数nに対して、フィボナッチ数列fnを出力するプログラムを書いてください。かならず、(a)で作った関数を呼び出すようにしてください。

ひでぇ

上の雑記帖では質問が酷いといっているのか回答が酷いといっているのかわからないけど、わたしは質問が酷すぎると思った。 自分で考えたという形跡がまったく見られない。再帰がわからないならそのことを質問するべきだし、 コードを書いてみたんだけどエラーがでてしまって動かないとか、いつまでたっても処理が終わらないなら 自分が書いたコードを添えてどこを直したらいいのかを質問すればいい。

問題をそのまま丸投げでは、そりゃ叩かれる。

まったくの専門外で、一般教養の講義でいきなりこの問題を出されて「再帰」が何なのかさっぱりわからない、 C++ も全くといっていいほどわからないというなら、正直にそのことを書けば解説もついたんだろうけど。 ( 専門外の、専門的な知識が要求される課題の辛さは良くわかっているのでわたしなら回答します )

ついでなので F# と Python で書いてみた。まずは F#

let rec fibonacci = fun integer ->
  match integer with
  | integer when integer <=  0 -> failwith "Invalid Argument"
  | integer when integer <= 2 -> 1
  | integer when integer >  2 -> fibonacci (integer - 1) + fibonacci (integer - 2)
  | _ -> failwith "Invalid Argument";;

で、Python ( 2007/12/28 修正。integer < 0 となっていたのを integer <= 0 に直しました orz )

fibonacci = lambda integer: (None if ((type( integer ) != int) or (integer <= 0)) else 
	(1 if integer <= 2 else (fibonacci( integer - 1 ) + fibonacci( integer - 2 )))
)

追記
C++ でも書いてみた (´･ω･`)

#include <stdio.h>
#include <iostream>

using namespace std;

unsigned long int fibonacci( unsigned long int ordinal_number )
{
	/*
	   関数名 fibonacci
	   引数   ordinal_number 
	   
	   概要:
	   フィボナッチ数列における序数 ordinal_number の時の値を返す。
	   引数が不正だった場合は 0 を返す。
	 */
	
	if( ordinal_number == 0 )
	{
		return 0;
	}
	
	if( ordinal_number <= 2 )
	{
		return 1;
	}else{
		return (fibonacci( ordinal_number - 2 ) + fibonacci( ordinal_number -1 ));
	}
}

int main( void )
{
	for( unsigned long int ordinal_number = 1; ordinal_number <= 10; ++ordinal_number )
	{
		cout << fibonacci( ordinal_number ) << endl;
	}
	
	return 0;
}

どれも漸化式をそのまま実装したのでスピード遅いです(´･ω･`)

2007.12.29 追記
高速版。漸化式をそのまま実装した場合は、引数が 3 以上のとき fibonacci() が (引数 + 1) 回呼び出されるから。 また、再帰の制限をしていないので引数が大きすぎるとスタックを使い果たしてしまう可能性もあります。この問題は、 一般式をちょっと改良したものを実装することで解決できます。

Python の場合

import math
fibonacci = lambda integer: (None if ((type( integer ) != int) or (integer <= 0)) else
    math.floor((((1 + math.sqrt( 5 )) / 2) ** integer / math.sqrt( 5 ) + 0.5))
)

F# の場合

open System;;
let fibonacci = fun ordinal -> 
    match ordinal with
    | ordinal when ordinal <= 0.0 -> failwith "Invalid Argument."
    | ordinal when ordinal <= 2.0 -> 1.0
    | ordinal when ordinal >  2.0 -> Math.Floor( Math.Pow( ((1.0 + Math.Sqrt( 5.0 )) / 2.0 ), ordinal ) / Math.Sqrt( 5.0 ) + 0.5 )
    | _ -> failwith "Invalid Argument.";;