C++で書くフィボナッチ数列

皆さんこんにちは
お元気ですか

たまには面白くフィボナッチ数列をC++で解いてみようかなと思います。

フィボナッチ数列って？

0 1 2 3 5 8 13・・・・・・・となるような結構有名な数列です。
今回３通りの解き方で解いてみたよ

再帰

非常に遅くて有名な再帰です。求めたい値を放り込み、再帰的に計算させていきます。

class RecursiveFibonacci:public Fibonacci{
public:
	virtual int calc(int x);
};

int RecursiveFibonacci::calc(int x){
	if(x == 0){
		return 0;
	}else if(x == 1){
		return 1;
	}else{
		return calc(x - 1) + calc(x - 2);
	}
}

メモ化再帰

再帰ですが、一度求めたものは計算させず、配列に保存した値を返す。O(N)

class MemorizeFibonacci:public Fibonacci{
	int memo[10000] = {0};
public:
	virtual int calc(int x);
};

int MemorizeFibonacci::calc(int x){
	if(x == 0){
		return 0;
	}else if(x == 1){
		return 1;
	}else if(memo[x] != 0){
		return memo[x];
	}
	memo[x] = calc(x-1) + calc(x-2);
}

動的計画法

メモ化再帰と違う点は初めから順番に行う操作（計算）を行う点ですね。O(N)

class DPFibonacci:public Fibonacci{
public:
	virtual int calc(int x);
};

int DPFibonacci::calc(int x){
	int dp[1000] = {0};
	dp[0] = 0;
	dp[1] = 1;
	for(int i = 2; i < x; i++){
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[x];
}

因みに５０で時間を比較すると全く違います。
再帰で行うシステムはn = 50で165秒かかります。
ほかはほとんどかかりませんが・・・・

参考文献

DPとは何か フィボナッチで - 簡潔なQ

ソースコード全て

#include <iostream>
#include <vector>

using namespace std;

class Fibonacci{
public:
	virtual int calc(int x) = 0;	
};

class RecursiveFibonacci:public Fibonacci{
public:
	virtual int calc(int x);
};

int RecursiveFibonacci::calc(int x){
	if(x == 0){
		return 0;
	}else if(x == 1){
		return 1;
	}else{
		return calc(x - 1) + calc(x - 2);
	}
}

class MemorizeFibonacci:public Fibonacci{
	int memo[10000] = {0};
public:
	virtual int calc(int x);
};

int MemorizeFibonacci::calc(int x){
	if(x == 0){
		return 0;
	}else if(x == 1){
		return 1;
	}else if(memo[x] != 0){
		return memo[x];
	}
	memo[x] = calc(x-1) + calc(x-2);
}

class DPFibonacci:public Fibonacci{
public:
	virtual int calc(int x);
};

int DPFibonacci::calc(int x){
	int dp[1000] = {0};
	dp[0] = 0;
	dp[1] = 1;
	for(int i = 2; i < x; i++){
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[x];
}

class TimeFibonatti{
public:
	Fibonacci *t_fib;
	void setFibonacci(Fibonacci *fib){
		t_fib = fib;
	}

	void calcTime(int x){
		clock_t start = clock();
		t_fib->calc(x);
		cout << (double)(clock() - start) / CLOCKS_PER_SEC << endl;
	}
};

int main(int argc, char const *argv[]){
	Fibonacci *r_fib = new RecursiveFibonacci();
	Fibonacci *m_fib = new MemorizeFibonacci();
	Fibonacci *dp_fib = new DPFibonacci();

	TimeFibonatti *t_fib = new TimeFibonatti();
	vector<Fibonacci*> fib(3);
	fib[0] = r_fib;fib[1] = m_fib;fib[2] = dp_fib;

	for(int i = 0; i < fib.size(); i++){
		t_fib->setFibonacci(fib[i]);
		t_fib->calcTime(50);
	}
	return 0;
}