数値Xのフィボナッチ数を計算する

フォボナッチ数とは

フォボナッチ数列は各項が直前の二項の和になっているような数列
フィボナッチ数はその各項

漸化式は一般に

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

ただし n は 2 以上、0 と 1 のときは 0 と 1

Fibonacci(0) = 0
Fibonacci(1) = 1

一般項

Fibonacci(n) = (( 1 + √5 ) / 2 )n - ( 1 - √5 ) / 2 )n ) / √5

一般項

一般項の定義をそのままコードに

float	fibonacci( float	n ){
	float	sqrt_5 = sqrtf( 5.0f );
	return	( powf((( 1.0f + sqrt_5 ) * 0.5f ), n ) - powf((( 1.0f - sqrt_5 ) * 0.5f ), n )) / sqrt_5;
}
int	main(){
	for( int	n = 0; n < 13; ++n ){
		debug_printf( "%f\n", fibonacci( static_cast<float>(n)));
	}
	return	0;
}

再帰

一般項を使うと√が出てきたりして困るので、漸化式の通り再帰を使って整数だけで書くと

int	fibonacci( int	n ){
	int	result = n;
	if( n >= 2 ){
		result = fibonacci( n-2 ) + fibonacci( n-1 );
	}
	return	result;
}
int	main(){
	for( int	n = 0; n < 13; ++n ){
		debug_printf( "%d\n", fibonacci( n ));
	}
	return	0;
}

ループ：その１

再帰はループにできるので

int	fibonacci( int	N ){
	int	p3 = 0;
	if( N ){
		int	p1 = 0;
		int	p2 = 1;
		int	n = 1;
		do{
			p3 = p1 + p2;
			p1 = p2;
			p2 = p3;
		}while( ++n < N );
	}
	return	p3;
}
int	main(){
	for( int	n = 0; n < 13; ++n ){
		debug_printf( "%d\n", fibonacci( n ));
	}
	return	0;
}

ループ：その２

void	fibonacci( int	N ){
	debug_printf( "0" );
	if( N ){
		debug_printf( ",1" );
		int	p1 = 0;
		int	p2 = 1;
		for( int	n = 0; n < N-1; ++n ){
			int	p3 = p1 + p2;
			p1 = p2;
			p2 = p3;
			debug_printf( ",%d", p3 );
		}
	}
	debug_printf( "\n" );
}
int	main(){
	for( int	n = 0; n < 13; ++n ){
		fibonacci( n );
	}
	return	0;
}

テンプレート：その１

テンプレートを使うとコンパイル時に決定されるので定数として利用できる

template<int N> struct fibonacci_helper_t {
	static const int	value = fibonacci_helper_t<N-1>::value + fibonacci_helper_t<N-2>::value;
};
template<> struct fibonacci_helper_t<0> {
	static const int	value = 0;
};
template<> struct fibonacci_helper_t<1> {
	static const int	value = 1;
};
template<int N> int	fibonacci(){
	return	fibonacci_helper_t<N>::value;
}
int	main(){
	debug_printf( "%d\n", fibonacci<10>());
	debug_printf( "%d\n", fibonacci<11>());
	debug_printf( "%d\n", fibonacci<12>());
	return	0;
}

テンプレート：その２

再帰条件がコンパイル時に決定できる再帰はテンプレートにできる

template<int N> struct fibonacci_helper_t {
	static const int	value = fibonacci_helper_t<N-1>::value + fibonacci_helper_t<N-2>::value;
	static void	print(){
		debug_printf( ",%d", value );
	}
};
template<> struct fibonacci_helper_t<0> {
	static const int	value = 0;
	static void	print(){
		debug_printf( "0" );
	}
};
template<> struct fibonacci_helper_t<1> {
	static const int	value = 1;
	static void	print(){
		debug_printf( ",1" );
	}
};
template<int lhs,int rhs> struct less_than_or_equal_to_t {
	static const bool	value = ( lhs <= rhs );
};
template<int max_value,int n = 0,bool = less_than_or_equal_to_t<n,max_value>::value> struct fibonacci_print_helper_t {
	static void	each(){
		debug_printf( "\n" );
	}
};
template<int N,int n> struct fibonacci_print_helper_t<N,n,true> {
	static void	each(){
		fibonacci_helper_t<n>::print();
		fibonacci_print_helper_t<N,n+1>::each();
	}
};
template<int N> void	fibonacci(){
	fibonacci_print_helper_t<N>::each();
}
int	main(){
	fibonacci<10>();
	fibonacci<11>();
	fibonacci<12>();
	return	0;
}